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

1、形式语言与自动机课后习题答案第二章4. 找出右线性文法，能构成长度为1至5个字符11以字母为首的字符串。答：G=NXPZS其中N二SABCDT二x，y其中x曰所有字母丫曰所有的字符 P如下:Sx SxA Ay A-*yBBy ByC Cy CyD Dy6. 构造上下文无关文法能够产生L=3/3 Wa,b*且3中a的个数是b的两倍答:G=N,T,P,S其中N珂ST=a,bP如下：S-*aab S-*aba S-*baaS-*aabS S-*aaSb SaSab SSaabS-abaS S-*abSa SaSba SSabaS-*baaS S-*baSa SbSaa SSbaa7. 找出由下列各组

2、生成式产生的语言(起始符为S)(1) S-SaS S-b(2) S-*aSb Sc/(4) Sa SaE EaS答:(1) b(ab)n/nO或者 L=(ba)nb/n0(2) L=ancbn/n0(3) L=a2n+1/n0第三章1.下列集合是否为正则集，若是正则集写出其正则式。(1) 含有偶数个a和奇数个b的a,b*上的字符串集合(2) 含有相同个数a和b的字符串集合(3) 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=

3、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*a5. 为下列正则集，构造右线性文法：a,b*(2) 以abb结尾的由a和b组成的所有字符串的集合(3) 以b为首后跟若干个a的字符串的集合 含有两个相继a和两个相继b的由a和b组成的所有字符串集合答:(1)右线性文法 G=(S,a,b,P,S)P:SaS S-bS S-(2) 右线性文法G=(,a,b,P,S)P: S-*aS S-*bS Sabb(3) 此正则集为ba*右线性文法 G=(S,A,a

4、,b,P,S)P:SbA AaA A(4) 此正则集为a/b*aaa,b*bba,b*/ a,b*bba,b*aaa,b* 右线性文法 G=(S,A,B,C,a,b,P,S)P: S-aS/bS/aaA/bbBAaA/bA/bbCBf aB/bB/aaCC-aC/bC/ e7.设正则集为a(ba)*(1) 构造右线性文法(2) O)找出(1)中文法的有限口 b动机答:(1)右线性文法 G=(S,A,a,b,P,S)P:SaA AbS A(2) 口动机如下：9对应图(a) (b)的状态转换图写出正则式。(图略) (1) 由图可知 qo二aqo+bqi+a+ qi=aq2+bqi qo=aqo+b

