《形式语言与自动机》(王柏、杨娟编著)北邮出版社-课后习题答案

1、AW*第二章4找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。答：G=N,T,P,S其中N=S,A,B,C,DT=x,y其中x=所有字母y=所有的字符P如下:SxSxAAyAyBByByCCyCyDDy6构造上下文无关文法能够产生L=wwea,b*且3中的个数是的两倍答:G=N,T,P,S其中N=ST=a,bP如下：SaabSabaSbaaSaabSSaaSbSaSabSSaabSabaSSabSaSaSbaSSabaSbaaSSbaSaSbSaaSSbaa7.找出由下列各组生成式产生的语言(起始符为S)SSaSSSaSbcSSaSaEaES答：b(ab)n/n20或者L=(ba

2、)nb/n20L=ancbn/n20L=a2n+1第三章1.下列集合是否为正则集，牡曰若是正则集写出其正则式。含有偶数个a和奇数个b的a,b*上的字符串集合含有相同个数a和b的字符串集合不含子串aba的a,b*上的字符串集合答：(1)是正则集，自动机如下bbbb不是正则集，用泵浦引理可以证明，具体见17题(2)。是正则集先看L为包含子串aba的a,b*上的字符串集合显然这是正则集，可以写出表达式和画出自动机。(略)则不包含子串aba的a,b*上的字符串集合L是L的非。根据正则集的性质，L也是正则集。4对下列文法的生成式，找出其正则式G=(S,A,B,C,D,a,bc,d,P,S),生成式P如下

