习题解答(123章).ppt

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第二次作业：,P38 1、3、5、7、8(1)(3)(5)、10、11(1)(2)、12(1)(3)(5)、15,第1、3、5题 符号串集合的运算P19,第7题 文法的形式定义 P22,第8题 句型、句子的定义 P23,第10、11题 语言的形式定义，从文法语言 P24,第12题 语言文法 P25,第15题 推导语法树、句型短语、简单短语，句柄的概念,P26、P27,P38 1、设T111，010，T20，01，1001，,计算：T2T1，T1*，T2,+,。,T2T1011，0010，0111，01010，100111，1001010,T1*，11，010，1111，11010，01011，010010,T2,+,0，01，1001，00，001，01001，010，0101,P38 3、令A0，1，2，写出集合A,+,和A*的七个最短符号串。,A,+,：0，1，2，00，01，02，10（有多种可能）,A*：，0，1，2，00，01，02（有多种可能）,P38 5、试证明：A+A A*A*A。,证明：A,+,A1A2An,A*A0（即）A+,A A*A（A0A+）AA+A+A+A,（A0A+）AA*A（证毕）,符号串集合的运算P19,P38 7、设有文法GS：,SA,AB|IF A THEN A ELSE A,BC|B+C|+C,CD|C*D|*D,DX|(A)|-D 试写出V,N,和V,T,。,V,N,S，A，B，C，D,V,T,IF，THEN，ELSE，+，*，X，(，)，-,文法的形式定义 P22,P39 12、试分别构造产生下列语言的文法：,（1）ab,n,a|n=0，1，2，3,（3）aba,n,|n1,（5）a,n,b,m,c,p,|n，m，p0,（1）GV,N,，V,T,，P，S，V,N,S，A，V,T,a，b，,P：SaAa,AbA|,（3）GV,N,，V,T,，P，S，V,N,S，A，V,T,a，b，,P：SabA,AaA|a,（5）GV,N,，V,T,，P，S，V,N,S，A，B，C，,V,T,a，b，c，,P：SABC,AaA|,BbB|,CcC|,语言文法 P25,P39 15.设文法G规则为：,S：=AB,B：=a|Sb,A：=Aa|bB,对下列句型给出推导语法树，并求出其句型短语，简单短语和句柄。,（2）baabaab (3)bBABb,2)句型baabaab的短语a,ba,baa,baab,baabaab，简单短语a，句柄 a,3)短语bB,AB,ABb，简单短语bB,AB，句柄bB,推导语法树、句型短语、简单短语，句柄的概念,P26、P27,第三次作业：,P40 18、19(1)(3)、21、23、24、26、27、29,第18题、第19题 文法二义性的证明 P29,第21题 句子关于文法的最左、最右推导P22P27,第23题 初步语法分析(分析句子)P31、P32,第24题 四种文法的判别P34P35,第26题 第27题 语言文法,第29题 文法的其他表示法（扩充的BNF）P36、P37,P41 23.设有文法如下：,:=V1,V1:=V2|V1iV2,V2:=V3|V2+V3|iV3,V3:=)V1*|(,试分析句子(,)(*,i(,(+(,(+(i(,(+)(i(*i(。,解=V1=V2=V3=(,=V1=V2=V3=)V1*=)V2*=)V3*=)(*,=V1=V2=iV3=i(,=V1=V2=V2+V3=V3+V3=(+V3=(+(,=V1=V1iV2=V1iV3=V1i(=V2i(=V2+V3i(,=V2+(i(=V3+(i(=(+(i(,=V1=V1iV2=V2iV2=V2+V3iV2=V3+V3iV2,=(+V3iV2=(+)V1*iV2=(+)V1iV2*iV2=(+)V2iV2*iV2,=(+)V3iV2*iV2=(+)(iV2*iV2=(+)(iV2*iV2,=(+)(iV3*iV2=(+)(i(*iV2=(+)(i(*iV3=(+)(i(*i(,初步语法分析(分析句子)P31、P32,自顶向下推导,自底向上规约,P41,24.下面文法那些是短语结构文法，上下文有关文法，上下文无关文法，及正规文法？,1.S:=aB B:=cB B:=b C:=c,2.S:=aB B:=bC C:=c C:=,3.S:=aAb aA:=aB aA:=aaA B:=b A:=a,4.S:=aCd aC:=B aC:=aaA B:=b,5.S:=AB A:=a B:=bC B:=b C:=c,6.S:=AB A:=a B:=bC C:=c C:=,7.S:=aA S:=A:=aA A:=aB A:=a B:=b,8.S:=aA S:=A:=bAb A:=a,正规文法 1,上下文无关文法 2 5 6 7 8,上下文有关文法 3,短语结构文法 4,四种文法的判别P34P35,P41,26.给出产生下列语言L（G）=W|W0，1+且W不含相邻1,的正规文法。,G=(S,A,B,0,1,P,S),P:S:=0|1|0B|1A S:=0|1|0S|1A,A:=0|0S 或者 A:=0|0S,B:=0|0S|1A,1)0、1 S:=0|1,2)00,、,01、10 S:=0|1|0S|1A A:=0,3)000、001、010、100、101 S:=0|1|0S|1A A:=0|0S,4)0000、0001、0010、0100、0101、,1000、1001、1010,语言文法,P41 27.给出一个产生下列语言 L（G）W|Wa,b*,且W中含a的个数是b个数两倍的前后文无关文法。,文法G=(S,A,B,a,b,P,S),P:S:=AAB|ABA|BAA|,A:=aS,B:=bS,或者,S:=Saab|aSab|aaSb|aabS|Saba|aSba|abSa,|abaS|Sbaa|bSaa|baSa|baaS|,或者 S:=aaSb|abSa|baSa|baa|aba|aab,解法：,1)S:=,2)aab,aba,baa S:=aab|aba|baa,3)aaaabb,aaabab,aaabba,aababa,aabbaa,bbaaaa,S:=Saab|aSab|aaSb|aabS|Saba|aSba|abSa|abaS|Sbaa,|bSaa|baSa|baaS|,P42,29.用扩充的BNF表示以下文法规则：,Z:=AB|AC|A,A:=BC|BCD|AXZ|AXY,S:=aABb|ab,A:=Aab|,解:,1Z:=A（B|C|）:=AB|C,2A:=BC（|D）|X（Z|Y）:=BCD|X（Z|Y）,3A:=a(AB|)b):=aABb,4A:=ab|:=ab,t,或 t,t t不出现或出现任意多次,()提取因子,文法的其他表示法（扩充的BNF）P36、P37,思考题：,语言L(GS)=b,2i+1,|i=0对应,的3型文法？,GV,N,，V,T,，P，S，V,N,S，A，V,T,b，,S bbS|b?,P：S bA|b,A bS,第四次作业：,P74 2、4、5,第4题 考察范围：左线性文法 状态转换图P47,第5题 考察范围：右线性文法 状态转换图P48,P74,4.画出下列文法的状态图：,Z：=Be,B：=Af,A：=e|Ae,并使用该状态图检查下列句子是否该文法的合法句子：f,eeff,eefe。,由状态图可知只有eefe是该文法的合法句子。,左线性文法 状态转换图P47,P74 5.设右线性文法G=(S,A,B,a,b,S,P)，其中P组成如下：,S：=bA A：=bB A：=aA A：=b B：=a,画出该文法的状态转换图。,右线性文法 状态转换图P48,第五次作业：,P74 6、7、8、9、10,第6题 左线性文法 状态转换图，,状态转换图 FA(DFA/NFA),第7题 具体字符串 状态转换图,状态转换图正规文法（右线性）,第8题 NFADFA,第9题 DFA右线性文法,右线性文法左线性文法,第10题 正规文法(右线性)DFA,P74,6.构造下述文法GZ的自动机，该自动机是确定的吗？它相应的语言是什么？,Z：=A0 A：=A0|Z1|0,解二：先画出该文法状态转换图：,其中M：,M（S，0）=A M（S，1）=,M（A，0）=A，Z M（A，1）=,M（Z，0）=,M（Z，1）=A,显然该文法的自动机是非确定的；,它相应的语言为：0，1上所有满足以00开头以0结尾,且每个1必有0直接跟在其后的字符串的集合,NFA=（S，A，Z，0，1，M，S，Z）,左线性文法 状态转换图，,状态转换图 FA(DFA/NFA),解一：将文法变换成符合规则的情况,P74,7.构造一个DFA，它接受0，1上所有满足下述条件的字符串，,其条件是：字符串中每个1都有0直接跟在右边，然后，再构造该,语言的正规文法。,解法一：,DFA=（S，A，Z，,0，1，M，S，Z）,其中M：M（S，0）=Z,M（S，1）=A,M（A，0）=Z,M（Z，0）=Z,M（Z，1）=A,该语言的正规文法GZ为：,右线性文法：/S：=0|1A|0Z 左线性文法：,A：=0|0Z A：=1|Z1,Z：=0|1A|0Z Z：=0|A0|Z0,0，,00，10,000，010，100,具体字符串 状态转换图,状态转换图正规文法（右线性）,解法二,构造出正规表达式,(0|10)*,转换系统,P74 8.设(NFA)M=(A,B,a,b,M,A,B)，其中M定义如下：,M(A,a)=A,B M(A,b)=B M(B,a)=,M(B,b)=A,B,请构造相应确定有穷自动机(DFA)M。,解：构造一个如下的自动机(DFA)M，(DFA)M=K,a,b,M,S,Z,K的元素是A B A,B,由于M（A,a）=A,B，故有M（A,a）=A,B,同样 M（A，b）=B,M（B，a）=,M（B，b）=A，B,由于M（A，B，a）=M（A，a）U M（B，a）=A，BU=A，B,故 M（A，B，a）=A，B,由于M（A，B，b）=M（A，b）U M（B，b）=BU A，B=A，B,故 M（A，B，b）=A，B,S=A，终态集Z=A，B，B,重新定义：令0=A 1=B 2=A,B，则DFA如下所示：,NFADFA,P59,可以进一步化简，把,M,的状态分成终态,组1，2和非终态组0,由于1，2,a,=1，2,b,=2,1，2，不能再划分。至此，整个划分含有两组1，20,令状态1代表1，2，化简如图：,P74 9.设有穷自动机M=(S,A,E,a,b,c,M,S,E)，其中M定义为,M(S,c)=A M(A,b)=A M(A,a)=E 请构造一个左线性文法。,解：先求右线性文法,ScA AbA Aa|aE,方法一：,其左线性文法G=（VN,VT,P,S）,VN=A,S VT=a,b,c,P:Ac AAb SAa EaA实际上是多余的规则，应该去掉,方法二：,状态转换图,DFA右线性文法 P61,右线性文法左线性文法 P50,P74,10.已知正规文法G=(S,B,C,a,b,c,P,S)，其中P内包含如下产生式：,S:=aS|aB ,B:=bB|bC ,C:=cC|c 请构造一个等价的有穷自动机。,解：M=(S,B,C,T,a,b,c,M,S,T),M(S,a)=S M(S,a)=B M(S,b)=M(S,c)=,M(B,a)=M(B,b)=B M(B,b)=C M(B,c)=,M(C,a)=M(C,b)=M(C,c)=T M(C,c)=C,正规文法(右线性)FA P61,第六次作业：,P7576,11、15、16、18、19（1）、20（1）（3）,第11题 由正规式构造DFA P65、66,第15题 NFA构造DFA P57（状态图）P65（转换系统图）,第16、20题 两个正规式的等级关系P63,（若两个正规式表达的正规集相等则两者等价）,第18题 正规文法构造相应正规式 P63,第19题 由正规式构造正规集P63,P74 11.构造下列正规式相应的DFA：,（1）1(0|1)*101,解：先构造该正规式的转换系统：,S,Z,1(0|1)*101,S,1,5,3,4,Z,1,1,0,1,(0|1)*,S,1,5,3,4,Z,1,1,0,1,2,0,1,I,I,0,I,1,S,0 1,S,1,2,3,0,1,1,2,3,2,3,2,3,4,1,2 3,2,3,2,3,2,3,4,2,2 3,2,3,4,2,3,5,2,3,4,3,4 3,2,3,5,2,3,2,3,4,Z,4,2 5,2,3,4,Z,2,3,5,2,3,4,5,4 3,由上述转换系统可得状态转换集K=S,1,2,3,4,5,Z，状态子集转换矩阵如下表所示：,由正规式构造DFA P65、66,其对应的DFA状态转换图为：,0,5,1,1,2,3,1,0,0,1,1,4,0,0,1,1,0,0,5,1,1,2,3,4,0,1,1,1,1,0,0,0,现在对该DFA进行化简，最终得到下列化简后的状态转换图,（先将其分成两组终态组5和非终态组0,1,2,3,4，,再根据是否可继续划分来确定最后的组数）：,P74 15.用两种方法将(NFA)M=(X,Y,Z,0,1,M,X,Z)，,构造相应的DFA，其中：,M(X,0)=Z M(X,1)=X M(Y,0)=X,Y,M(Y,1)=,M(Z,0)=X,Z M(Z,1)=Y,X,Z,1,0,1,0,0,0,Y,0,第一种方法：先画出其状态转换图，利用非子集法：,假设(DFA)M=(K,VT,M,S,Z)，,其中K=X,Y,Z,X,Y,X,Z,Y,Z,X,Y,Z，,VT=0,1，M的规则如下表：,I,I,0,I,1,S,0 1,X,Z,X,0,2 0,Y,X,Y,1,3,Z,X,Z,Y,2,4 1,X,Y,X,Y,Z,X,3,6 0,X,Z,X,Z,X,Y,4,4 3,Y,Z,X,Y,Z,Y,5,6 1,X,Y,Z,X,Y,Z,X,Y,6,6 3,NFA构造DFA P57（状态图）P65（转换系统图）,0,1,1,0,0,0,1,3,0,1,1,2,4,6,0,其中Y,Z为不可到达状态，应该删去，,所以S=X，Z=Z,X,Z,X,Y,Z，再进行化简，,发现4和6两状态等价，最后其DFA如下所示：,第二种方法：先构造其对应的转换系统,X,Z,1,0,1,0,0,0,Y,0,Z,S,由上述转换系统可得状态转换集、,状态子集转换矩阵如下表所示：,I,I,0,I,1,S,0 1,S,X,Z,Z,X,0,1 2,Z,Z,X,Z,Z,Y,1,3,4,X,Z,Z,X,2,1 2,X,Z,Z,X,Z,Z,X,Y,3,3 5,Y,X,Y,4,5,X,Y,X,Y,Z,Z,X,5,6 2,X,Y,Z,Z,X,Y,Z,Z,X,Y,6,6 5,1,4,1,0,5,0,0,0,1,0,1,3,6,1,0,2,先化简，分为非终态集 2,4,5,0 和终态集 6,1,3，,易于发现可划分为0,2，1，3,6，4，5，其DFA如下所示：,P75 20.证明下列关系式成立，其中A、B是任意正规表达式。,（1）A|A=A （3）A*=|AA*,（1）解：L(A|A)=L(A)L(A)=L(A)，所以A|A=A；,（3）解：L(A*)=(L(A)*，L(|AA*)=L(A)L(A*)=(L(A)*，,所以A*=|AA*；,P74 16.已知e1=(a|b)*，e2=(a*b*)*，试证明e1=e2。,证明：,L(e1)=L(a|b)*)=(L(a|b)*=(L(a)L(b)*=a,b*；,L(e2)=L(a*b*)*)=(L(a*b*)*=(L(a*)L(b*)*=a*b*,=a,b*；,因此e1=e2（得证）,两个正规式的等级关系P63,（若两个正规式表达的正规集相等则两者等价）,P74 18.根据下面正规文法构造等价的正规表达式：,S:=cC|a ,A:=cA|aB ,B:=aB|c ,C:=aS|aA|bB|cC|a ,解：由式可得 B=aB+c B=a*c,由式可得 A=cA+aB A=c*aa*c,由式可得 S=cC+a,由式可得 C=aS+aA+bB+cC+a,C=c*(aS+aA+bB+a),C=c*(aS+ac*aa*c+ba*c+a),S=cc*(aS+ac*aa*c+ba*c+a)+a,=cc*aS+cc*(ac*aa*c+ba*c+a)+a,=(cc*a)*(cc*(ac*aa*c+ba*c+a)+a),=(cc*a)*(cc*(ac*aa*c|ba*c|a)|a),另一种答案是S=c(ac|c)*(ac*aa*c|ba*c|aa|a)|a,正规文法构造相应正规式 P63,P74 19.a,b，写出下列正规集：,（1）(a|b)*(aa|bb)(a|b)*,解：L(a|b)*(aa|bb)(a|b)*),=L(a|b)*)L(aa|bb)L(a|b)*),=(L(a|b)*aa,bb(L(a|b)*,=a,b*aa,bba,b*,由正规式构造正规集P63,