编译原理第4章答案精编版.docx

1、编译原理第4章答案精编版第四章词法分析1构造下列正规式相应的 DFA(1)1(0 * 101(2)1(1010* | 1(010) * 1)* 0(3)a(a|b) *|ab*a)* b(4)b(ab) * | bb) * ab解：(1)1(0|1) * 101 对应的 NFA为(2)1(1010110F表由子集法将NFA转换为DFAI10 = &closure(MoveTo(l,0)I 1 = &closure(MoveTo(l,1)A0B1B1B1C1,2C1,2D1,3C1,2D1,3B1E1,4E1,4B1B1F表由子集法将NFA转换为DFAI10 = &closure(MoveTo(

2、l,0)I 1 = &closure(MoveTo(l,1)A0B1,6B1,6C10D2,5,7C10D2,5,7E3,8B1,6E3,8F1,4,6,9F1,4,6,9G1,2,5,6,9,10D2,5,7G1,2,5,6,9,10H1,3,6,9,10I1,2,5,6,7H1,3,6,9,10J1,6,9,10K2,4,5,7I1,2,5,6,7L3,8,10I1,2,5,6,7J1,6,9,10J1,6,9,10D2,5,7K2,4,5,7M2,3,5,8B1,6L3,8,10F1,4,6,9M2,3,5,8N3F1,4,6,9N3O4O4P2,5P2,5N3B1,6|ab a) b

3、(| bb) ab (3)a(a|b)(4)b(ab)2已知 NFA=( x,y,z,0,1,M,x,z M(y,1)= $ ,M(z,1)=y,构造相应的 解：根据题意有NFA图如下）其中:M(x,0)=z,M(y,0)=x,y,M(z,0)=x,z,M(x,1)=x,DFAnF表由子集法将NFA转换为DFAI10 = &closure(MoveTo(l,0)I 1 = &closure(MoveTo(l,1)AxBzAxBzCx,zDyCx,zCx,zEx,yDyEx,yEx,yFx,y,zAxFx,y,zFx,y,zEx,y1 1 01F面将该DFA最小化：(1)首先将它的状态集分成两个

4、子集： Pi=A,D,E,P 2=B,C,F(2)区分 P2：由于 F(F,1)=F(C,1)=E,F(F,0)=F 并且 F(C,O)=C,所以 F, C 等价。由于 F(B,O)=F(C,O)=C, F(B,1)=D,F(C,1)=E,而 D, E 不等价(见下步)，从而 B 与 C, F 可以区分。有 P21=C,F,P 22=B。(3)区分P1：由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有Pn=A,E,P 12=D(4)由于F(A,0)=B,F(E,0)=F, 而B, F不等价，所以 A，E可以区分。(5)综上所述，DFA可以区分为P=A，B，D，E，C，F。

5、所以最小化的 DFA如下：3将图4.16确定化:解:0,I10 = &closure(MoveTo(l,0)I 1 = &closure(MoveTo(l,1)ASBQ,VCQ,UBQ,VDV,ZCQ,UCQ,UEVFQ,U,ZDV,ZGZGZEVGZFQ,U,ZDV,ZFQ,U,ZGZGZGZn0,4.把图4.17的 和(b)分别确定化和最小化:(b)解：(a)：A，然后删除B所在的行。)(a2)最小化的 DFA(al)确定化的 DFA(b):该图已经是 DFA下面将该 DFA最小化：(6)首先将它的状态集分成两个子集： Pi=O,P(7)区分 P2 :由于 F(4,a)=0P21=4,P

6、22=1,2,3,5。(8)区分 P22：由于 F(1,b)=F(5,b)=4P221=1,5,P 222=2,3。2=1,2,3,4,5属于终态集，而其他状态输入属于 P21,而 F(2,b)与 F(3,b)a后都是非终态集，所以区分 F2如下：P1，所以区分P22如下不等于4,即不属于下表由子集法将NFA转换为DFAIla = gclosure(MoveTo(l,a)I b = &closure(MoveTo(l,b)A0B0,1C1B0,1B0,1C1C1A0可得图(a1)，由于F(A,b)=F(B,b)=C, 并且F(A,a)=F(B,a)=B, 所以A,B等价，可将 DFA最小化，即

7、：删除B,将原来引向B的引线引向与其等价的状态 A,有图(a2)。( DFA的最小化，也可看作将上表中的 B全部替换为b15 构造一个 DFA它接收艺=0 , 1上所有满足如下条件的字符串：每个 该语言的正则文法。解：根据题意，DFA所对应的正规式应为：(0|(10) *。所以，接收该串的都有0直接跟在右边。然后再构造NFA如下:01F表由子集法将NFA转换为DFAI10 = &closure(MoveTo(l,0)I 1 = &closure(MoveTo(l,1)A0B0,2C1B0,2B0,2C1C1B0,20显然，A, B等价，所以将上述 DFA最小化后有:00对应的正规文法为：GA:

8、A 1C|0A| C 0A6 设无符号数的正规式为 e :e =dd |dd .dd |.dd |dd e(s| & )dd |e(s| & )dd |.dd e(s| & )dd |dd .dd e(s| & )dd化简 e，画岀 e 的 DFA 其中 d=0,1,2,9,s=+, -解：把原正规式的每 2, 3项，4, 5项，6, 7项分别合并后化简有：e =dd |d .dd |d e(s| & )dd |d .dd e(s| & )dd=dd*|d *.dd *|(d *|d *.dd *)e(s| e )dd * 最新资料推荐=(& |d*.|(d *|d *.dd *)e(s| &

9、 )dd *=(& |d *.|d *( & |.dd *)e(s| & )dd *F面构造化简后的 0对应的NFAn7 给文法GS:S aA|bQA aA|bB|bB bD|aQQ aQ|bD|bD bB|aAE aB|bFF bD|aE|b构造相应的最小的 DFA解：由于从S岀发任何输入串都不能到达状态 E和F,所以，状态E, F为多余的状态，不予考虑。这样，可以写出文法ADQGS对应的NFAF表由子集法将NFA转换为DFAII d =-closure(MoveTo(l,d)I e= -closure(MoveTo(I,e)I s=-closure(MoveTo(l,s)I .= -clo

10、sure(MoveTo(I,.)A0,1,4,6:B1,7C5,6r D2,6B1,7B1,7D2,6C5,6E7F6D2,6G3,4,7E7E7F6E7G3,4,7G3,4,7C5,6F表由子集法将NFA转换为DFAII a = &closure(MoveTo(l,a)I b = &closure(MoveTo(l,b)iS2A3Q2A2A4B,Z3Q3Q5D,Z4B,Z3Q6D5D,Z2A7B6D2A7B7B3Q6D由上表可知：(1)因为4, 5是DFA的终态，其他是非终态，可将状态集分成两个子集：Pi=1，2, 3，6，7，P2=4，5 在Pi中因为2,3输入b后是终态，而1，6，7输入

11、b后是非终态，所以 Pi可区分为：Pii=1，6，7，Pi2=2，3在Pii中由于I输入b后为3, 6输入b后为7,而3，7分属Pii和Pi2,所以I与6不等价，同理，I与 7不等价。所以 Pii可区分为：Piii=i ， Pii2=6， 7查看Pii2=6，7，由于输入a后为2，3,所以6，7是否等价由2，3是否等价决定。查看Pi2=2 , 3，由于输入b后为4, 5,所以2, 3是否等价由4, 5是否等价决定。(6)查看P2=4 , 5,显然4, 5是否等价由2, 3与6, 7是否同时等价决定。由于有(4)即6, 7是否 等价由2, 3是否等价决定，所以，4, 5是否等价由2, 3是否等价

12、决定。由于有(5)即2, 3是否等价由 4, 5是否等价决定，所以有 4, 5等价，2, 3等价,进而6, 7也等价。(7)删除上表中的第3, 5, 7行，并将剩余行中的 3, 5, 7分别改为对应的等价状态为 2, 4, 6有下表：II aIb1S2A 2A2A2A4B,Z4B,Z2A6D6D2A6D这样可得最小化的 DFA如下:8 给岀下述文法所对应的正规式:S 0A|1BA 1S|1B 0S|0解：把后两个产生式代入第一个产生式有：S=01|01SS=10|10S有:S=01S|10S|01|10=(01|10)S|(01|10)=(01|10) 即:(01|10) *(01|10)为所

13、求的正规式。4.189 将图解：(1)(i)因为7。由于由于由于(01|10)的DFA最小化，并用正规式描述它所识别的语言:2bbJ 1cax-ba 4图 4.18bb6, 7是DFA的终态，其他是非终态，可将状态集分成两个子集： P仁1 , 2, 3, 4, 5 , P2=6 ,F(6,b)=F(7,b)=6, 而6, 7又没有其他输入，所以 6 , 7等价。F(3,c)=F(4,c)=3,F(3,d)=F(4,d)=5,F(3,b)=6,F(4,b)=7, 而 6, 7 等价，所以 3,4 等价。F(1,b)=F(2,b)=2,F(1,a)=3,F(2,a)=4, 而 3, 4 等价，所以

14、 1,2 等价。由于状态5没有输入字符b,所以与1, 2, 3 , 4都不等价。综上所述，上图 DFA的状态可最细分解为： P=1 , 2 , 3 , 4 , 5 , 6 , 7。bb该DFA用正规式表示为:b*a(c|da) *bb*10 构造下述文法 GS的自动机：S A0A A0|S1|0该自动机是确定的吗？若不确定，则对它确定化。该自动机相应的语言是什么?解：由于该文法的产生式必须先用代入法得到它对应的正规式。把S A0有该文法的正规式： 0(0|01) *0,S A0, A A0|S1中没有字符集 Vt的输入，所以不是确定的自动机。S所以，要将其他确定化，A0 代入产生式 A S1 有: A=A0|A01|0=A(0|01)|0=0(0|01) *。代入改写该文法为确定的自动机为：o0Y由于状态A有3次输入0的重复输入，所以上图只是 NFA下面将它确定化:F表由子集法将NFA转换为DFAII o = &closure(MoveTo(l,0)I b = &closure(MoveTo(l,1)AWBXBXCX,Y,ZCX,Y,ZCX,Y,ZBX由上表可知DFA为:1 : ；A 0宀.1