3、:SaASBAabSAbBBbBcCCDDbBDdG=(S,A,B,C,D,a,bc,d,P,S),生成式P如下:SaASBAcCAbBBbBBaCDCabBDd答:(1)由生成式得:S=aA+B式化简消去，得到*U*da+)a)*即*将代入S=aabS+*acbd+cb)*(2)由生成式得:S=aA+B由得*将代入C=d*+aa=b将代入A+=ab+c(+ad将代入S=+a(+bc(5.为下列正则集，构造右线性文法:a,b*以abb结尾的由a和b组成的所有字符串的集合以b为首后跟若干个a的字符串的集合含有两个相继a和两个相继b的由a和b组成的所有字符串集合答：(1)右线性文法G=(S,a,b

4、,P,S)P:SaSSbSS(2)右线性文法G=(S,a,b,P,S)P:SaSSbSSabb此正则集为*右线性文法G=(S,A,a,b,P,S)P:SbAAaAA此正则集为a,b*aaa,b*bba,b*,a,b*bba,b*aaa,b*右线性文法G=(S,A,B,C,a,b,P,S)P:SaS/bS/aaA/bbBAaA/bA/bbCBaB/bB/aaCCaC/bC/7.设正则集为a(ba*)构造右线性文法找出(1)中文法的有限自b动机答：(1)右线性文法G=(S,A,a,b,P,S)P:SaAAbSA(2)自动机如下：(p2是终结状态)9对应图(a)(b)的状态转换图写出正则式。(图略)

5、(1)由图可知q0=aq0+bqi+a+q1=aq2+bq1q0=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)*q0=aq1+bq2+a+bq1=aq0+bq2+bq0=aq1+bq0+a=q1=aq0+baq1+bbq0+ba+b=(ba)*(aq0+bbq0+ba+b)=q2=aaq0+abq2+bq0+a

6、b+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结尾的所有字符串集合14构造DFAM1等价于NFAM,NFAM如下：M=(q0,qiq2zq3,a,bzZ弘汕)，其中z如下：z0间=20耳1z。力尸凡z(q1,a)=q2z(q1

7、,b)=q2z沪尸汕z/)=ez(q3,a)=q3z(q3,b)=q3M=(q0,q1q2zq3,a,bzZ,q0,q1,q2),其中z如下：z(q0,a)=q1,q2z(q0,b)=q1z(q1,a)=q2z(q1,b)=口仏z(q2,a)=q3z(q2,b)=qz(q3,a)=ez(q3,b)=q0答：(1)dfam1=q1,a,b,z“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,q3z满足abqqq。qqq0,q1,q2q。qqJqqq。q。qJ

8、q。q。qqJq。qqJq。qq0,q1,q3q0,q1,q2，q3q。，q3q。qJq。qJqqjqo，qjq。qJqqjdfam1=q1,a,b,i，q0,qj/qj,q1,q3,q0,q1,q2,q1,q2,q1,q2,q3,q2,q3其中Qi=qo,qizq3,口丄皿qoqiqMqiqMqJ，qiqqMqyqJ满足abq。qqjqq1,q3qqqjqjq口1耳2qjqjq。4。角耳2口1耳2耳34内耳2q1,q2MJqqqjeq。q1,q2,q3q2，q3qqjMJqjq。15.15.对下面矩阵表示的abcp（起始状态）申PqrqPqr申r（终止状态）qr申P给出该自动机接收的所有长度

9、为3的串将此转换为没有的答：(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因为-c则设不含的(p,q,r,a,b,c,1,P,r)(P,a)=(P,a)=(p,(P,b)=(P,b)=(p,(P,c)=(P,c)=(p,(q,a)=(q,a)=(q,(q,b)=(q,b)=(q,(q,c)=(q,c)=(q,)(r,a)=(r,a)=-(r,)(r,b)=(r,b)=(r,)(r,c)=(r,c)=-(r,)图示如下：（r为

10、终止状态）(2)-NFA：M=(p,q,r,a,b,c,p,r)其中如表格所示。b,ca,b,ca,b,ca,b,ca,b,c16设NFAM=(q0,q,a,b,q0,qj),其中如下：(qo,a)=qo,q1(qo,b)=qi(q1,a)=e(q1,b)=q。，q1构造相应的DFAM,并进行化简答：构造一个相应的DFAM1=Q1,a,b,1,q0,q1，q0,q1其中Q1=q0,q1,q0,q1满足abqj咖由于该DFA已是最简,故不用化简17.使用泵浦引理,证明下列集合不是正则集：由文法G的生成式S-aSbS/c产生的语言L(G)wcoea,b*且3有相同个数的和2oo/oea,b*证明：

11、(1)在L(G)中，a的个数与b的个数相等假设L(G)是正则集，对于足够大的k取o令owoo因为wwoW存在o使owwe所以对于任意o只能取oe则owo-在不等于时不属于与假设矛盾。则L(G)不是正则集假设该集合是正则集，对于足够大的k取o令owoo因为ooo存在o使oooe所以对于任意o只能取oe则ooo-在不等于时与的个数不同，不属于该集合与假设矛盾。则该集合不是正则集假设该集合是正则集，对于足够大的k取o令oooo因为ooo存在o使oooe所以对于任意3只能取3匕则333-在不等于时前后的个数不同，不属于该集合与假设矛盾。则该集合不是正则集（4）假设该集合是正则集，对于足够大的k取33=

12、kabkab令33=333因为333第四章10.把下列文法变换为无生成式、无单生成式和没有无用符号的等价文法：S-A】|、2,A】|A4,、2-A、IA5，A3-S|b|,A4-S|a,A5-S|d|解由算法3,变换为无生成式：N=S,A1,A2,A3,A4,A5G=(S,S,Ai，A2,A3,A4,A5,a,b,d,P1,S1)，其中生成式P1如下：S1-|S,S-A】|A2,A1-A3IA4,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,A

13、4,A5,运用算法4,则P1变为：S1a|b|d|,S-a|b|d,A1a|b|d,A2a|b|d,A3a|b|d,A4a|b|d,Aa|b|d5由算法1和算法2,消除无用符号,得到符合题目要求的等价文法：G1=(S1,a,b,d,P1,S1)其中生成式P1为：S1a|b|d|.11.设2型文法G=(S,A,B,C,D,EF,a,b,c,P,S),其中P：SASB|;AaAS|a;BSBS|A|bb试将G变换为无生成式,无单生成式,没有无用符号的文法,再将其转换为Chomsky范式.解:由算法3,变换为无生成式：N=S由Sasb得出SasbIAB,由AaAS得出AaAS|aA,由BSBS得出B

14、SBS|SB|BS|B,由SUN得出S1|S,因此无的等效文法G1=(SQAB,a,b,d,P1,S1),其中生成式P1如下:S1IS,SASBIAB,AaASIaAIa,BSBSISBIBSIBIAIbb,由算法4,消单生成式：NS1=S1,S,NS=S,NA=A,NB=A,B由于SASB|ABUP且不是单生成式，故P1中有S1|ASB|AB,同理有SASBIAB,AaASIaAIa,BSBSISBIBSIaASIaAIaIbb,因此生成的无单生成式等效文法为G=(S,S,A,B,a,b,P1,S1)，其中生成式P1如下：S1-|ASB|AB,SfASB|AB,AfaAS|aA|a,BfSB

15、S|SB|BS|aAS|aA|a|bb,由算法1和算法2，消除无用符号(此题没有无用符号);转化为等价的Chomsky范式的文法：将S1fASB变换为SfAC,CfSB,将SfASB变换为SfAC,将AfaAS|aA变换为A-ED|EA,DfAS,E-a,将BfSBS|aAS|aA|a|bb,变换为BfCS|ED|EA|FF,Ffb,由此得出符合题目要求的等价文法：G1=(S,S,A,B,C,D,a,b,P1,S1),其中生成式P1如下：S1f|AC|AB,SfAC|AB,AfED|EA|a,BfCS|SB|BS|ED|EA|a|FF,CfSB,DfAS,Efa,Ffb.15.将下列文法变换为

16、等价的Greibach范式文法：SfDD|a,DfSS|b解：将非终结符排序为S,D,S为低位,D为高位，对于DfSS,用SfDD|a代入得DfDDS|aS|b,用引理4.2.4,变化为DfaS|b|aSD|bD,DfDS|DSD,(2)将D生成式代入S生成式得SfaSD|bD|aSDD|bDD|a,将D生成式代入D生成式得DfaSS|bS|aSDS|bDS|aSSD|bSD|aSDSD|bDSD,由此得出等价的Greibach范式文法：G1=(S,D,D,a,b,P1,S)，其中生成式P1如下：SfaSD|bD|aSDD|bDD|a,DfaS|b|aSD|bD,DfaSS|bS|aSDS|b

17、DS|aSSD|bSD|aSDSD|bDSD.2A1fA3b|A2a,A2fA1b|A2A2a|b,A3fA1a|A3A3b|a解：转化为等价的Chomsky范式的文法：A1fA3A4|A2A5,A2fA1A4|A2A6|b,A3fA1A5|A3A7|a,A4fb,A5fa,A6一A2A5，A7A3A4，转化为等价的Greibach范式的文法:将非终结符排序为A,A2ZA3,A4ZA5,A1为低位A5为高位，对于A2-A、，用A-A扎|A2A5代入得A2-A3A4A4|A2Af4|A2A6|b,用引理4.2.4,变化为A-AAA|b|AAAA|bA,34434422A2-A5A4A2|A6A2

18、|A5A4|A6,对于A3-A1A5，用A1-A3A4IA2A5代入得A3一ZIA44IA3A7|a,A3生成式右边第一个字符仍是较低位的非终结符，将a2生成式代入a3生成式得A-AAAIAAAAAIbAAIAAAAAAIbAAAIAA345344555534425525537Ia,用引理4.2.4,变化为A3-bA5A5IbA2A5A5IaIbA5A5A3IbA2A5A5A3IaA3,A3-A4A5IA4A4A5A5IA4A4A2A5A5IA7IA4A5A3IA4A4A5A5A3IAAAAAAIAA,TOC o 1-5 h z4255373对于A6A2A5，将A2生成式代入A6生成式得A-A

19、AAAIbAIAAAAAIbAA,6344553442525a6生成式右边第一个字符仍是较低位的非终结符，将a3生成式代入a6生成式636得A-bAAAAAIbAAAAAAIaAAAIbAAAAAAI55445255445445553445bAAAAAAAIaAAAAIbAAAAAAIbAAAAAAA55344534455544252554425IaAAAAIbAAAAAAAIbAAAAAAAAI4425553442525534425aAAAAAIbAAIbA,4425255对于A7A3A4，将A3生成式代入A7生成式得A-bAAAIbAAAAIaAIbAAAAIbAAAAAI55425544

20、553425534aA3A4,将a5,a6生成式代入a2生成式得AaAAIbAAAAAAIbAAAAAAAIaAAAAI24255445225544524452bAAAAAAAIbAAAAAAAAIaAAAAAI5344522553445234452bAAAAAAAIbAAAAAAAAIaAAAAAI55442522554425244252bAAAAAAAAIbAAAAAAAAAIaAAAAAAI55344252255344252344252bAAAIbAAIaAIbAAAAAIbAAAAAAIaAAAI25252455445255445445bAAAAAAIbAAAAAAAIaAAAAIbA

21、AAAAAI55344525534453445554425bAAAAAAAIaAAAAIbAAAAAAAI255442544255534425bAAAAAAAAIaAAAAAIbAAIbA,2553442534425255将A4,A7生成式代入A3生成式得A3aA5IaA4A5A5IaA4A2A5A5IaA5A3IaA4A5A5A3IaA4A2A5A5A3IbAAAIbAAAAIaAIbAAAAIbAAAAAIaAAI5542554455342553434bAAAAIbAAAAAIaAAIbAAAAAIbAAAAA554325543435534325534A3IaA3A4A3,由此得出等价的G

22、reibach范式文法:G=(S,D,D,a,b,P1,S)，其中生成式P1如下：A-AA|AA,13425A2-A3A4A4|b|A3A4A4A2|bA2,A3-bA5A5|bA2A5A5|a|bA5A5A3|bA2A5A5A3|aA3,A4-b,A5-a,A-bAAAAA|bAAAAAA|aAAA|bAAAAAA|655445255445445553445bAAAAAAA|aAAAA|bAAAAAA|bAAAAAAA255344534455544252554425|aAAAA|bAAAAAAA|bAAAAAAAA|425553442525534425aAAAAA|bAA|bA,344252

23、55A-bAAA|bAAAA|aA|bAAAA|bAAAAA|755425544553425534aAA,34A-aAA|bAAAAAA|bAAAAAAA|aAAAA|24255445225544524452bAAAAAAA|bAAAAAAAA|aAAAAA|5344522553445234452bAAAAAAA|bAAAAAAAA|aAAAAA|55442522554425244252bAAAAAAAA|bAAAAAAAAA|aAAAAAA|55344252255344252344252bAAA|bAA|aA|bAAAAA|bAAAAAA|aAAA|25252455445255445445b

24、AAAAAA|bAAAAAAA|aAAAA|bAAAAAA|55344525534453445554425bAAAAAAA|aAAAA|bAAAAAAA|255442544255534425bAAAAAAAA|aAAAAA|bAA|bA,2553442534425255A-aA|aAAA|aAAAA|aAA|aAAAA|aAAAAA35455425553455342553|bAAA|bAAAA|aA|bAAAA|bAAAAA|aAA|5542554455342553434bAAAA|bAAAAA|aAA|bAAAAA|bAAAAA554325543435534325534A|aAAA.3343

25、设文法G有如下得生成式:S-aDD,D-aS|bS|a,构造等价的下推自动机.解：根据P162163的算法，构造下推自动机M,使M按文法G的最左推导方式工作.162-163设M=(Q,T,6zq0,Z0ZF),其中Q=q0,qf,T=a,b,=a,b,D,S,Z0=S,F=qf,6定义如下:6q0疋,S)=(q0,aDD)z6q疋,D)=(q,)z(q,)z(q,),6q0,a,a)=(q,)z6q疋疋)=(q)-给出产生语言L=aibjCk|i,j,k20且i=j或者j=k的上下文无关文法.你给出的文法是否具有二义性?为什么?解:G=(S,A,B,C,D,E,a,b,C，P，S)P：S-AD

26、|EB,AaAb|,BbBc|,DcD|,EaE|文法具有二义性。因为当句子3中a,b,c个数相同时，对于3存在两个不同的最左（右）推导。如abcL，存在两个不同的最左推导SnADnaAbDnabDnabcCnabc及SnEBnaEBnaBnabBcnabc。22.设下推自动机M=(q0/qizazbzZ0ZXz6q,Z0g),其中&如下&q0,b,Z0)=(q0,xz。)eq0疋,Z0)=(q。，),A&q0，bx)=(q0,xx),&q1,b,x)=(q1,),&q0，bx)=(q1,x),&q1,z0)=(q0,z0)，试构造文法G产生的语言L(G)=L(M).解：在g中,n=q0zZ0

