编译原理第4章答案

1、第四章词法分析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(101011£0£F表由子集法将NFA转换为DFAI10 = &closure(MoveTo(l,0)I 1= &closure(MoveTo(l,1)A0B1B1B1C1,2C1,2D1,3C1,2D1,3B1E1,4E1,4B1B1F表由子集法将NFA转换为DFA|ab a) b (|

2、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,DFAI10 = &closure(MoveTo(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

3、,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,6110110F表由子集法将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,yF

4、面将该DFA最小化:(1)首先将它的状态集分成两个子集：R=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。 区分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可以区分。综上所述，DFA

5、可以区分为P=A，B，D，E，C，F。所以最小化的 DFA如下:3将图4.16确定化:解: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)分别确定化和最小化:b23bab145bb(b)解：(a1)确定化的 DFA(b):该图已经是 DFA下面将该 DFA最小化：(6) 首先将它的状态集分成两个子集：R=O,P(7) 区分 P2 :由于 F(4,a)=0(a

6、2)最小化的 DFA2=1,2,3,4,5属于终态集，而其他状态输入a后都是非终态集，所以区分F2如下(a)：下表由子集法将NFA转换为DFAIIa = 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最小化，即：删除B,将原来引向B的引线引向与其等价的状态A,有图(a2)。( DFA的最小化，也可看作将上表中的B全部替换为A，然后删除B所在的行。)P21=4,P 22=1,2,3

7、,5。(8) 区分P22：由于F(1,b)=F(5,b)=4 属于P21,而F(2,b)与F(3,b)不等于4,即不属于 內，所以区分P22如下:P221=1,5,P222=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 属于 氐，所以 2, 3 可区分。P222 区分为 P222i2 , P2222Q(11) 结论：该DFA的状态集可分为：P= 0,1,5,2,3,4 ,其中1,5等价。删去状态5,将原来引向5的引线引向

8、与其等价的状态1,有图(b1)。b3bab14b(b1)最小化的DFA5 构造一个NFA转换为DFADFA它接收艺=0 , 1上所有满足如下条件的字符串：每个1都有0直接跟在右边。然后再构造该语言的正则文法。解：根据题意，DFA所对应的正规式应为：(0|(10) *。所以，接收该串的 NFA如下:I10 = &closure(MoveTo(l,0)I != &closure(MoveTo(l,1)A0B0,2C1B0,2B0,2C1C1B0,2F表由子集法将对应的正规文法为：GA:A 1C|0A| £C 0A6 设无符号数的正规式为e：9 =dd*|dd *.dd *

9、|.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项分别合并后化简有：9 =dd |d .dd |d e(s| e )dd |d .dd e(s| e )dd=dd*|d *.dd *|(d *|d *.dd *)e(s|e )dd *=(e |d *.|(d *|d *.dd *)e(s| e )dd *=(£ |d *.|d *( £

10、; |.dd *)e(s|£ )ddF表由子集法将NFA转换为DFAII d =£-closure(MoveTo(l,d)I e=£ -closure(MoveTo(I,e)I s=£-closure(MoveTo(l,s)I .= £-closure(MoveTo(I,.)A0,1,4,6:B1,7C5,6r D2,6B1,7B1,7D2,6C5,6E7F6D2,6G3,4,7E7E7F6 丁E7G3,4,7G3,4,7C5,6sCFddddEeAddDG7 给文法GS:S aA|bQA aA|bB|bB bD|aQQ aQ|bD|bD bB

11、|aAE aB|bFF bD|aE|b构造相应的最小的DFA解：由于从S岀发任何输入串都不能到达状态E和F,所以，状态E，F为多余的状态，不予考虑。这样，可以写岀文法 GS对应的NFADQnF表由子集法将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后是终

12、态，而1，6，7输入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是否

13、等价由2, 3是否等价决定。由于有(5)即2, 3是否等价由 4, 5是否等价决定，所以有 4, 5等价，2, 3等价,进而6, 7也等价。(7) 删除上表中的第3, 5, 7行，并将剩余行中的 3, 5, 7分别改为对应的等价状态为2, 4, 6有下表：II aIb1S2A2A2A2A4B,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)即:(

14、01|10)*(01|10)为所求的正规式。9将图4.18的DFA最小化，并用正规式描述它所识别的语言：解:aa图 4.18(1)因为6, 7是DFA的终态，其他是非终态,可将状态集分成两个子集:P1=1，2，3, 4, 5，P2=6，7。 由于F(6,b)=F(7,b)=6, 而6，7又没有其他输入，所以6，7等价。(3) 由于 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 等价。(1)由于 F(1,b)=F(2,b)=2,F(1,a)=3,F(2,a)=4,而 3，4 等价，所以 1,2 等价。(2)由于状态5没有输入字符b,所以与1，2，3，4都不等价。综上所述，上图DFA的状态可最细分解为：P=1，2，3，4，5，6，7该DFA用正规式表示为：* * *b a(c|da) bb10 构造下述文法 GS的自动机:S A0A A0|S1|0该自动机是确定的吗？若不确定，则对它确定化。该自动机相应的语言是什么？解：由于该文法的产生式S A0，A A0|S1中没有字符集 Vt的输入，所以不是确定的自动机。要将其他确定化，必