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