5、qi+a=qi=abqi+bqi+aaq0+aa=(b+ab) qx+aaqo+aa=(b+ab) *( aaqo+aa)=qo=aq0+b(b+ab) *( aaq0+aa ) +a+ =qo(a+b (b+ab) *aa)+ b(b+ab) *aa+a+ =(a+b (b+ab) *aa) *(b+ab) *aa+a+ )=(a+b (b+ab) *aa) *(4) q0=aq1+bq2+a+bqi=aqo+bq2+bqo=aqi+bqo+a=q1=aq0+baq1+bbq0+ba+b=(ba)*(aq0 +bbq0+ba+b)=q2=aaqo+abq2+bqo+ab+a=(ab)*(aa

6、q0 +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,bz找岀接受下列语言的DFA：（1）含有3个连续b的所有字符串集合（2）以aa为首的所有字符串集合（3）以aa结尾的所有字符串集合答:（1） M=（q0/qio .qojqj）,其中 如下:abq。qoqiqiqoq2q2q。q3Qb(2) M=(q0/qi q2 JJa.b, o 皿你),其

7、中。如下:abqoq：GqiC2GQzqz(3) M=(q0,qi q2 za,b,。皿件)，其中。如下:abqoq：qoQiC12q。q2C2q。14构造DFA IVk等价于NFA M, NFA M如下：(1) M=(q0/qi qqsLfa, o 亦),其中。如下：0 (q0,a)=q0/qi。(q0/b)=q00 (qi,a)=q2 o (qi/b)= q2o (q2,a)=q3 o (q2/b)= e0 (q3,a)=q3 o (q3/b)= q3(2) M=(qoq q*屜b, o，qo， qie)，其中。如下：o (q0,a)=qlzq2 o (q,b)二qo (qba)=q2 o

8、 (qlzb)= qizq20 (q2,a)=q3 o (q2,b)= q。(0(Q3,a)= e a (q3/b)= q。答:(1) DFAa”b，o .(Qo/ qo/Qi/Q3 qo/h/b，Qo； 口丄心心其中 Ch qojzlqozqi, qo,qi,q2L qoqaLt qo,q qoi, qjqo,q2, qJqoqs S满足abqo(qo,qjQoeqo,qiQo/Qi/Qzqo,q2qo,qi,q2qo,qi, 2,3qo.qzqo,q2Qo,qi/ Q3)qoQo/Ad Q2/Q3qo,qi, 2,3Q0/Q2/ Q3Qo,qi/ Q3)qo,qi, 2,3q%” Q3Qo

9、,q2/ Q3)Qo,qi/ Q3)Qo.qJqo,q3Qo,qi/ Q3)qo,qj(2) DFA M讦CL a,b, o D q(J， q qq血诃“亠环心 其中 Qi 二qoqi,q儿qj/qqoqeHqsqJ/qd qi.qqjjqqjS满足abqo(qi/QsqqgQjqo,qq2gQjqgq2qjqo qj Qo/Qi5满足abqo(Qo,qi$qdqJ巾qo,qjqo,qi(qo,qjqo,qi由于该DFA己是最简，故不用化简17. 使用泵浦引理，证明下列集合不是正则集：(1) 0 | 3丄3。| Wk 存在 3。使 G)1G)oiG)2eL所以对于任意3。只能取3 o=an n

10、 G(0,k)则3132= akn(an)(cb)kc在i不等于0时不属LA与假设矛盾。则L(G)不是正则集(2) 假设该集合是正则集，对于足够大的k取3=a5k令 3 = Gi3o32因为 | 3。|0 | 3丄3。| Wk 存在 使(UWoigWL所以对于任意3。只能取o0=an n G(O,k)则G)1woiQ2= akn(an)ibk在i不等于0时a与b的个数不同，不属于该集合 与假设矛盾。则该集合不是正则集(3) 假设该集合是正则集，对于足够大的k取3=aSak令3=3i332【人I为| 3 | 0 | 3丄3 | W k存在3 使3丄3 * 3 2 G LA所以对于任意3。只能取3

11、 0=an n G(O,k)则G)1G)0,G)2= ak-n(anjicak在j不等于0时C前后a的个数不同,不属于该集合 与假设矛盾。则该集合不是正则集(4) 假设该集合是正则集，对于足够大的k取0G)= aWb令 3 Ci) = G)1a)0(i 2因为 I 3。|0 I 3丄3。| Wk 存在 3。使(UWoigWL所以对于任意3。只能取o0=an n G(O,k)则w1G)oii)2= afaba 在i不等于0时不满足3 3的形式,不属丁该集合与假设矛盾。则该集合不是正则集18 构造米兰机和摩尔机对Ta,b*的字符串，如果输入以bab结尾，则输出1；如果输入以bba结尾，则输 出2；

12、否则输出3。答：米兰机：说明状态qaa表示到这个状态时，输入的字符串是以aa结尾。其他同理。b/3摩尔机，状态说明同米兰机。A3A4A4 I b I A3A4A4A2/ I bA zA3 b A5A5 I bAzsAs I a | bAsAsA3/ | bA2/AsAsA3，| aA3*,A4 b,A5 a,Ae f bAsAsAoAoAs | b A2? As As A4A4 As | qAaAaAs | bAsAsAsAAoAs | 匕人2人5人5人3虫山亦5 | a A,氏 a A山5 | bAsAsAaAAAzAs I bAzsAsAdAaAzAs |As bA5A5A3/A4A4A2

13、,A5 | bAjAsAsA/AAAA | aA3/A4A4A2/A5 | bA/A5 | bA5/A7 * b A5A5A4 I bA/AsAsAa I a Aa | bAsAsAsAa | bA2* AsAsA3fA4 | aA3/A4 /Af - a； I bAsAs/UUAj |3/4443 aA4A4A5A2/ |bA5A5A3/A4A4A5A2/ |I aA3/A4A4A5A2/ | 泳444皿足 A/ |bA2/AsAsA4A4A2，A5A2， |a A4A4 A2? As A2?| bAsA5A3/A4A4A2，AsA2/ |匕人“皿工皿“九 I aA3/A4A4A2,A5A2

