形式語言與自動(dòng)機(jī)王柏楊娟編著課后習(xí)題答案

1、專業(yè)資料形式語言與自動(dòng)機(jī)課后習(xí)題答案第二章4找出右線性文法，能構(gòu)成長度為 1至5個(gè)字符且以字母為首的字符串。答：G=N,T,P,S其中N=S,A,B,C,D T=x,y 其中x 所有字母 y 所有的字符 P如下:4 x Sf xAAf yA f yB4 y Bf yCCf yC f yDD f y6 構(gòu)造上下文無關(guān)文法能夠產(chǎn)生L= 3 / 3 a,b*且3中a的個(gè)數(shù)是b的兩倍 答: G=N,T,P,S其中 N=S T=a,b P 如下：Sf aab S f aba SfbaaSf aabS Sf aaSbSf aSabS f SaabSf abaS Sf abSaSf aSbaS f Saba

2、Sf baaS Sf baSaSf bSaaS f Sbaa7 找出由下列各組生成式產(chǎn)生的語言(起始符為S) Sf SaS S f b Sf aSb S f c(3) Sf a S f aE E f aS答：(1) b(ab) n /n 0或者 L=(ba) nb /n 0(2) L=a ncbn /n 0(3) L=a2n+1 /n 0第三章1.下列集合是否為正則集，若是正則集寫出其正則式。(1) 含有偶數(shù)個(gè)a和奇數(shù)個(gè)b的a,b*上的字符串集合(2) 含有相同個(gè)數(shù)a和b的字符串集合(3) 不含子串a(chǎn)ba的a,b*上的字符串集合答：(1)是正則集，自動(dòng)機(jī)如下b bb b 不是正則集，用泵浦引理

3、可以證明，具體見 17題(2)(3)是正則集先看L 為包含子串a(chǎn)ba的a,b*上的字符串集合 顯然這是正則集，可以寫出表達(dá)式和畫出自動(dòng)機(jī)。(略) 則不包含子串a(chǎn)ba的a,b*上的字符串集合L是L 根據(jù)正則集的性質(zhì)，L也是正則集。4 對下列文法的生成式，找出其正則式(1) G=(SAB,C,D,a,b,c,d,P,S),生成式 P如下:Sf aA S BAf abS A bBB b B f cCC D D f bBDf d(2) G=(SAB,C,D,a,b,c,d,P,S),生成式 P如下:Sf aA S f BAf cC A f bBBf bB B f aCf D C f abBDf d答：

4、(1)由生成式得：S=aA+B A=abS+bBB=b+cC C=DD=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+由生成式得：S=aA+B A=bB+cCB=a+bBC=D+abBD=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*a5.為下列正則集，構(gòu)造右線性文法：(1) a,b*的非& )(

5、cb)*(cd+b) 以abb結(jié)尾的由a和b組成的所有字符串的集合(3) 以b為首后跟若干個(gè)a的字符串的集合(4) 含有兩個(gè)相繼a和兩個(gè)相繼b的由a和b組成的所有字符串集合 答：(1)右線性文法 G=(S,a,b,P,S)P: S f aS S f bS S(2) 右線性文法 G=(S,a,b,P,S)P: S f aS S f bS S f abb(3) 此正則集為ba*右線性文法 G=(S,A,a,b,P,S)P: S f bA A f aA A f(4) 此正則集為a,b*aaa,b*bba,b*, a,b*bba,b*aaa,b* 右線性文法 G=(SAB,C,a,b,P,S)P: S

6、 f aS/bS/aaA/bbBA f aA/bA/bbCBf aB/bB/aaCCf aC/bC/ &7.設(shè)正則集為a(ba)*(1) 構(gòu)造右線性文法找出(1)中文法的有限自b動(dòng)機(jī)答：(1)右線性文法 G=(S,A,a,b,P,S)P: S f aA A f bS A f&(2) 自動(dòng)機(jī)如下：(p2是終結(jié)狀態(tài))9. 對應(yīng)圖(a) (b)的狀態(tài)轉(zhuǎn)換圖寫出正則式。(圖略)(1)由圖可矢廿 qo=aqo+bq1+a+&q 1=aq2+bq1q onaqo+bq+a=q =abq1+bq1 +aaqo+aa=(b+ab) q 1+aaqo+aa=(b+ab) *( aaq o+aa)=qo=aqo+

