编译原理第章答案

1、1构造下列正规式相应的DFA：(1)1(0|1)*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为II 0=-closure(MoveTo(I,0)I 1=-closure(MoveTo(I,1)A0B1B1B1C1,2C1,2D1,3C1,2D1,3B1E1,4E1,4B1B1下表 由子集法 将 NFA 转 换为 DFA：II 0=-closure(MoveTo(I,0)I 1=-closure(MoveTo(I,1)A0B1,6B1,6C10D2,5,7C10D

2、2,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）其中：(3)a(M(x,0)=z,M(y,0)=x,y,M(z,0)=x,z,M(x,1)=x,M(y,1)=,M(z,1

3、)=y,(a|b) *|ab *a )*b( 略)(4) b( (ab) * |bb) * ab(略 ) 2已知NFA=0,1,M,x,z 相应的 DFA。 解：根据题意有(x, y,z, 构造下表由子集法将 NFA转换为 DFA：10I 1 0I 0=-closure(MoveTo(I,0)I 1=-closure(MoveTo(I,1)AxxBzyAxBz0 1Cx,zDyCx,z0z0zCx,zEx,yDyEx,yEx,y0Fx,y,zAxFx,y,zFx,y,zEx,yNFA图如下1 1 0A 0 B 0 C D 0 E 0 1F0 11面将该 DFA最小化：(1) 首先将它的状态集分

4、成两个子集：P1=A,D,E,P 2=B,C,F(2) 区分 P2: 由于 F(F,1)=F(C,1)=E,F(F,0)=F 并且 F(C,0)=C, 所以 F， C 等价。由于 F(B,0)=F(C,0)=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可以区分，有 P11=A,E,P 12=D 。(4) 由于 F(A,0)=B,F(E,0)=F, 而 B，F 不等价，所以 A， E可以区分。1I0， I 0=-co

5、sure(MoveTo(I,0)I 1=-closure(MoveTo(I,1)AS S1B Q,VQ1CQZ, U 0，1BQ,VDV,ZCQ,UCQ,UEV1FQ,U,ZDV,Z1G ZUGZEVGZ11FQ,U,ZDV,ZFQ,U,ZGZGZGZ04. 把图 4.17确定化和最小的 (a) 和 (b) 分别 化：(5) 综上所述， DFA可以区分为 P=A ，B ，D ，E ， C，F 。所以最小化的 DFA如下：表由子集法(a)(b) 解： (a):DFA的最小化，也可看作将上表中的B 全部将 NFA 转换为 DFA：bIIa =-closure(MoveTo(I,a)I b=-clo

6、sure(MoveTo(I,b)A0B0,1C1B0,1B0,1C1C1A0可得图( a1)，由于 F(A,b)=F(B,b)=C, 并且 F(A,a)=F(B,a)=B, 所以 A,B 等价，可将 DFA最小化，即：删除 B，将原来引向 B 的引线引向与其等价的状态A，有图 (a2)替换为 A，然后删除 B 所在的行。)(a1)确 化的CA定化的DFA 该图已 DFA最aDFA( a2)最小经是 DFA。下 小化：(6) 首先(b): 面将该将它的状态集分成两个子集： P1=0,P 2=1,2,3,4,5(7) 区分 P2：由于 F(4,a)=0 属于终态集，而其他状态输入 a 后都是非终态

7、集，所以区分 P2如下： P21=4,P 22=1,2,3,5 。(8) 区分 P22: 由于 F(1,b)=F(5,b)=4 属于 P21,而 F(2,b) 与F(3,b) 不等于 4,即不属于 P21，所以区分 P22如下： P221=1,5,P 222=2,3 。(9) 区分 P221: 由于 F(1,b)=F(5,b)=4, 即 F(1,a)=1,F(5,a)=5, 所以 1,5 等价。(10) 区分 P222:由于 F(2,a)=1 属于 P221，而 F(3,a)=3 属于 P222,所以 2，3可区分。 P222区分为 P22212 ，P2222 3(11) 结 论：该 DFA的

8、状态集可分为： 向 5 的引线引向与其等价的状态P=0,1,5,2,3,4,1，有图 (b1) 。其中 1,5 等价。删去状态 5，将原来引=0 ， 1 上所有满足如下条 直接跟在右边。然后再构的正规式应为： 的 NFA 如下：(b1) 最小化的 DFA 5构造一个 DFA，它接收 件的字符串：每个 1 都有 0 造该语言的正则文法。 解：根据题意， DFA所对应 (0|(10) *。所以，接收该串0 1下表由子集法将 NFA转换为 DFA：II 0=-closure(MoveTo(I,0)I 1=-closure(MoveTo(I,1)A0B0,2C1B0,2B0,2C1C1B0,2GA ：

9、A 1C|0A| C 0A 6设无符号数的正规式为： =dd*|dd *.dd * |.dd *|dd *e(s| )dd *|e(s| )dd *|.dd *e(s| )dd * |dd *.dd *e(s| )dd化简,画出 的 DFA，其中 d=0,1,2, 9,s=+, -解：把原正规式的每 2，3项，4，5 项， 6，7项分别合并后化简有： =dd*|d *.dd *|d * e(s| )dd *|d *.dd *e(s| )dd *=dd*|d *.dd *|(d *|d *.dd *)e(s| )dd *=( |d * .|(d *|d *.dd *)e(s| )dd *下面构应

10、的7造化简后的NFA：对2d3sII d= -closure(MoveTo(I,d)I e= -closure(MoveTo(I,e)I s=-closure(MoveTo(I,s)I . =-closure(MoveTo(I,.)A0,1,4,6B1,7C5,6D2,6B1,7B1,7D2,6C5,6E7F6D2,6G3,4,7E7E7F6E7G3,4,7G3,4,7C5,6下表由子集法将 NFA转换为 DFA：7给文法GS：SdDAaA|bQ aA|bB|b bD|aQ aQ|bD|b bB|aA aB|bF bD|aE|b构造相应的最小的 DFA。E，F 为多余的状态，不予考虑。这样，可

11、解：由于从 S出发任何输入串都不能到达状态E 和 F，所以，状态下表由子集法将 NFA转换为a以写出文法 GS 对应的 NFA：II a=-closure(MoveTo(I,a)I b=-closure(MoveTo(I,b)1S2A3Q2A2A4B,Z3Q3Q5D,Z4B,Z3Q6D5D,Z2A7B6D2A7B7B3Q6D由上表可知：(1) 因为 4， 5 是 DFA的终态，其他是非终态，可将状态集分成两个子集：P1=1，2，3，6，7 ， P2=4 ， 5(2) 在 P1中因为 2,3 输入 b后是终态，而 1，6，7 输入 b 后是非终态，所以 P1可区分为： P11=1 ，6，7 ，

12、P12=2 ， 3(3) 在 P11中由于 1输入 b后为 3，6输入 b后为 7，而 3，7分属 P11和 P12，所以 1与 6不等价，同理， 1与 7不 等价。所以 P11 可区分为：P111=1 ， P112=6 ， 7(4) 查看 P112=6 ， 7 ，由于输入 a后为 2， 3，所以 6，7是否等价由 2，3 是否等价决定。(5) 查看 P12=2 ， 3 ，由于输入 b后为 4，5，所以 2，3 是否等价由 4，5是否等价决定。(6) 查看 P2=4 ， 5 ，显然 4， 5是否等价由 2，3与 6， 7是否同时等价决定。由于有(4)即 6，7是否等价由2，3是否等价决定，所以

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

14、) 即:(01|10) * (01|10) 为所求的正规式。4.18(01|10)的 DFA 最小化，并用正规式描述它所识别的语言：解：(1)(2)(3)(1)(2)(3)因为7。由于由于由于16，7是 DFA的终态， b其他是非终态，可将图 4.18 b3状态集F(6,b)=F(7,b)=6, F(3,c)=F(4,c)=3,F F(1,b)=F(2,b)=b2 ,=3,F(2,a)=4,而 6，7 又没有其他输=F(4,d)=5,Fa( 3,b)=6,bP1=1，2，3，4，5 ，P2=6 ，7 等价，所以 3,4 等价。6， bb。子集：57 等价以7 1,由于状态 5没有输入字符 b, 所以与 1，2，3， 综上所述，上图 DFA的状态可最细分解为：3，4 等价，所以 7 1,2 等价。4 都不等价。P=1 ， 2 ，3 ，4 ，5 ， 6 ， 7 。该 DFA 用正规式表示为：b*a(c|da) *bb*10 构造下述文法 GS 的自动机： S A0A A0|S1|0 该自动机是确定的吗？若不确定，则对它确定化。该自动机相应的语言是什么？ 解：由于该文法的产生式 S A0， A A0|S1 中没有字符集 VT的输入，所以不是确定的自动机。要将其他确定 化，必须先用代入法得到它对应的正规式。把 S A0代入产生式 A S1有