a,b,c a,b,c a,b,c
c a,b,c b,c a,b,c r
a,b,c
16．设NFA M=({q0,q1},{a,b},ζ,q0,{q1}),其中ζ如下： ζ(q0,a)={q0,q1} ζ(q0,b)={q1} ζ(q1,a)= Φ ζ(q1,b)= {q0, q1} 构造相应的DFA M1，并进行化简
答：构造一个相应的DFA M1={Q1, {a,b},ζ1, [q0],{ [q1]，[q0,q1]} 其中Q1 ={[q0]，[q1]，[q0,q1]} ζ1满足 a b [q0] [q0,q1] [q1] [q1] [q0,q1] Φ [q0,q1] [q0,q1] [q0,q1] 由于该DFA已是最简，故不用化简
17.使用泵浦引理，证明下列集合不是正则集：
（1） 由文法G的生成式S→aSbS/c产生的语言L(G) （2） {ω/ω∈{a,b}*且ω有相同个数的a和b} （3） {akcak/k≥1}
（4） {ωω/ω∈{a,b}*}
证明：（1）在L(G)中，a的个数与b的个数相等
假设L(G)是正则集，对于足够大的k取ω= ak (cb)kc 令ω=ω1ω0ω2
因为|ω0|>0 |ω1ω0|≤k 存在ω0使ω1ω0iω2∈L 所以对于任意ω0只能取ω0=an n∈(0,k)
则ω1ω0iω2= ak–n(an)i(cb)kc 在i不等于0时不属于L 与假设矛盾。则L(G)不是正则集
k k
（2）假设该集合是正则集，对于足够大的k取ω= ab令ω=ω1ω0ω2
因为|ω0|>0 |ω1ω0|≤k 存在ω0使ω1ω0iω2∈L
n
所以对于任意ω0只能取ω0=a n∈(0,k)
则ω1ω0iω2= ak–n(an)ibk 在i不等于0时a与b的个数不同，不属于该集合 与假设矛盾。则该集合不是正则集
（3）假设该集合是正则集，对于足够大的k取ω= ak cak 令ω=ω1ω0ω2
因为|ω0|>0 |ω1ω0|≤k 存在ω0使ω1ω0iω2∈L
所以对于任意ω0只能取ω0=an n∈(0,k)
则ω1ω0iω2= ak–n(an)icak 在i不等于0时c前后a的个数不同，不属于该集合 与假设矛盾。则该集合不是正则集
k k
（4）假设该集合是正则集，对于足够大的k取ωω= abab令ωω=ω1ω0ω2
因为|ω0|>0 |ω1ω0|≤k 存在ω0使ω1ω0iω2∈L 所以对于任意ω0只能取ω0=an n∈(0,k)
则ω1ω0iω2= ak–n(an)ibakb 在i不等于0时不满足ωω的形式，不属于该集合 与假设矛盾。则该集合不是正则集
18．构造米兰机和摩尔机
对于{a,b}*的字符串，如果输入以bab结尾，则输出1；如果输入以bba结尾，则输出2；否则输出3。 答：米兰机： 说明状态qaa表示到这个状态时，输入的字符串是以aa结尾。其他同理。
a/3
qaa b/3 qab a/3 a/3 b/3 b/1 qba qbb a/2 b/3
摩尔机，状态说明同米兰机。
a a b a qaa,3 qaab,3 qaba,3
b/3 b/3 b/3
a b a b
qbba,2 qbab,1 a qbb,3 b b/3 b/3 b/3 b b ? 第四章
10. 把下列文法变换为无ε生成式、无单生成式和没有无用符号的等价文法：
S →A1 | A2 , A1 →A3 | A4 , A2 →A4 | A5 , A3 →S | b |ε, A4 →S | a，A5 →S | d |ε
解: ⑴ 由算法3，变换为无ε生成式：
N’ = { S, A1,A2,A3,A4,A5 }
G1 = ( { S1,S, A1,A2,A3,A4,A5 } , { a,b,d }, P1 , S1 ) ,其中生成式P1如下： S1 →ε| S , S →A1 | A2 , A1 →A3 | A4 , A2 →A4 | A5 , A3 →S | b , A4 →S | a , A5 →S | d ,
⑵ 由算法4，消单生成式：
NS1 = { S1,S,A1,A2,A3,A4, A5 } ,
NS = NA1 = NA2 = NA3 = NA4 = NA5 = { S, A1,A2,A3,A4, A5 } , 运用算法4，则P1变为： S1 →a | b | d |ε , S →a | b | d , A1 →a | b | d , A2 →a | b | d , A3 →a | b | d , A4 →a | b | d , A5 →a | b | d
⑶ 由算法1和算法2，消除无用符号，得到符合题目要求的等价文法：
G1 = ( { S1 } , { a,b,d } , P1 , S1 ) ，其中生成式P1为：S1 →a | b | d |ε.
11. 设2型文法G = ( { S,A,B,C,D,E,F } , { a,b,c } , P , S ) , 其中P：
S →ASB |ε; A →aAS | a ; B →SBS | A | bb
试将G变换为无ε生成式,无单生成式,没有无用符号的文法,再将其转换为Chomsky范式.
解: ⑴ 由算法3，变换为无ε生成式：
N’ = { S }
由S →ASB得出S →ASB | AB , 由A →aAS得出A →aAS | aA ,
由B →SBS得出B →SBS | SB | BS |B, 由S∈N’ 得出S1 →ε| S ,
因此无ε的等效文法G1 = ( { S1,S,A,B } , { a,b,d } , P1 , S1 ) ,其中生成式P1如下： S1 →ε| S , S →ASB | AB , A →aAS | aA | a,
B →SBS | SB | BS | B| A | bb , ⑵ 由算法4，消单生成式：
NS1 = { S1,S } , NS = { S } , NA = { A } , NB = { A,B }
由于S →ASB | AB∈P且不是单生成式,故P1中有S1 →ε| ASB | AB ,
同理有 S →ASB | AB , A →aAS | aA | a , B →SBS | SB | BS | aAS | aA | a | bb,
因此生成的无单生成式等效文法为
G1 = ( { S1,S, A,B } , { a,b } , P1 , S1 ) ,其中生成式P1如下： S1 →ε| ASB | AB , S →ASB | AB , A →aAS | aA | a ,
B →SBS | SB | BS | aAS | aA | a | bb,
⑶ 由算法1和算法2，消除无用符号(此题没有无用符号); ⑷ 转化为等价的Chomsky范式的文法:
将S1 →ASB变换为 S →AC , C →SB , 将S →ASB 变换为 S →AC ,
将A →aAS | aA 变换为 A →ED | EA, D →AS , E →a,
将B →SBS | aAS | aA | a | bb , 变换为 B →CS | ED | EA | FF, F →b , ⑸ 由此得出符合题目要求的等价文法：
G1 = ( { S1,S, A,B,C,D } , { a,b } , P1 , S1 ) ,其中生成式P1如下： S1 →ε| AC | AB , S →AC | AB , A →ED | EA | a ,
B →CS | SB | BS | ED | EA | a | FF , C →SB , D →AS , E →a , F →b .
15. 将下列文法变换为等价的Greibach范式文法:
⑴ S →DD | a , D →SS | b
解: 将非终结符排序为S,D,S为低位,D为高位, ⑴ 对于D →SS ,用S →DD | a 代入得 D →DDS | aS | b ,
用引理4.2.4,变化为D →aS | b | aSD' | bD' , D’ →DS | DSD’ , ⑵ 将D生成式代入S生成式得 S →aSD | bD | aSD’D | bD'D | a , ⑶ 将D生成式代入D’生成式得
D’ →aSS | bS | aSD'S | bD'S | aSS D' | bS D' | aSD'S D' | bD'S D' , ⑷ 由此得出等价的Greibach范式文法：
G1 = ( { S,D,D’ } , { a,b } , P1 , S ) ,其中生成式P1如下： S →aSD | bD | aSD’D | bD'D | a , D →aS | b | aSD' | bD' ,
D’ →aSS | bS | aSD'S | bD'S | aSS D' | bS D' | aSD'S D' | bD'S D' .
⑵ A1 →A3b | A2a , A2 →A1b | A2A2a | b , A3 →A1a | A3A3b | a 解: ⑴ 转化为等价的Chomsky范式的文法: A1 →A3A4 | A2A5 ,
A2 →A1A4 | A2A6 | b , A3 →A1A5 | A3A7 | a , A4 →b , A5 →a ,
A6 →A2A5 , A7 →A3A4 ,
⑵ 转化为等价的Greibach范式的文法:
将非终结符排序为A1, A2,A3,A4,A5 ,A1为低位A5为高位,
①对于A2 →A1A4 ,用A1 →A3A4 | A2A5代入得A2 →A3A4A4 | A2 A5A4 | A2A6 | b ,
用引理4.2.4,变化为
A2 →A3A4A4 | b | A3A4A4A2’ | bA2’ , A2’ →A5A4A2’ | A6A2’ | A5A4 | A6 ,
②对于A3 →A1A5 ,用A1 →A3A4 | A2A5代入得A3 →A3A4A5 | A2A5A5 | A3A7 | a ,
A3生成式右边第一个字符仍是较低位的非终结符,将A2生成式代入A3生成式得
A3 →A3A4 A5 | A3A4A4 A5A5 | b A5A5 | A3A4A4A2’ A5A5 | bA2’A5A5 | A3A7 | a ,
用引理4.2.4,变化为
A3 →b A5A5 | bA2’A5A5 | a | b A5A5A3’ | bA2’A5A5A3’ | aA3’ ,
A3’ →A4A5 | A4A4A5A5 | A4A4A2’A5A5 | A7 | A4A5A3’ | A4A4A5A5A3’ | A4A4A2’A5A5A3’ | A7A3’ ,
③对于A6 →A2A5 ,将A2生成式代入A6生成式得 A6 →A3A4A4A5 | bA5 | A3A4A4A2’A5 | bA2’A5 ,
A6生成式右边第一个字符仍是较低位的非终结符,将A3生成式代入A6生成式得
A6 →bA5A5A4A4A5 | bA2’A5A5A4A4A5 | aA4A4A5 | bA5A5A3’A4A4A5 | bA2’A5A5A3’A4A4A5 | aA3’A4A4A5 | bA5A5A4A4A2’A5 | bA2’A5A5A4A4A2’A5 | aA4A4A2’A5 | bA5A5A3’A4A4A2’A5 | bA2’A5A5A3’A4A4A2’A5 | aA3’A4A4A2’A5 | bA2’A5 | b A5 ,
④对于A7 →A3A4 , 将A3生成式代入A7生成式得
A7 →b A5A5A4 | bA2’A5A5A4 | a A4 | b A5A5A3’A4 | bA2’A5A5A3’A4 | aA3’A4 ,
⑤将A5,A6生成式代入A2’生成式得
A2’ →aA4A2’ | bA5A5A4A4A5A2’ | bA2’A5A5A4A4A5A2’ | aA4A4A5A2’ | bA5A5A3’A4A4A5A2’ | bA2’A5A5A3’A4A4A5A2’ | aA3’A4A4A5A2’ | bA5A5A4A4A2’A5 A2’ | bA2’A5A5A4A4A2’A5A2’ | aA4A4A2’A5A2’ | bA5A5A3’A4A4A2’A5A2’ | bA2’A5A5A3’A4A4A2’A5A2’ | aA3’A4A4A2’A5A2’ | bA2’A5A2’ | b A5A2’ | aA4 | b A5A5A4A4A5 | bA2’A5A5A4A4A5 | aA4A4A5 | bA5A5A3’A4A4A5 | bA2’A5A5A3’A4A4A5 | aA3’A4A4A5 | bA5A5A4A4A2’A5 | bA2’A5A5A4A4A2’A5 | aA4A4A2’A5 | bA5A5A3’A4A4A2’A5 | bA2’A5A5A3’A4A4A2’A5 | aA3’A4A4A2’A5 | bA2’A5 | b A5 , 将A4,A7生成式代入A3’生成式得
A3’ →aA5 | aA4A5A5 | aA4A2’A5A5 | aA5A3’ | aA4A5A5A3’ | aA4A2’A5A5A3’ | b A5A5A4 | bA2’A5A5A4 | aA4 | bA5A5A3’A4 | bA2’A5A5A3’A4 | aA3’A4 | bA5A5A4A3’ | bA2’A5A5A4A3’ | a A4A3’ | b A5A5A3’A4 A3’ | bA2’A5A5A3’A4 A3’ | aA3’A4A3’ ,