7、b(b+ab) *( aaq o+aa ) +a+ &=q o(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) qo=aq1+bq2+a+bq1=aqo+bq2+bqo=aq1+bqo+a=q =aqo+baq1+bbqo+ba+b=(ba)*(aq 0 +bbq o+ba+b)=q2=aaqo+abq2+bqo+ab+a=(ab)*(aaq o +bq o+ ab+a)=qo=a(ba)*(a+bb) q 0 + a(ba)*(ba+b)+b(ab)*(a

8、a+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. 設(shè)字母表T=a,b,找出接受下列語言的 DFA(1) 含有3個(gè)連續(xù)b的所有字符串集合(2) 以aa為首的所有字符串集合(3) 以aa結(jié)尾的所有字符串集合答：(1) M=(q0,q 1 q 2,q 3,a,b, o ,q0,q 3),其中如下:14構(gòu)造DFA M1等價(jià)于NFA M, NFA M如下：(1) M=(qo,q 1 q2,q3,a,b,o ,q0,q 3),其中 o如下：o (qo,a)=q 0,q 1 o (

9、q 0,b)=q 0o (q1,a)=q 2 o (q1,b)= q 2 o (q2,a)=q 3o (q2,b)=o (q3,a)=q 3 o (q3,b)= q 3 (2) M=(qo,q 1 q2,q3,a,b,o ,q0, q 1,q 2),其中 o如下：o (qo,a)=q 1,q2o (q 0,b)=q 1o (q1,a)=q 2 o (q1,b)= q q2 o (q2,a)=q 3o (q2,b)= q 0o (q3,a)= o (q3,b)= q 0答：(1) DFA M=Q, a,b, o 1, q o, q0,q1,q3 , q0,q2,q3, q 0, q1,q2,q

10、3其中 Q =q0,q0,q1, q 0,q 1,q2,qo,q2q0,q 1,q2,q 3,q0,q1,q3,qo,q2,q3, q 0,q3o 1滿足abq 0q0,q1q 0q 0,q1q0,q1,q 2q 0,q 2q 0,q 1,q2q 0,q1, q 2,q3q 0,q 2q 0,q 2q 0,q1, q 3q 0q 0,q 1, q 2心q 0,q 1, q 2心q 0,q 2, q 3q 0,q1, q 3q 0,q1, q 2,q3q 0,q2, q 3q 0,q2, q 3q 0,q1, q 3q 0,q 3q 0,q 3q 0,q1, q 3q 0,q 3(2) DFAM

11、=Qi,a,b,1,q。,q Qq 3,qi，q3,q0,qi，q2,qi，q2,q i，q2，q3,q 2，q3其中 Q =q o,q 1,q3,q 1,q2, q0,q 1,q2,q 1,q2,q3,q1,q2,q3,q2,q31滿足abq 0q 1,q3q1q 1,q3q2q 0,q1,q2q 1q2q 1,q 2q 2q3q 0q 0,q1,q2q 1,q2,q 3q 0,q1,q2q 1,q2q2,q3q 0,q1,q2q 3q 0q1,q 2,q3q2,q3q 0,q1,q2q 2,q3q3q 015. 15.對下面矩陣表示的& -NFAabcP（起始狀態(tài)）0pqrqPqr0r（終

12、止?fàn)顟B(tài)）qr0p(1) 給出該自動(dòng)機(jī)接收的所有長度為3的串(2) 將此 -NFA轉(zhuǎn)換為沒有&的NFA答：(1)可被接受的的串共 23個(gè)，分別為 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)其中 如表格所示。因?yàn)? -closure(p)= 則設(shè)不含&的NFA M=(p,q,r,a,b,c, 1,p,r)1(p,a)=(p,a)= -closure(p,

13、),a)=p1(p,b)=(p,b)= -closure(p, ),b)=p,q 1(p,c)=(p,c)= -closure(p, ),c)=p,q,r1(q,a)=(q,a)= -closure(q, ),a)=p,q1(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圖示如下：

14、(r為終止?fàn)顟B(tài)）16. 設(shè) NFA M=(q o,q i,a,b,d ,q0,q1),其中廳如下： (qo,a)=q 0,q 1 d (q 0,b)=q 1d (qi,a)= d (qi,b)= q 0 q 1構(gòu)造相應(yīng)的DFA M1,并進(jìn)行化簡答：構(gòu)造一個(gè)相應(yīng)的 DFA M1=Q1, a,b, d 1, q。, q 1 , q。 其中 Q =q 0 , q1 , q 0,q 1d 1滿足abq 0q0,q1q 1q 1q 0,q1q 0,q1q0,q1q 0,q 1由于該DFA已是最簡，故不用化簡17. 使用泵浦引理，證明下列集合不是正則集：(1) 由文法G的生成式S- aSbS/c產(chǎn)生的語言

15、L(G)(2) 3 /a,b*且3有相同個(gè)數(shù)的 a和bk k(3) a ca /k 1(4) 33 / 3 a,b*證明：(1)在L(G)中，a的個(gè)數(shù)與b的個(gè)數(shù)相等 假設(shè)L(G)是正則集，對于足夠大的k取3 = ak (cb) kc令3 = 3 1 3 0 3 2因?yàn)?| 3 o|O |3 1 3 o| W k 存在 3 0使 3 1 3 0 3 2 L所以對于任意3 0只能取3 0=an n (0,k) 則3 13 0i 3 2= ak-n(an)i(cb) kc在i不等于0時(shí)不屬于L 與假設(shè)矛盾。則L(G)不是正則集(2) 假設(shè)該集合是正則集，對于足夠大的k取3 = akbk 令3 = 3

