形式語言與自動機課后習題答案

1、形式語言與自動機課后作業(yè)答案第二章4找出右線性文法，能構成長度為 1 至 5 個字符且以字母為首的字符串。答：G=N,T,P,S其中 N=S,A,B,C,D T=x,y 其中 x 所有字母 y 所有的字符4 x Sf xAA f yA f yB4 y BfyCCfy CfyDDfy 6 構造上下文無關文法能夠產生L=3/a,b*且3中 a 的個數是 b 的兩倍答: G=N,T,P,S其中 N=S T=a,b P 如下：Sfaab Sfaba SfbaaSfaabS SfaaSbSfaSabSfSaabSfabaS SfabSaSfaSbaSfSabaSfbaaS SfbaSaSfbSaaSfS

2、baa7 找出由下列各組生成式產生的語言(起始符為S)SfSaS SfbSfaSb Sfc(3) Sfa SfaE EfaS答：(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)是正則集，自動機如下P 如下:(3) 是正則集先看 L 為包含子串 aba 的a,b*上的字符串集合 顯然這是正則集，可以寫出表達式和

3、畫出自動機。(略) 則不包含子串 aba 的a,b*上的字符串集合 L 是L的非。 根據正則集的性質，L 也是正則集。4對下列文法的生成式，找出其正則式(1)G=(SAB,C,D,a,b,c,d,P,S), 生成式 P 如下：SfaA SBAfabS AbBBfb BfcCCfD DfbBDfd(2)G=(SAB,C,D,a,b,c,d,P,S), 生成式 P 如下：SfaA SfBAfcC AfbBBfbB BfaCfD CfabBDfd答： (1) 由生成式得：S=aA+B A=abS+bB B=b+cC C=D D=d+bB 式化簡消去 CD 得到 B=b+c(d+bB)即 B=cbB+

4、cd+b =B=(cb)*(cd+b)將代入b bb b不是正則集，用泵浦引理可以證明，具體見 17 題(2)S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =S=(aab)*(ab+& )(cb)*(cd+b)(2) 由生成式得：S=aA+B A=bB+cCB=a+bB C=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+acaba+b*a5. 為下列正則集，構造右線性文法：(1)a,b*(2)以 abb 結尾的由 a 和 b

5、 組成的所有字符串的集合(3)以 b 為首后跟若干個 a 的字符串的集合(4)含有兩個相繼 a 和兩個相繼 b 的由 a 和 b 組成的所有字符串集合 答：(1)右線性文法G=(S,a,b,P,S)P: SfaS SfbS S(2)右線性文法 G=(S,a,b,P,S)P: SfaS SfbS Sfabb(3)此正則集為ba*右線性文法 G=(S,A,a,b,P,S)P: SfbA AfaA Af(4)此 正 則 集 為 a,b*aaa,b*bba,b*,a,b*bba,b*aaa,b*右 線 性 文 法G=(SAB,C,a,b,P,S)P: SfaS/bS/aaA/bbBAfaA/bA/bb

6、CBfaB/bB/aaCCfaC/bC/&7.設正則集為 a(ba)*(1)構造右線性文法找出(1)中文法的有限自動機答：(1)右線性文法 G=(S,A,a,b,P,S)P: SfaA AfbS Af&(2)自動機如下：(p2 是終結狀態(tài))9.對應圖(a) (b)的狀態(tài)轉換圖寫出正則式。(圖略)(1)由圖可矢廿 qo=aqo+bq1+a+&q1=aq2+bq1qo=aqo+bq+a=q1=abq1+bq1+aaqo+aa=(b+ab) q1+aaqo+aa=(b+ab) *( aaq0+aa)=q0=aqo+b(b+ab) *( aaqo+aa ) +a+ &=

7、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) qo=aq1+bq2+a+bq1=aqo+bq2+bqo=aq1+bqo+a=q1=aqo+baq1+bbqo+ba+b=(ba)*(aq0+bbqo+ba+b)=q2=aaqo+abq2+bqo+ab+a=(ab)*(aaq0+bq0+ ab+a)=qo=a(ba)*(a+bb) q0+ a(ba)*(ba+b)+b(ab)*(aa+b)q0+ b(ab)*(ab+a)+a+b=a(ba)

8、*(a+bb) +b(ab)*(aa+b)* (a(ba)*(ba+b)+ b(ab)*(ab+a)+a+b)10.設字母表 T=a,b,找出接受下列語言的 DFA(1)含有 3 個連續(xù) b 的所有字符串集合(2)以 aa 為首的所有字符串集合(3)以 aa 結尾的所有字符串集合答：(1) M=(qo,qiq2,q3,a,b, o ,qo,q3),其中如下:abqoqoq1q1qoq2q2qoq3q3q3q3(2) M=(qo,qq ,a,b,o,qo,q2),其中o如下:abqoq1q1q2q2q2q2(3) M=(qo,qiq2,a,b,o,qo,q2),其中o如下:abq。q1q。q1q