27、,q0zq0,z0,q1,q0,x,q0,q0,x,q1,q1,z0,q0,q1,z0,q1,q1,x,q0,q1,x,q1.S生成式有S讥厶吒，S讥张1，根据&q0,b,Z0)=(q0,xZ0)，则有口0忆0耳0-blq/q。q/yq。，qo，Zo，q。-blq。,qi，zo，q。，q，Zo，qi-bqo，X,q。qyZyqJ，。忆。-匕也1&忆。耳1,因为有&q0,b,x)=(q0,XX),则有qo,x,q。fbqo,x,q。q/q。,q。，x,q0fbq0,x,q1q1,x,q0，q。，x,qifblq/q。q。,X,q。，x,qifblq/q险x，qi,因为有&q0,a,X)=(qiZ

28、X),则有qo,x,q。faqi,x,q。,q0,x,q1faq1,x,q1，因为有&%,Z。)=(q。,Z。)，则有%血耳。faqo，zo，q。，qi,zo，qifaqo,zo，qi，因为有&q,Z0)=(q。，)，则有qo，zo，q。f，因为有&qiZb,X)=(qiZ),则有q1,x,q1f利用算法1和算法2,消除无用符号后，得出文法G产生的语言L(G)=N,T,P,S其中N=也召山码爲山码広已,q/qj,T=a,b,生成式p如下：S讥张。,q(/Zo,qofbq,X,qi%和。,q。,x,qifblq/qjq?x,qi,qoXqJfaqi,x,qi,q/yq。-眄。忆汽。,qAq。f,

29、口。忆。耳。f-23.证明下列语言不是上下文无关语言:(1)anbnCmW证明假设是上下文无关语言由泵浦引理取常数当3匕且32时可取WapbpCp将3写为333333同时满足333W3和3不可能同时分别包含和因为在这种情况下有333如果3和3都只包含即333aj(bjW则当工时33333中会出现的个数与的个数不等如果3和3都只包含即333Cjj当大于时33333中会出现的个数大于的个数的个数如果3和3分别包含和和当时33333中会出现的个数小于的个数(或个数不等)这些与假设矛盾故不是上下文无关语言ak是质数证明假设是上下文无关语言由泵浦引理取常数当3U且32时可取3=ak(2k且工1)将3当写

30、为3=33333同当时满足|333|Wp且|33|=2j1贝当+寸33333至少包含因子且丰因此必定不是质数即33333不属于这与假设矛盾故不是上下文无关语言证明:由组成的字符串且是含有的个数相同的所有字符串假设是上下文无关语言由泵浦引理取常数当3U且32时可取3akbkCk2将3写为333333同时满足333W3和3不可能同时分别包含和因为在这种情况下有333如果3和3都只包含或即333aj(bj或CjW则当丰时33333中会出现的个数不再相等如果3和3分别包含和和33333中会出现的个数与的不等这些与假设矛盾故不是上下文无关语言24.设G是Chomsky范式文法，存在3uL(G),求在边缘为3的推导树中，最长的路径长度与3的长度之间的关系.解：设边缘为3的推导树中，最长路径长度为n,则它与3的长度之间的关系为|3IW2n-1.因为由Chomsky范式的定义可知,Chomsky范式文法的推导树都是二叉树,在最长路径长度为n的二叉推导树中，满