16、 1 3 0 3 2因?yàn)?| 3 0|0 |3 1 3 0| W k 存在 3 0使 3 1 3 0 3 2 L所以對于任意3 0只能取3 0=an n (0,k) 則3 13 0i3 2= ak-n(an)ibk在i不等于0時(shí)a與b的個(gè)數(shù)不同，不屬于該集合 與假設(shè)矛盾。則該集合不是正則集(3) 假設(shè)該集合是正則集，對于足夠大的k取3 = akcak令3 = 3 1 W 0 3 2因?yàn)?| 3 0|0 |3 1 3 o| W k 存在 3 0使 3 1 3 0 3 2 L所以對于任意3 0只能取3 0=an n (0,k)則3 13 0i3 2= ak-n(an)icak在i不等于0時(shí)c前后a

17、的個(gè)數(shù)不同，不屬于該集合 與假設(shè)矛盾。則該集合不是正則集(4)假設(shè)該集合是正則集，對于足夠大的k取33 = ak bakb令3 3 = 3 1 3 03 2因?yàn)?| 3。|0 |3 1 3 0| AA | a A 4 | b A 5AA3 A | bA 2 AAA A | aA 3 A , 將A,A6生成式代入Aa生成式得A f aAA2 I bAAA4AA5A | bA AAAAAA | aAA4AA | bAAA3 AAAA2 | bA 2 AAA AAAA2 | aA 3 AaAAA2 | bA 5A5AAA A A | bA2 A5AAAA AA | aAAA2 A5A2 | bAAA

18、 AAA2 AA | bA AAA A4AA AA | aA 3氏AA AA2 | bA 2 AA | b A 4 | aA 4 | b A 5AA4AA | bA 2 A5AAA4A5 | aA 4AA5 | bA 5AA AA4A5 | bA 2 A5AA3 AAA5 | aA3 AA6A | bAsAAAA A | bA AA5AAA2 A | aA4AA A | bAAA AAA2 A | bA A5A5A3 AAA2 A5 | aA AAA A | bA A5 | b A , 將A4,A7生成式代入 A生成式得A f aA5 | aA 4W | aA 4A AA | aA 5A*|

19、aA 収AA | aA 収AAA3 |b A5A5A4 | bA AAA | aA | bAAA A | bA AA5A3 A | aA A| bAAAA | bA AAAA | a A4A3 | b AAA A A | bA AAA A A | aA AA, 由此得出等價(jià)的 Greibach范式文法：G = ( S,D,D , a,b , P 1 , S ),其中生成式 P如下：A f A3A4 | A 2A5 ,A f AAA | b | A 3AAA2| bA 2,A b A5A| bA2AA5| a | bA5AA3| bA2民品 | aA3,A b ,A a ,A bAAsAAA |

20、 bA AAAAAA | aNA4A | bAAA A4A4A5 | bA AAA AAA | aA A4A4A5 | bAsAAAAe A | bA AAAAA A | aAAA A | bAAA AAAe A | bAe AAA AAAe A | aA A4AA2 A | bA A5 | b A , A b A5AA | bA 2 A5A5A41 a A 4 | b A 5A5A3 A | bA 2 A5A5A3 A | aA 3 A , A aAA2| bAAAAAsA| bA2 AAAAAfA| aAA4AA|bAAsA AAA5A | bA 2 AAAA AAAA | aA 3 A4