14、/ | bA/AsA/ | bA5A2# | aA4 | b A5A5A4A4A5 I 匕人2浪5人5人4人亦5 I aAiiA4A5 | 匕人5人5人3上亦亦5 | BA； 444$I SAsAaAoAs IbAsAsA4A4A2，A5 | bAzsAsAAAoAzs | bAaAaAqAs | bAsAsA3，A4A4A2/A5 | bAzAsAsA/AoAoAzAs | aA/AA/As | bA/As | b A5/A3 3A5 I aAAsAj I aA4A2 A5A5 | aAsAj | aA4A5A5A3 | aA4A2 A5A5A3 | b A5A5A4 | bAfAsAA I

15、 aA4 | bAsAsAj% | bA/AsAsA/Aa | aAAa | bAsAAA, I hd；Z4M I a A4 A3 I b AsAsAsAa A3 I b A2# A5 As As* A4 A3 | aA3/A4A3/.20. 设文法G有如下得生成式:S aDD, D -*aS | bS | a ,构造等价的下推口动机.解：根据P162-163的算法，构造下推口动机M,使M按文法G的最左推导方式工作.设 M = (QT,，6 ,q,Zo,F ),其中Q = qogf,T = a,b,r =a,b,D,S,Z0 = S,F 十 f,S定义如下：$(q。，,S) = (q, aDD

16、),$ ( q。， ,D ) = ( q,aS ), ( q,bS ), ( q,a ),$(q,a,a) = (q。, ),$ ( q。, , ) = ( q” )21. 给出产生语言L = aWn i,j,k$O且i=j或者j = k的上下文无关文法.你给出 的文法是否具有二义性为什么解：G=(S,A,B,C,D,E,a,b,c, P, S)P： S AD |EB, A f aAb | , B -*bBc | , D cD | , E aE | 文法具有二义性。因为当句子3中a,b,c个数相同时，对丁存在两个不同的最左(右)推导。女口 abc L,存在两个不同的最左推导S AD aAbD

17、abD abcC abc及 S EB aEB aB abBc abc。22. Bn 设下推自动机 M = (q,qi,a,b,Z,X, 8 , q。, Z0/ )，其中 $ 如下：5 (qo,b, Zo) = (qo, XZo), 8 (q0/ , Z。) = (q。, e ) ,A* (q,b, X) = (q, XX), $ (q,X) = (q】， ),(qo,b, X) = (q X),$ (q】,a, Zo) = (qo, Zo),试构造文法G产生的语言L(G) = L(M).解：在 G 中,N = q%qo, q。厶q込qoXq。, qXq込qZqo, qsZo,q込qiXqo,

