形式语言与自动机课后习题答案
第二章
4．找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。
答：G={N,T,P,S}
其中N={S,A,B,C,D} T={x,y} 其中x∈{所有字母} y∈{所有的字符} P如下:
S→x S→xA A→y A→yB
B→y B→yC C→y C→yD D→y
6．构造上下文无关文法能够产生
L={ω/ω∈{a,b}*且ω中a的个数是b的两倍}
答：G={N,T,P,S}
其中N={S} T={a,b} P如下:
S→aab S→aba S→baa
S→aabS S→aaSb S→aSab S→Saab
S→abaS S→abSa S→aSba S→Saba
S→baaS S→baSa S→bSaa S→Sbaa
7．找出由下列各组生成式产生的语言（起始符为S）
(1)S→SaS S→b
(2)S→aSb S→c
(3)S→a S→aE E→aS
答：（1）b(ab)n /n≥0}或者L={(ba)nb /n≥0}
(2) L={ancbn /n≥0}
(3) L={a2n+1 /n≥0}
第三章
1．下列集合是否为正则集，若是正则集写出其正则式。
（1）含有偶数个a和奇数个b的{a,b}*上的字符串集合
（2）含有相同个数a和b的字符串集合
（3）不含子串aba的{a,b}*上的字符串集合
答：（1）是正则集，自动机如下
a
a
b b b b
a
a
(2) 不是正则集，用泵浦引理可以证明，具体见17题（2）。
(3) 是正则集
先看L’为包含子串aba的{a,b}*上的字符串集合
显然这是正则集，可以写出表达式和画出自动机。（略）
则不包含子串aba的{a,b}*上的字符串集合L是L’的非。
根据正则集的性质，L也是正则集。
4．对下列文法的生成式，找出其正则式
（1）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下：
S→aA S→B
A→abS A→bB
B→b B→cC
C→D D→bB
D→d
（2）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下：
S→aA S→B
A→cC A→bB
B→bB B→a
C→D C→abB
D→d
答：(1) 由生成式得：
S=aA+B ①
A=abS+bB ②
养螃蟹喂什么B=b+cC ③
C=D ④
D=d+bB ⑤
③④⑤式化简消去CD，得到B=b+c(d+bB)
即B=cbB+cd+b =>B=(cb)*(cd+b) ⑥
将②⑥代入①
S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =>S=(aab)*(ab+ε)(cb)*(cd+b)
(2) 由生成式得：
S=aA+B ①
A=bB+cC ②
B=a+bB ③
C=D+abB ④
D=dB ⑤
由③得 B=b*a ⑥
将⑤⑥代入④ C=d+abb*a=d+ab+a ⑦
将⑥⑦代入② A=b+a+c(d+b+a) ⑧
将⑥⑧代入① S=a(b+a+c(d+ab+a))+b*a
=ab+a+acd+acab+a+b*a
5.为下列正则集，构造右线性文法：
(1){a,b}*
(2)以abb结尾的由a和b组成的所有字符串的集合
(3)以b为首后跟若干个a的字符串的集合
(4)含有两个相继a和两个相继b的由a和b组成的所有字符串集合
答：（1）右线性文法G=({S},{a,b},P,S)
P: S→aS S→bS S→ε
(2) 右线性文法G=({S},{a,b},P,S)
P: S→aS S→bS S→abb
(3) 此正则集为{ba*}
右线性文法G=({S,A},{a,b},P,S)
P: S→bA A→aA A→ε
(4) 此正则集为{{a,b}*aa{a,b}*bb{a,b}*, {a,b}*bb{a,b}*aa{a,b}*}
右线性文法G=({S,A,B,C},{a,b},P,S)
P: S→aS/bS/aaA/bbB
A→aA/bA/bbC
B→aB/bB/aaC
C→aC/bC/ε
7.设正则集为a(ba)*
(1)构造右线性文法
(2)找出（1）中文法的有限自 b动机
答：（1）右线性文法G=({S,A},{a,b},P,S)
P: S→aA A→bS A→ε
（2）自动机如下：
a
b
(p2是终结状态)
9.对应图（a）(b)的状态转换图写出正则式。（图略）
（1）由图可知q0=aq0+bq1+a+ε
q1=aq2+bq1
q0=aq0+bq1+a
=>q1=abq1+bq1+aaq0+aa
=(b+ab) q1+aaq0+aa
=(b+ab) *( aaq0+aa)
=>q0=aq0+b(b+ab) *( aaq0+aa ) +a+ε
= q0(a+b (b+ab) *aa)+ b(b+ab) *aa+a+ε
=(a+b (b+ab) *aa) *((b+ab) *aa+a+ε)
=(a+b (b+ab) *aa) *
(3)q0=aq1+bq2+a+b
q1=aq0+bq2+b
q0=aq1+bq0+a
=>q1=aq0+baq1+bbq0+ba+b
=(ba)*(aq0 +bbq0+ba+b)
=>q2=aaq0+abq2+bq0+ab+a
=(ab)*(aaq0 +bq0+ ab+a)
=>q0=a(ba)*(a+bb) q0 + a(ba)*(ba+b)+b(ab)*(aa+b)q0+ b(ab)*(ab+a)+a+b
=[a(ba)*(a+bb) +b(ab)*(aa+b)]* (a(ba)*(ba+b)+ b(ab)*(ab+a)+a+b)
10.设字母表T={a,b},找出接受下列语言的DFA：
（1）含有3个连续b的所有字符串集合
（2）以aa为首的所有字符串集合
（3）以aa结尾的所有字符串集合
答：（1）M=({q0,q1 q2,q3},{a,b},σ,q0,{q3}),其中σ如下：
| a | b |
q0 | q0 | q1 |
q1魔鬼交易 | q0 | q2 |
q2 | q0 | q3 |
q3 | q3 | q3 |
| | |
（2）M=({q0,q1 q2 },{a,b},σ,q0,{q2}),其中σ如下：
（3）M=({q0,q1 q2 },{a,b},σ,q0,{q2}),其中σ如下：
| a | b |
q0 | q1 | q0 |
q1 五彩小泡泡 | q2 | q0 |
q2 | q2 | q0 |
| | |
14构造DFA M1等价于NFA M，NFA M如下：
（1）M=({q0,q1 q2,q3},{a,b},σ,q0,{q3}),其中σ如下：
σ(q0,a)={q0五分钟演讲,q1} σ(q0,b)={q0}
σ(q1,a)={q2} σ(q1,b)= {q2 }
σ(q2,a)={q3} σ(q2,b)= Φ
σ(q3,a)={q3} σ(q3,b)= {q3 }
（2）M=({q0,q1 q2,q3},{a,b},σ,q0,{ q1,q2}),其中σ如下：
σ(q0,a)={q1,q2} σ(q0,b)={q1}
σ(q1,a)={q2} σ(q1,b)= {q1,q2 }
σ(q2,a)={q3} σ(q2,b)= {q0}
σ(q3,a)= Φσ(q3,b)= {q0}
答：（1）DFA M1={Q1, {a,b},σ1, [q0],{ [q0,q1,q3]，[q0,q2,q3]，[q0, q1,q2,q3]}
其中Q帅气动漫壁纸1 ={[q0],[q0,q1], [q0,q1,q2],[ q0,q2],[ q0,q1, q2,q3],[ q0,q1, q3],[ q0,q2, q3],[ q0,q3]}
σ1满足
| a | b |
[q0] | [q0,q1] | [ q0] |
[q0,q1] | [q0,q1,q2] | [ q0,q2] |
[q0,q1,q2] | [ q0,q1, q2,q3] | [ q0,q2] |
[ q0,q2] | [ q0,q1, q3] | [q0] |
[ q0,q1, q2,q3] | [ q0,q1, q2,q3] | [ q0,q2, q3] |
[ q0,q1, q3] | [ q0,q1, q2,q3] | [ q0,q2, q3] |
[ q0,q2, q3] | [ q0,q1, q3] | [ q0,q3] |
[ q0,q3] | [ q0,q1, q3] | [ q0,q3] |
| | |
（2）DFA M1={Q1, {a,b},σ1, [q0],{ [q1],[q3], [q1,q3],[q0,q1,q2],[q1,q2] ,[q1,q2,q3],[q2,q3]
}
其中Q1 ={[q0],[q1,q3], [q1],[q2],[ q0,q1,q2],[q1,q2],[q3], [q1,q2,q3],[q2,q3]}
σ1满足
| a | b |
[q0] | [q1,q3] | [q1] |
[q1,q3] | [q2] | [ q0,q1,q2] |
[q1] | [q2] | [q1,q2] |
[q2] | [q3] | [q0] |
[ q0,q1,q2] | [q1,q2,q3] | [ q0,q1,q2] |
[q1,q2] | [q2,q3] | [ q0,q1,q2] |
[q3] | Φ | [q0] |
[q1,q2,q3] | 美德即知识[q2,q3] | [ q0,q1,q2] |
[q2,q3] | [q3] | [q0] |
| | |
15. 15.对下面矩阵表示的ε-NFA
| ε | a | b | c |
P(起始状态) | φ | {p} | {q} | {r} |
q 说能组什么词 | {p} | {q} | {r} | φ |
r(终止状态) | {q} | {r} | φ | {p} |
| | | | |
(1)给出该自动机接收的所有长度为3的串
(2)将此ε-NFA转换为没有ε的NFA
答：（1）可被接受的的串共 23个，分别为aac, abc, acc, bac, bbc, bcc, cac, cbc, ccc, caa, cab, cba, cbb, cca, ccb, bba, aca, acb, bca, bcb, bab, bbb, abb
（2）ε-NFA：M=({p,q,r},{a,b,c},σ,p,r) 其中σ如表格所示。
因为ε-closure(p)= Φ
则设不含ε的NFA M1=({p,q,r},{a,b,c},σ1,p,r)
σ1(p,a)=σ’(p,a)=ε-closure(σ(σ’(p,ε),a))={p}
σ1(p,b)=σ’(p,b)=ε-closure(σ(σ’(p,ε),b))={p,q}
σ华夏说1(p,c)=σ’(p,c)=ε-closure(σ(σ’(p,ε),c))={p,q,r}