21、AAA2 | bA 5A5AAA A A | bA2 A5AA4AA AAA | aAAA2 A5A? | bAAA AA4A2 AA? | bA AAA A4AA2 AA | aA 3 AAA AAA | bA 2 AAA | bA 5A2 | aA 4 | b A 5AA4AA5 | bA 2 A5AAAA5 | aA 4AA5 | bA 5AA3 AA4A5 | bA 2 A5AA3 AAA5 | aA3 AAA | bAsAAA A5| bA2 AAAAA2 A | aA4A4A A |bAAsA AAA2 A | bA A5A5A3 AAA2 A | aA AAA A | bA A5

22、 | b A5 , A aA5 | aA 4A5A5 | aA 4A2 A5A5 | aA 5A3| aA 4AA5A3| aA aa A5AA3 |b A5A5A4 | bA AAA I aA4 | bAAA A4 | bA AAA A | aA A| bAAAA | bA 2 A5A5A4A3| a A 4 A3 |b A 5A5A3 A A3 | bA 2 A5AA3 A A3|aA? AAA .20.設(shè)文法G有如下得生成式：S aDD , D aS | bS | a ,構(gòu)造等價(jià)的下推自動(dòng)機(jī)解：根據(jù)P162-163的算法,構(gòu)造下推自動(dòng)機(jī) M,使M按文法G的最左推導(dǎo)方式工作.設(shè) M = (

23、Q,T, r , 3 ,q 0,Z0,F ),其中Q = q 0,qf ,T = a,b,r = a,b,D,S ,Z0 = S ,F = q f ,0,a ) ,3定義如下：0,bS ) , ( q3 ( q 0, & ,S ) = ( q3 ( q 0, & ,D ) = ( q3 ( q 0,a,a ) = ( q3 ( q 0, & , ) = ( q0, aDD ) ,0,aS ) , ( q0, ) ,f,) 21.給出產(chǎn)生語言L = a ibjckI i , j , k 0 且 i = j或者j = k 的上下文無關(guān)文法你給出的文法是否具有.二義性 ？為什么？解：G=(S A B

24、,C,D,E,a,b,c,P,S)P: S AD |EB, A aAb | & , BbBc| ,DcD | , E aE| 文法具有二義性。因?yàn)楫?dāng)句子3中a,b,c個(gè)數(shù)相同時(shí)，對于3存在兩個(gè)不同的最左（右）推導(dǎo)。如 abcL ,存在兩個(gè)不同的最左推導(dǎo) S : AD aAbD ab氐abcS abc及 S : EB : aEB : aB : abBc : abc。22.設(shè)下推自動(dòng)機(jī) M = ( q o,q i,a,b,Z o,X, S , q0, Z0,0 ),其中3 如下3 (q 0,b, Z o) = (q0, XZ。) ,3 (q 0,& , Z。)= (q0,&) ,A3 (qo,b,

25、 X) = (qo, XX) , S (q i,b, X) = (q1,& ),8 (qo,b, X) = (qi, X) ,3 (qi,a, Z o) = (q o, Z 0),試構(gòu)造文法G產(chǎn)生的語言L (G) = L(M).q i,Zo,q o,q i,Zo,q 1,解：在 G 中,N = qo,Zo,qo, qo,Zo,q|, qo,X,q。, q o,X,q |, q 1,X,q o, q 1,X,q 1 .S生成式有S f qo,Zo,qo,S f qo,Zo,q1,根據(jù) 8 (q o,b, Z o) = (qo, XZ o),則有q,Z,qo f bqo,X,qoq o,Z,qo,

26、 qo,Zo,qo f bqo,X,q 1 q i,Zo,q o, q o,Z o,qi f bqo,X,qoq o,Zo,q 1, q o,Z o,q1 f bqo,X,q 1 q 1,Zo,q | , 因?yàn)橛?8 (q o,b, X) = (qo, XX),則有q o,X,q o f bq o,X,q o q o,X,q o,q o, X,qof bqo,X,qiq1, X,qo,qo, X,q1fbqo,X,qoqo, X,q1,qo, X,q1f bqo,X,q1 q1, X,q1,因?yàn)橛?8 (q o,a, X) = (q1, X),則有qo,X,q o f aq 1,X,q o,q

