编译原理第4章答案

1、第四章词法分析1(01011(1010* | 1(010) * 1)* 0a(a|b)*|ab *a) * bb(ab)* | bb) * ab解：(1)1(0* 101对应的NFA为i 构造下列正规式相应的DFA下表DFA1I10 = &closure(MoveTo(l,0)I 1 = &closure(MoveTo(l,1)A0B1B1B1C1,2C1,2D1,3C1,2D1,3B1- E1,4E1,4B1B1下表由子集法将NFA转换为DFAI10 = e-closure(MoveTo(I,0)I 1 = &closure(MoveTo(l,1)A0B1,6:B1,

2、6C10D2,5,7C10D2,5,7E3,8B1,6:E3,8F1,4,6,9:F1,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,构造相应的DFA。解：根据题意有 NFA图如下下表由子集法将 NA转换为(3)a(a|b)

3、 ab a) (略) (4)b(ab) bb) * ab (2 已知I略)NFA=(x,y,z,0 ,1,M,x,z)其中：M(x,0)=z,M (y,0)=x,y,M(z,0)=x,z ,M(x,1)=x,M(y,1)= $ ,M(z,1)=y-Qi0 AJ10 = &closure(MoveTo(l,0)7.I 1 = &closure(MoveTo(l,1)Ax( xy)【zAxBz Cx,zDyCx,z°、Cx,zEx,yr Dy'Ex,yr Ex,y0Fx,y,zAxFx,y,zj|Fx,y,zEx,y0DFA11口 0 (©0 ©

4、;©00 O 01F面将该(5)DFA最小化：首先将它的状态集分成两个子集：P =A,D,E,P 2=B,C,F区分 P2：由于 F(F,1)=F(C,1)=E,F(F,0)=F 并且 F(C,0)=C, F(B,1)=D,F(C,1)=E, 而D, E不等价(见下步)，从而 B与C， 区分P1:由于A, E输入0到终态，而D输入0不到终态，所以所以 F , C 等价。由于 F(B,0)=F(C,0)=C,F 可以区分。有 P21=C,F,P 22=B oD与 A，E可以区分，有 P1=A,E,P 12=D o由于F(A,0)=B,F(E,0)=F, 而B，F不等价，所以 A，E可以

5、区分。综上所述，DFA可以区分为P=A，B，D，E，C，F。所以最小化的DFA如下:11 0 I。0D03.将图4.16确定化:n0V0解：下表由子集法将 NFA转换为DFA的(a)和(b)分别确定化4.把图 4.17和最小化：解：(a):换为下DFACE1AFBDab子集法将NFA转b0 r由a1*(b(b)IIa = &closure(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最小化，

6、即：删除 B,将 原来引向B的引线引向与其等价的状态 A,有图(a2) o( DFA的最小化，也可看作将上表中的B全部替换为 A,然后删除B所在的行。)a定化的小化的该图已小化：nDFADFA经是DFA。下面将该首先将它的(8)(9)(10)状态集分成两个子集：P1=0,P 2=1,2,3,4,5区分P2:由于F(4,a)=0 属于终态集，而其他状态输入a后都是非终态集，所以区分P2如下： P21=4,P 22=1,2,3,5。区分 P22：由于 F(1,b)=F(5,b)=4P221=1,5,P222=2,3。区分 P221：由于 F(1,b)=F(5,b)=4,区分P222：由于F(2,a

7、)=1属于属于P21,而F(2,b)与F(3,b)不等于4,即不属于P21，所以区分P22如下:即 F(1,a)=1,F(5,a)=5, 所以 1,5 等价。P221，而 F(3,a)=3 属于 P>22,所以 2， 3 可区分。P222 区分为 2丄2 ， P22223。其中1,5等价。删去状态5,将原来引向5(11)结论：该 DFA的状态集可分为：P= 0,1,5,2,3,4 ,的引线引向与其等价的状态1,有图(bl)(b1)最小化的DFAb23ba1baabes5 构造一个 DFA它接收 艺 串：每个1都有0直接跟在右解：根据题意，DFA所对应的 收该串的NFA如下：=0 , 1上

8、所有满足如下条件的字符 边。然后再构造该语言的正则文法。 正规式应为：(01(10)*。所以，接下表由子集法将 NFA转换为DFAI10 = bdosure(MoveTo(l,0)I 1 = bdosure(MoveTo(l,1)A0B0,2:C1B0,2B0,2C1C1B0,2A 1C|0A| bC 0A6设无符号数的正规式为e :e =dd |dd .dd |.dd |dd e(s| b )dd |e(s| b )dd |.dd e(s| b )dd |dd .dd e(s| b )dd 化简 e ,画岀 e 的 DFA 其中 d=0,1,2,9,s=+,-解：把原正规式的每2, 3项，4

9、, 5项，6 , 7项分别合并后化简有：e =dd |d .dd |d e(s| b )dd |d .dd e(s| b )dd=dd*|d *.dd*|(d *|d *.dd *)e(s| b )dd*=(b |d *.|(d *|d *.dd *)e(s| b )dd *=(b |d *.|d *( b |.dd *)e(s| b )dd *下面构造化简后的e对应的NFADFAd表由子集法将NFA转换为II d =-closure(MoveTo(l,d)I e=b -closure(MoveTo(I,e)I s= b-closure(MoveTo(I,s)I . = -closure(Mo

10、veTo(l,.)A0,1,4,6B1,7C5,6D2,6B1,7B1,7D2,6C5,6E7F62D2,6G3,4,7E7E7F6E7G3,4,7G3,4,7C5,67 .给文法dDdnGS:S/ dBeAaA|bQ aA|bB|b bD|aQ aQ|bD|b bB|aA aB|bF bD|aE|bE和F,所以，状态 E, F为多余的状态，不予考虑。这样，可以写岀文子集法将NFA转换为DFA下表由构造相应的最小的 DFA。解：由于从S岀发任何输入串都不能到达状态法GS对应的NFAII a = &closure(MoveTo(l,a)I b = &closure(MoveTo(

11、l,b)1S2A3Q2A2A4B,Z3Q3Q5D,Z4B,Z3Q6D5D,ZI'2A7B6D2A7B7B3Q:6DQ由上表可知:(1)因为4, 5是DFA的终态，其他是非终态，可将状态集分成两个子集：Pi=1，2，3, 6, 7，P2=4，5 在R中因为2,3输入b后是终态，而1, 6, 7输入b后是非终态，所以P1可区分为：Pn=1 , 6, 7 , P12=2 , 3 在P11中由于1输入b后为3, 6输入b后为7,而3, 7分属P11和P12，所以1与6不等价，同理，1与7不等价。 所以P11可区分为：P111=1 , P112=6 , 7 查看Ph2=6 , 7，由于输入a后为

12、2, 3,所以6, 7是否等价由2, 3是否等价决定。(5)查看P12=2 , 3，由于输入b后为4, 5,所以2, 3是否等价由4, 5是否等价决定。 查看P2=4 , 5,显然4, 5是否等价由2, 3与6, 7是否同时等价决定。由于有(4)即6, 7是否等价由2, 3是否等价决定，所以，4 , 5是否等价由2, 3是否等价决定。由于有(5)即2 , 3是否等价由4, 5是否等价决定，所以有4, 5等价，2, 3等价，进而6, 7也等价。 删除上表中的第 3, 5, 7行，并将剩余行中的 3, 5 , 7分别改为对应的等价状态为 2 , 4, 6有下表：II aIb1S2A2A2A2A4B

13、,Z4B,Z2A6D6D2A6D8 给岀下述文法所对应的正规式: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)为所求的正规式。(01|10)9 将图4.18的DFA最小化，并用正规式描述它所识别的语言:解：(1)(1)子集:,4 等价b,d,其他是非终态，可将状态集b而 6 , 7又没有其他输入，所以b因为 由于 由于 由于 由于状态5没有输入2 ,所以与1 , 2 , , 4都不等价。：“综上所述，上图 DFA的

14、状态可最细分解为：P=1 , 2 , 3 , 4 , 5 , 6 , 7。6, 7是DFA的终态，F(6,b)=F(7,b)=6,F(3,c)=F(4,c)=3,F(3,d)=F(4,d)=5,F(3,b)=6,F(1,b)=F(2,b)=2,FX=3,F(2,a)=42P1=1 , 2, 3, 4, 5 , P2=6 , 7。7等价，所以3,4等价。等价。这样可得最小化的 DFA如下:该DFA用正规式表示为：b*a(c|da) *bb*10 构造下述文法 GS的自动机:S A0A A0|S1|0该自动机是确定的吗？若不确定，则对它确定化。该自动机相应的语言是什么?解:由于该文法的产生式S AO, A A0|S1中没有字符集 VT的输入，所以不是确定的自动机。要将其他确定化，必须先用代入法得到它对应的正规式。把S A0代