9、2q。q2q2qo14 構造 DFA Mi等價于 NFA M, NFA M 如下：(1)M=(qo,q1q2,q3,a,b,o,qo,q3),其中o如下：o(qo,a)=qo,q1o(qo,b)=qoo(q1,a)=q2o(q1,b)= q2o(q2,a)=q3o(q2,b)=o(q3,a)=q3o(q3,b)= q3(2)M=(qo,q1q2,q3,a,b,o,qo, q1,q2),其中o如下：o(qo,a)=q1,q2o(qo,b)=q1o(q1,a)=q2o(q1,b)= q14o(q2,a)=q3o(q2,b)= qoo(q3,a)= o(q3,b)= qo答：(1)DFA M=Q,

10、a,b,o1, qo, qo,q1,q3,qo,q2,q3,qo, q1,q2,q3其中 Q =qo,qo,q1,qo,q1,q2,qo,q2,qo,q1,q2,q3,qo,q1, q3,qo,q2,q3, qo,q3o1滿足abqoqo,q1qoqo,q1qo,q1,q2qo,q2q0,q1,q2q0,q1, q2,q3q0,q2q0,q2q0,q1, q3q0q0,q1, q2加q0,q1, q2皿q0,q2, q3q0,q1, q3q0,q1, q2心q0,q2, q3q0,q2, q3q0,q1, q3q0,q3q0,q3q0,q1, q3q0,q3(2) DFAM=Qi,a,b,1,

11、 q。,qi,q3,qi,q3,qo,qi,q2,qi,q2 ,qi,q2,q3,q2,q3其中 Q =qo,qi,q3, qi,q2, qo,qi,q2,qi,q2,q3, qi,q2,q3,q2,q31滿足abq0q1,q3q1q1,q3q2q0,q1,q2q1q2q1,q2q2q3q0q0,q1,q2q1,q2,q3q0,q1,q2q1,q2q2,q3q0,q1,q2q3q0q1,q2,q3q2,q3q0,q1,q2q2,q3q3q015. 15.對下面矩陣表示的& -NFAabcP（起始狀態(tài)）0pqrqPqr0r（終止狀態(tài)）qr0p(1) 給出該自動機接收的所有長度為3 的串(

12、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 M=(p,q,r,a,b,c,1,p,r)1(p,a)=(p,a)= -closure(p, ),a)=p1(P,b)=(p,b

13、)= -closure(p, ),b)=p,q1(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,r1(q,c)=(q,c)= -closure(q, ),c)=p,q,r1(r,a)=(r,a)= -closure(r, ),a)=p,q,r1(r,b)=(r,b)= -closure(r, ),b)=p,q,r1(r,c)=(r,c)= -closure(r, ),c)=p,q,r圖示如下： (r 為終止狀態(tài)）16.設 NFA M=(

14、qo,qi,a,b, o ,qo,qi),其中廳如下： (qo,a)=qo,q1 o (qo,b)=q1o (qi,a)= o (qi,b)= q0, q1構造相應的 DFA M1,并進行化簡答：構造一個相應的 DFA M1=Q1, a,b,o1, qo, q1 , qo,q(|其中 Q =q0 , q1, qo,q1o1滿足abq0q0,q1q1q1q0,q1q0,q1q0,q1q0,q1由于該 DFA 已是最簡，故不用化簡17.使用泵浦引理，證明下列集合不是正則集：(1)由文法 G 的生成式 S- aSbS/c 產生的語言 L(G)(2)3/a,b*且3有相同個數的 a 和 bk k(3)

15、aca/k 1(4)33/a,b*證明：(1)在 L(G)中，a 的個數與 b 的個數相等 假設 L(G)是正則集，對于足夠大的 k 取3= ak(cb)kc 令3=313032因為|3o|O |313o|Wk 存在30使313032 L所以對于任意30只能取30=ann (0,k) 則313J32= ak-n(an)i(cb)kc 在 i 不等于 0 時不屬于 L 與假設矛盾。則 L(G)不是正則集(2)假設該集合是正則集，對于足夠大的k 取3= akbk令3=313032因為|3o|O |313o|Wk 存在30使313032 L所以對于任意30只能取30=ann (0,k) 則313 0 32= ak-n(an)ibk在 i 不等于 0 時 a 與 b 的個數不同，不屬于該集合 與假設矛盾。則該集合不是正則集(3)假設該集合是正則集，對于足夠大的k 取3= akcak令3=3130CO2因為|3o|O |313o|Wk 存在30使313032 L所以對于任意3o只能取3o=ann (0,k)則313oi32= ak-n(an)icak在 i 不等于 0 時 c 前后 a 的個數不同，不屬于該集合 與假設矛盾。則該集合不是正則集(4)假設該集合是正則集，對于足夠大的k 取33= akbakb令3 3=313032因為