27、o,X,q q f aq 1,X,q 1, 因?yàn)橛?8 (q 1,a, Z o) = (q o, Z o),則有q1,Z o,qo f aqo,Zo,qo,q1,Z o,q1 f aq o,Zo,q H ,因?yàn)橛?8 (q o, & , Z o) = (q o,& ),則有q o,Z o,qo f ,因?yàn)橛?8 (q1,b, X) = (q1,& ),則有q 1,X,q 1 fe利用算法1和算法2,消除無用符號后，得出文法 G產(chǎn)生的語言L(G)= n,t,p,s 其中 N = S,qo,Zo,qo,q 1,Zo,qo,q 1,X,q 1, q o,X,q 1 ,T = a,b , 生成式P如下

28、：S f q o,Z o,qo,q 0,Z o,qo f bqo,X,q 1 q 1,Zo,q o, q0, X,q 1 f bqo,X,q 1 q 1, X,q 1, qo,X,q 1 f aq 1,X,q 1,q1,Z o,qo f aqo,Zo,qo,q 0,Z 0,q0 fe ,q 0,Z o,qo fe .23.證明下列語言不是上下文無關(guān)語言： a H | m p時(shí),可取3 = a pbpcp,將3寫為 3=3 1 3 2 3 0 3 3 3 4 , 同時(shí)滿足| 3 2 3 0 3 3| W P3 2和3 3不可能同時(shí)分別包含a和C,因?yàn)樵谶@種情況下,有| 3 2 0 3|p； 如果

29、3 2和3 3都只包含a (b),即3 2303 3 = a j (b j ) (j p時(shí),可取3 k=a ( k p 且 k 工 1 ), 將3與為3 = 3 1 3 2 3 0 3 3 3 4 , 同時(shí)滿足| 3 2 3 0 3 3| W p , 且| 3 2 3 3|=j 1 ,則當(dāng) i=k+1 時(shí),| 3 1 3 2 3 0 33 4|=k+(i-1)*j=k+k*j= k*(1+j) ,k*(1+j)至少包含因子k且k工1 ,因此必定不是質(zhì)數(shù)，即3 13 2i 3 033 3 4不屬于L.這與假設(shè)矛盾，故L不是上下文無關(guān)語言.由a,b,c 組成的字符串且是含有 a,b,c 的個(gè)數(shù)相同

30、的所有字符串證明： 假設(shè)L是上下文無關(guān)語言，由泵浦引理，取常數(shù)p,當(dāng)3 L且| 3 | p時(shí),可取3 = a kbkck (k p),將 3 寫為 3 =3 1 3 23 03 33 4 ,同時(shí)滿足 | 3 23 03 3| W p3 2和3 3不可能同時(shí)分別包含a和c,因?yàn)樵谶@種情況下，有| 3 23 03 3|p； 如果3 2和3 3都只包含a (b或c),即3 2 3 0 3 3 = a (b 則當(dāng)i工1時(shí)，3 1 3 2 3 0 3 3 3 4中會(huì)出現(xiàn)a,b,c的個(gè)數(shù)不再相等； 如果3 2和3 3分別包含a和b (b和c) ,31 3丿3 03 3i 3沖會(huì)出現(xiàn)a,b的個(gè)數(shù)與c的不等；

31、這些與假設(shè)矛盾，故L不是上下文無關(guān)語言24. 設(shè)G是Chomsky范式文法，存在3 L (G)，求在邊緣為3的推導(dǎo)樹中，最長的路 徑長度與3的長度之間的關(guān)系.解：設(shè)邊緣為3的推導(dǎo)樹中，最長路徑長度為n,則它與3的長度之間的關(guān)系為 I 3 | W2n-1 .因?yàn)橛蒀homsky范式的定義可知，Chomsky范式文法的推導(dǎo)樹都是二叉樹，在最長路 徑長度為n的二叉推導(dǎo)樹中，滿二叉樹推出的句子長度最長,為2n-1,因此3的長度與 其推導(dǎo)樹的最長路徑長度 n的關(guān)系可以用上式表示.25. 設(shè)計(jì)PDA接受下列語言(注意：不要求為確定的) 0 m1n | m W n ;解：設(shè) PDA M = ( Q,T, r , S ,q0,Z0,F ),其中Q = q 0,q 1,q f ,T = 0,1,r = 0,1, z 0 ,F = q f ,S定義如下：S ( q 0, , Z 0) = ( q 1, Z 0 ) ,S ( q0,0, z 0)=: ( q0, 0Z0 ) ,S ( q0,0,0 ) = (q0, 00 ),S ( q0,1, z 0 )= ( qf, &),S ( q0,1,0 ) = (q1, &),S ( q1,1,0 ) = (q1, &),S ( q1, & , z 0 )= ( qf,& )S ( q1,1, Z 0 )= (