《形式语言与自动机》（王柏、杨娟编著）答案

形式语言与自动机课后习题答案

第二章

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 偶 b a 奇a偶b a b b b b 偶a奇b a 奇a奇b 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 ②

右线性文法G=({S,A,B,C},{a,b},P,S) 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}*}

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 P1 b P2 (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}),其中ζ如下： a b q0 q1 Φ q1 q2 Φ q2 q2 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]} 其中Q1 ={[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} ζ1(q,a)=ζ’(q,a)=ε-closure(ζ(ζ’(q,ε),a))={p,q} ζ1(q,b)=ζ’(q,b)=ε-closure(ζ(ζ’(q,ε),b))={p,q,r} ζ1(q,c)=ζ’(q,c)=ε-closure(ζ(ζ’(q,ε),c))={p,q,r} ζ1(r,a)=ζ’(r,a)=ε-closure(ζ(ζ’(r,ε),a))={p,q,r} ζ1(r,b)=ζ’(r,b)=ε-closure(ζ(ζ’(r,ε),b))={p,q,r} ζ1(r,c)=ζ’(r,c)=ε-closure(ζ(ζ’(r,ε),c))={p,q,r} 图示如下：(r为终止状态)

b,c a,b,c p a,b,c q 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)k

c 令ω=ω1ω0ω2

因为|ωi0|>0 |ω1ω0|≤k 存在ω0使ω1ω0ω2∈L 所以对于任意ωn0只能取ω0=a n∈(0,k)

则ωik–nnik

1ω0ω2= a(a)(cb)c 在i不等于0时不属于L 与假设矛盾。则L(G)不是正则集

（2）假设该集合是正则集，对于足够大的k取ω= ak bk 令ω=ω1ω0ω2

因为|ωi0|>0 |ω1ω0|≤k 存在ω0使ω1ω0ω2∈L

所以对于任意ωn

0只能取ω0=a n∈(0,k)

则ω1ωii0ω2= ak–n(an)bk 在i不等于0时a与b的个数不同，不属于该集

合

与假设矛盾。则该集合不是正则集

（3）假设该集合是正则集，对于足够大的k取ω= ak cak 令ω=ω1ω0ω2

因为|ω0|>0 |ω1ω0|≤k 存在ω0使ωi1ω0ω2∈L 所以对于任意ωn0只能取ω0=a n∈(0,k)

则ωik–n1ω0ω2= a(an)icak 在i不等于0时c前后a的个数不同，不属于该集合

与假设矛盾。则该集合不是正则集

（4）假设该集合是正则集，对于足够大的k取ωω= ak bakb 令ωω=ω1ω0ω2

因为|ω0|>0 |ω1ω0|≤k 存在ω0使ω1ωi0ω2∈L 所以对于任意ω0只能取ω0=an n∈(0,k)

则ωi–ni1ω0ω2= ak(an)bakb 在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 a/2 qbb b/3

摩尔机，状态说明同米兰机。

a a b a

qaa,3 qaab,3 qaba,3

b/3 b/3 b/3 a b a b

qbba,2 a qbb,3 qbab,1 b/3 b 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 |ε ,

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库《形式语言与自动机》（王柏、杨娟编著）答案在线全文阅读。