不完全，不保证正确，不过部分答案通过课程实验编写的程序进行了验证。有空可能整到 BYRDocs 上，不过大概率没空。仅供参考。
有限自动机的转化部分
（来源：22-23 期末试题 1 && 2 && 3）
%EF%BC%9A%E5%BE%80%E5%B9%B4%E9%A2%98%E9%83%A8%E5%88%86%E4%B8%AA%E4%BA%BA%E8%A7%A3%E6%9E%90/10.png)
解析：
%EF%BC%9A%E5%BE%80%E5%B9%B4%E9%A2%98%E9%83%A8%E5%88%86%E4%B8%AA%E4%BA%BA%E8%A7%A3%E6%9E%90/11.png)
（来源：19-20 期末试题 5）
%EF%BC%9A%E5%BE%80%E5%B9%B4%E9%A2%98%E9%83%A8%E5%88%86%E4%B8%AA%E4%BA%BA%E8%A7%A3%E6%9E%90/12.png)
解析：
转换后的 NFA ：
%EF%BC%9A%E5%BE%80%E5%B9%B4%E9%A2%98%E9%83%A8%E5%88%86%E4%B8%AA%E4%BA%BA%E8%A7%A3%E6%9E%90/14.png)
转换后的 DFA ：
%EF%BC%9A%E5%BE%80%E5%B9%B4%E9%A2%98%E9%83%A8%E5%88%86%E4%B8%AA%E4%BA%BA%E8%A7%A3%E6%9E%90/13.png)
（来源：19-20 期末试题 5）
%EF%BC%9A%E5%BE%80%E5%B9%B4%E9%A2%98%E9%83%A8%E5%88%86%E4%B8%AA%E4%BA%BA%E8%A7%A3%E6%9E%90/15.png)
解析：
转换后的 NFA ：
%EF%BC%9A%E5%BE%80%E5%B9%B4%E9%A2%98%E9%83%A8%E5%88%86%E4%B8%AA%E4%BA%BA%E8%A7%A3%E6%9E%90/16.png)
转换后的 DFA ：
%EF%BC%9A%E5%BE%80%E5%B9%B4%E9%A2%98%E9%83%A8%E5%88%86%E4%B8%AA%E4%BA%BA%E8%A7%A3%E6%9E%90/17.png)
（来源：19-20 期末试题 3）
%EF%BC%9A%E5%BE%80%E5%B9%B4%E9%A2%98%E9%83%A8%E5%88%86%E4%B8%AA%E4%BA%BA%E8%A7%A3%E6%9E%90/20.png)
试题 1 和 2 类似，略。
解析：
转换后的 NFA ：
%EF%BC%9A%E5%BE%80%E5%B9%B4%E9%A2%98%E9%83%A8%E5%88%86%E4%B8%AA%E4%BA%BA%E8%A7%A3%E6%9E%90/18.png)
转换后的 DFA ：
%EF%BC%9A%E5%BE%80%E5%B9%B4%E9%A2%98%E9%83%A8%E5%88%86%E4%B8%AA%E4%BA%BA%E8%A7%A3%E6%9E%90/19.png)
上下文无关文法的转化部分
（来源：某年期末 B 卷）
%EF%BC%9A%E5%BE%80%E5%B9%B4%E9%A2%98%E9%83%A8%E5%88%86%E4%B8%AA%E4%BA%BA%E8%A7%A3%E6%9E%90/1.png)
解析：
- 先化简 CFG ：
1
2
3
4
5
6
7
8
9
| N = { A, B, C, D, S }
T = { a, b, c }
P:
A -> b
B -> A C | B C | b
C -> b
D -> a B | c
S -> A B | A C | B C | C D D | b
S = S
|
- 转换为 CNF ：
1
2
3
4
5
6
7
8
9
10
11
| N = { A, B, C, D, S, E, G}
T = { a, b, c }
P:
A -> b
B -> A C | B C | b
C -> b
D -> E B | c
S -> A B | A C | B C | C G | b
E -> a
G -> D D
S = S
|
（来源：21-22 期末试题 5）
%EF%BC%9A%E5%BE%80%E5%B9%B4%E9%A2%98%E9%83%A8%E5%88%86%E4%B8%AA%E4%BA%BA%E8%A7%A3%E6%9E%90/2.png)
解析：已经是最简的 CFG ，Chomsky 范式如下：
1
2
3
4
5
6
7
8
9
10
11
12
| N = { S, A, B }
T = { a, b, c }
P:
S -> C C | A B
A -> C F | D S | a
B -> D G | E S | b
C -> b
D -> a
E -> c
F -> D A
G -> B B
S = S
|
（来源：21-22 期末试题 4）
%EF%BC%9A%E5%BE%80%E5%B9%B4%E9%A2%98%E9%83%A8%E5%88%86%E4%B8%AA%E4%BA%BA%E8%A7%A3%E6%9E%90/3.png)
解析：
- 先化简 CFG ：（ A 不可达）
1
2
3
4
5
6
| N = { B, S }
T = { a, b, c }
P:
B -> a B B | b | c S
S -> a B | b b
S = S
|
- 转换为 CNF ：
1
2
3
4
5
6
7
8
9
10
| N = { S, B, C, D, E, F }
T = { a, b, c }
P:
S -> C C | D B
B -> D F | E S | b
C -> b
D -> a
E -> c
F -> B B
S = S
|
（来源：21-22 期末试题 3）
%EF%BC%9A%E5%BE%80%E5%B9%B4%E9%A2%98%E9%83%A8%E5%88%86%E4%B8%AA%E4%BA%BA%E8%A7%A3%E6%9E%90/4.png)
解析：已经是最简的 CFG ，Chomsky 范式如下：
1
2
3
4
5
6
7
8
9
10
11
| N = { A, B, C, D, S, E, F}
T = { a, b, c }
P:
S -> C A | D B
A -> C D A | D S | a
B -> D F | E S | b
C -> b
D -> a
E -> c
F -> B B
S = S
|
（21-22 期末试题 1 和 2 基本没区别，不打了）
（来源：19-20 期末试题 5）
%EF%BC%9A%E5%BE%80%E5%B9%B4%E9%A2%98%E9%83%A8%E5%88%86%E4%B8%AA%E4%BA%BA%E8%A7%A3%E6%9E%90/5.png)
解析：（ A 可致空，(A, B) 是单元偶对，C 非生成）
1
2
3
4
5
6
7
8
| N = { A, B, D, S }
T = { a, b, c, d }
P:
A -> a b B
B -> a | a A
D -> d d d
S -> a | a A | b | b A | c c D
S = S
|
（来源：19-20 期末试题 4）
%EF%BC%9A%E5%BE%80%E5%B9%B4%E9%A2%98%E9%83%A8%E5%88%86%E4%B8%AA%E4%BA%BA%E8%A7%A3%E6%9E%90/6.png)
解析：（ A 可致空，(S, A) 和 (S, B) 是单元偶对，C 非生成，D 不可达）
1
2
3
4
5
6
7
| N = { A, B, S }
T = { a, d }
P:
A -> a B
B -> a | a A
S -> a | a A | d d d
S = S
|
（来源：19-20 期末试题 3）
%EF%BC%9A%E5%BE%80%E5%B9%B4%E9%A2%98%E9%83%A8%E5%88%86%E4%B8%AA%E4%BA%BA%E8%A7%A3%E6%9E%90/7.png)
解析：（ A 可致空，(S, B)，(S, C)，(S, D) 是单元偶对，C 非生成，D 不可达）
1
2
3
4
5
6
7
| N = { A, B, S }
T = { a, d }
P:
A -> a B
B -> A a | a
S -> A a | a | a a | d d
S = S
|
（来源：19-20 期末试题 2）
%EF%BC%9A%E5%BE%80%E5%B9%B4%E9%A2%98%E9%83%A8%E5%88%86%E4%B8%AA%E4%BA%BA%E8%A7%A3%E6%9E%90/8.png)
解析：（ A 可致空，(S, B) 和 (S, C) 是单元偶对，C 非生成，D 不可达）
1
2
3
4
5
6
7
| N = { A, B, S }
T = { a }
P:
A -> a B
B -> a | a A
S -> a | a A | a a a
S = S
|
（来源：19-20 期末试题 1）
%EF%BC%9A%E5%BE%80%E5%B9%B4%E9%A2%98%E9%83%A8%E5%88%86%E4%B8%AA%E4%BA%BA%E8%A7%A3%E6%9E%90/9.png)
解析：（ A 可致空，(S, B) 和 (S, C) 是单元偶对，C 非生成，D 不可达）
1
2
3
4
5
6
7
| N = { A, B, S }
T = { a }
P:
A -> a B
B -> a | a A
S -> a | a A
S = S
|