形式语言与自动机王柏杨娟编著课后习题答案

1、专业资料形式语言与自动机课后习题答案第二章4找出右线性文法，能构成长度为 1至5个字符且以字母为首的字符串。答：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 构造上下文无关文法能够产生L= 3 / 3 a,b*且3中a的个数是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 找出由下列各组生成式产生的语言(起始符为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) 含有偶数个a和奇数个b的a,b*上的字符串集合(2) 含有相同个数a和b的字符串集合(3) 不含子串aba的a,b*上的字符串集合答：(1)是正则集，自动机如下b bb b 不是正则集，用泵浦引理

3、可以证明，具体见 17题(2)(3)是正则集先看L 为包含子串aba的a,b*上的字符串集合 显然这是正则集，可以写出表达式和画出自动机。(略) 则不包含子串aba的a,b*上的字符串集合L是L 根据正则集的性质，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.为下列正则集，构造右线性文法：(1) a,b*的非& )(

5、cb)*(cd+b) 以abb结尾的由a和b组成的所有字符串的集合(3) 以b为首后跟若干个a的字符串的集合(4) 含有两个相继a和两个相继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.设正则集为a(ba)*(1) 构造右线性文法找出(1)中文法的有限自b动机答：(1)右线性文法 G=(S,A,a,b,P,S)P: S f aA A f bS A f&(2) 自动机如下：(p2是终结状态)9. 对应图(a) (b)的状态转换图写出正则式。(图略)(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. 设字母表T=a,b,找出接受下列语言的 DFA(1) 含有3个连续b的所有字符串集合(2) 以aa为首的所有字符串集合(3) 以aa结尾的所有字符串集合答：(1) M=(q0,q 1 q 2,q 3,a,b, o ,q0,q 3),其中如下:14构造DFA M1等价于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（起始状态）0pqrqPqr0r（终

12、止状态）qr0p(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 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为终止状态）16. 设 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构造相应的DFA M1,并进行化简答：构造一个相应的 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产生的语言

15、L(G)(2) 3 /a,b*且3有相同个数的 a和bk k(3) a ca /k 1(4) 33 / 3 a,b*证明：(1)在L(G)中，a的个数与b的个数相等 假设L(G)是正则集，对于足够大的k取3 = ak (cb) kc令3 = 3 1 3 0 3 2因为 | 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时不属于L 与假设矛盾。则L(G)不是正则集(2) 假设该集合是正则集，对于足够大的k取3 = akbk 令3 = 3

16、 1 3 0 3 2因为 | 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时a与b的个数不同，不属于该集合 与假设矛盾。则该集合不是正则集(3) 假设该集合是正则集，对于足够大的k取3 = akcak令3 = 3 1 W 0 3 2因为 | 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时c前后a

17、的个数不同，不属于该集合 与假设矛盾。则该集合不是正则集(4)假设该集合是正则集，对于足够大的k取33 = ak bakb令3 3 = 3 1 3 03 2因为 | 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, 由此得出等价的 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.设文法G有如下得生成式：S aDD , D aS | bS | a ,构造等价的下推自动机解：根据P162-163的算法,构造下推自动机 M,使M按文法G的最左推导方式工作.设 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.给出产生语言L = a ibjckI i , j , k 0 且 i = j或者j = k 的上下文无关文法你给出的文法是否具有.二义性 ？为什么？解：G=(S A B

24、,C,D,E,a,b,c,P,S)P: S AD |EB, A aAb | & , BbBc| ,DcD | , E aE| 文法具有二义性。因为当句子3中a,b,c个数相同时，对于3存在两个不同的最左（右）推导。如 abcL ,存在两个不同的最左推导 S : AD aAbD ab氐abcS abc及 S : EB : aEB : aB : abBc : abc。22.设下推自动机 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产生的语言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,根据 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 | , 因为有 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,因为有 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, 因为有 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 ,因为有 8 (q o, & , Z o) = (q o,& ),则有q o,Z o,qo f ,因为有 8 (q1,b, X) = (q1,& ),则有q 1,X,q 1 fe利用算法1和算法2,消除无用符号后，得出文法 G产生的语言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.证明下列语言不是上下文无关语言： a H | m p时,可取3 = a pbpcp,将3写为 3=3 1 3 2 3 0 3 3 3 4 , 同时满足| 3 2 3 0 3 3| W P3 2和3 3不可能同时分别包含a和C,因为在这种情况下,有| 3 2 0 3|p； 如果

29、3 2和3 3都只包含a (b),即3 2303 3 = a j (b j ) (j p时,可取3 k=a ( k p 且 k 工 1 ), 将3与为3 = 3 1 3 2 3 0 3 3 3 4 , 同时满足| 3 2 3 0 3 3| W p , 且| 3 2 3 3|=j 1 ,则当 i=k+1 时,| 3 1 3 2 3 0 33 4|=k+(i-1)*j=k+k*j= k*(1+j) ,k*(1+j)至少包含因子k且k工1 ,因此必定不是质数，即3 13 2i 3 033 3 4不属于L.这与假设矛盾，故L不是上下文无关语言.由a,b,c 组成的字符串且是含有 a,b,c 的个数相同

30、的所有字符串证明： 假设L是上下文无关语言，由泵浦引理，取常数p,当3 L且| 3 | p时,可取3 = a kbkck (k p),将 3 写为 3 =3 1 3 23 03 33 4 ,同时满足 | 3 23 03 3| W p3 2和3 3不可能同时分别包含a和c,因为在这种情况下，有| 3 23 03 3|p； 如果3 2和3 3都只包含a (b或c),即3 2 3 0 3 3 = a (b 则当i工1时，3 1 3 2 3 0 3 3 3 4中会出现a,b,c的个数不再相等； 如果3 2和3 3分别包含a和b (b和c) ,31 3丿3 03 3i 3冲会出现a,b的个数与c的不等；

31、这些与假设矛盾，故L不是上下文无关语言24. 设G是Chomsky范式文法，存在3 L (G)，求在边缘为3的推导树中，最长的路 径长度与3的长度之间的关系.解：设边缘为3的推导树中，最长路径长度为n,则它与3的长度之间的关系为 I 3 | W2n-1 .因为由Chomsky范式的定义可知，Chomsky范式文法的推导树都是二叉树，在最长路 径长度为n的二叉推导树中，满二叉树推出的句子长度最长,为2n-1,因此3的长度与 其推导树的最长路径长度 n的关系可以用上式表示.25. 设计PDA接受下列语言(注意：不要求为确定的) 0 m1n | m W n ;解：设 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 )= (