18、qi/X,qi(1)S生成式有SS fqo,Zo,q，根据 8 (q0/b, Zo) = (qo, XZo)测有qo/Zo,Qo bfqo/Xo Qo/Zo,Qo / qo,Zo,qo ibqoXqi qZogo / qo/Zo/Qi bqoXqo qchZqJ / qcZcqi blqozXi qZozqJ , 因为有 8 (qo,b, X) = (qOz XX),则有qo,X,qo bq0,Xzq0 q0,X,q0, qo, Xzq0 bfqoXqi qi, X,q0, qo, KqJ bqo,X,qoq。,qo, X?qi btqozMi qi, X,qi, 因为有 5 (q0/az X

19、) = (qb X)贝有qozKqo alqiXqo,(qozqj faq“X,qi,因为有 6 (q】,a, Zo) = (q。, Zo),则有qZo，qd aq%qo /qi/Zo,qi aqo,Zo,qJ /因为有 $ (qo, , Z。) = (q, )，则有qo,ZO/qo /因为有 8 (qlzb, X) = (qlz )，则有q】Xq一 利用算法1和算法乙消除无用符号后，得出文法G产生的语言L(G) = NXP.S 其中 N = S/qo/ZO/qo/qi,Zo/qo4qi,X/qJ/ qqj ,T = azb 住成式 P 如下: S qoqo,qo,ZO/qo -*bq0/X,

20、qJ qiqj /qo, X,qJ -*bq0XqJ qi, XzqJ zqo,X,qi aqiXqi,Qi/Zo,qo aqo,Zo,qo /qo,Zo,qo /qo,Z0/q0 24 证明下列语言不是上下文无关语言:(1) 证明：anbncm | mWn;假设L是上下文无关语言，由泵浦引理，取常数p,当3 WL J1I 3 &p时，可取3 = aPbPCP,将 3 写为 GJ = G)1G)2(D0G3W4,同时满足 1 3 2 3()3 31 Wp(1) 5和5不可能同时分别包含a和C,因为在这种情况下，有| 3 23o(*)3|p；(2) 如果32和33都只包含a (b),即323。3

21、3 = )(jWp),则当iHl时,3) 33033匚34中会出现a的个数与b的个数不等；如果32和33都只包含C，即323。33 = CJ (jWp),当i大于1时,3】3 J 3 3 J 3 中会出现C的个数大于a的个数(b的个数)；(3) 如果5和I分别包含a和b (b和c),当i=0时*)x ww0w(X)4中会出现 a, b的个数小J： c的个数(或a,b个数不等)这些与假设矛盾，故L不是上下文无关语言.(2)证明： ak | k是质数;假设L是上下文无关语言，由泵浦引理，取常数p,当3WLlL|3|$p时,可取3k (kNp 且 kHl ),将 3 写为 3 = 3同时满 | 2

22、0 W 3 | P ,且1| co 2 w 31 = j1，则当 i=k+l 时,| w 1 2 ow 3 41 =k+(i-l)*j=k+k*j= k*(l+j) zk*(l+j) 至少包含因子k且kHl,因此必定不是质数，即332匕033检4不属于L. 这与假设矛盾，故L不是上下文无关语言.(3) 证明：由a,b,c组成的字符串11是含有a,b,c的个数相冋的所有字符串. 假设L是上下文无关语言，由泵浦引理，取常数p,当3 W L 11|时，可取3 = akbkCk(kP),将 3 写为 G) = G)1GJ2G)oG)3G4/同时满足 I (O2G)oG)3|p(1) 和5不可能同时分别

23、包含a和C,因为在这种情况下，有I W2P；(2) 如果 5 和 33 都只包含 a (b 或 c)zEP w2G)0G)3 = aj (H 或 ci)(jWp),则当 iH 1时，3 13 J53 J34中会出现a,b,c的个数不再相等；(3) 如果5和33分别包含a和b (b和c), wxw2jw0w3jw4中会出现a,b的个 数与c的不等；这些与假设矛盾，故L不是上下文无关语言.25设G是Chomsky范式文法，存在3 W L(G),求在边缘为的推导树中撮长的路径 长度与3的长度之间的关系.解：设边缘为3的推导树中，最长路径长度为n,则它与3的长度之间的关系为|3|W 2叫因为由Chom

24、sky范式的定义可知,Chomsky范式文法的推导树都是二义树，在最长路 径长度为n的二叉推导树中，满二叉树推出的句子长度最长，为2,因此的长度与 其推导树的最长路径长度n的关系可以用上式表示.26.设计PDA接受下列语言(注意:不耍求为确定的)(1) 0mln| mn;解：设 PDA M = (QT,，6 ,q,Zo,F )，其中Q = qo 皿 qf /T = O,1,r =o,i,z。,F = qf,8定义如下：(qo, e ,Zo) = (qi,Zo), (q,0, Zo) = ( q。, 0Zo) /6 ( qo,0,0 ) = ( qo, 00), (q,l,Zo) = (qf, ), $ ( q,l, 0 ) = ( ),8(qiX0) = (qi/e ), (q】,Z) = (qf, ) 6(qi,l,Zo) = (qf, ) 8(qd, ) = (qf, )(2) 0mln| mn;解:设 PDA M = (QT,，6 ,q,Zo,F )，其中Q = qo,q】,qf,T = 0,l,r =o,i,z