第四章词法分析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为卜表由子集法将NFA转换为DFAI10 = -closure(MoveTo(I,0)I 1 =e -closure(MoveTo(I,1)A0B1B1B1C1,2C1,2D1,3C1,2D1,3B1E1,4E1,4B1B1(2)1(1010I10 = -closure(MoveTo(I,0)I 1 = -closure(MoveTo(I,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,6I000J00略） 略）KMN2.已知 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,DFA0口（0a(a|b) *|ab*a)* b ( (4)b(ab) * | bb) * ab (II o = -closure(MoveTo(I,0)I 1 =e -closure(MoveTo(I,1)A冈BzAxBzCx,zDyCx,zCx,zEx,yDyEx,yEx,yFx,y,zAxFx,y,zFx,y,zEx,y1100AC100E 一.D 01F面将该DFA最小化：(1)首先将它的状态集分成两个子集：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可以区分，有R1=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。所以最小化的DFA如下：3 .将图确定化:0, 0,1解：下表由子集法将 NFA转换为DFAII o = e -closure(MoveTo(I,0)I 1 =e -closure(MoveTo(I,1)1ASBQ,VCQ,UBQ,VDV,ZCQ,UCQ,UEVFQ,U,ZDV,ZGZGZEVGZFQ,U,ZDV,ZFQ,U,ZGZGZGZ(b)B,将原来引向B的引线引向与其等价的状态A,然后删除B所在的行。)(al)确定化的 DFA(b):该图已经是 DFA下面将该 DFA最小化：(6)首先将它的状态集分成两个子集：P尸0,P 2=1,2,3,4,54 .把图的(a)和(b)分别确定化和最小化:(a)解：(a)：IIa = -closure(MoveTo(I,a)I b =e -closure(MoveTo(I,b)A0B0,1C1B0,1B0,1C1C1A0下表由子集法将NFA转换为DFA可得图(al),由于F(A,b)=F(B,b)=C,并且F(A,a)=F(B,a尸B,所以A,B等价，可将 DFA最小化，即：删除A,有图(a2)。(DFA的最小化，也可看作将上表中的B全部替换为(a2)最小化的 DFA(7)区分P2：由于 F(4,a)=0属于终态集，而其他状态输入a后都是非终态集，所以区分B如下：P2i=4,P 22=1,2,3,5。(8)区分P22：由于F(1,b)=F(5,b)=4 属于P21,而F(2,b)与F(3,b)不等于4,即不属于P2i,所以区分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 属于 %,所以 2, 3 可区分。P222区分为 P22212 , P2222G(11)结论：该DFA的状态集可分为：P= 0,1,5,2,3,4 ,其中1,5等价。删去状态5,将原来引向5的引线引向与其等价的状态1,有图(b1) 0b(b1)最小化的DFA5 .构造一个 DFA,它接收2 =0 , 1上所有满足如下条件的字符串：每个 1都有0直接跟在右边。然后再构造 该语言的正则文法。解：根据题意，DFA所对应的正规式应为：(0|(10)。所以，接收该串的NFA如下：0卜表由子集法将NFA转换为DFAI10 = -closure(MoveTo(I,0)I 1 =e -closure(MoveTo(I,1)A0B0,2C1B0,2B0,2C1C1B0,2显然，A, B等价，所以将上述 DFA最小化后有:0对应的正规文法为：GA:A 1C|0A| sC 0A6 .设无符号数的正规式为8 :0 =dd*|dd *.dd *|.dd *|dd *e(s| e )dd *|e(s| e )dd *|.dd *e(s| e )dd*|dd *.dd *e(s| e )dd* 化简 0，画出。的 DFA 其中 d=0,1,2,9,s=+,-解：把原正规式的每2, 3项，4, 5项，6, 7项分别合并后化简有：0 =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|Odd *=(e |d*.|d *( e |.dd *)e(s|Odd *下面构造化简后的0对应的NFA卜表由子集法将NFA转换为DFAII d=e -closure(MoveTo(I,d)I e= -closure(MoveTo(I,e)I s= -closure(MoveTo(I,s)I . = -closure(MoveTo(I,.)A0,1,4,6 B1,7C5,6D2,6B1,7B1,7D2,6C5,6E7r f6D2,6G3,4,7E7E7F6E7G3,4,7G3,4,7C5,67 .给文法GS: S aA|bQ A aA|bB|bB bD|aQ Q aQ|bD|b D bB|aA E aB|bF F bD|aE|b构造相应的最小的 DFA解：由于从S出发任何输入串都不能到达状态E和F,所以，状态E, F为多余的状态，不予考虑。这样，可以写出文法 GS对应的NFAa卜表由子集法将NFA转换为DFAII a = -closure(MoveTo(I,a)I b = -closure(MoveTo(I,b)iS2A3Q2A2A4B,Z3Q3Q5D,Z4B,Z3Q6D5D,Z2A7B6D2A7B7B3Q6D由上表可知：(1)因为4, 5是DFA的终态，其他是非终态，可将状态集分成两个子集：Pi=1 , 2, 3, 6, 7, P2=4, 5(2)在Pi中因为2,3输入b后是终态，而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(4)查看Pii2=6 , 7,由于输入a后为2, 3,所以6, 7是否等价由2, 3是否等价决定。(5)查看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是否等价决定。由于有(5)即2, 3是否等价由 4, 5是否等价决定，所以有 4, 5等价，2, 3等价，进而6, 7也等价。(7)删除上表中的第3, 5, 7行，并将剩余行中的 3, 5, 7分别改为对应的等价状态为2, 4, 6有下表：II aIbiS2A2A2A2A4B,Z4B,Z2A6D6D2A6Dba14