资源描述：
《编译原理第4章答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、编译原理习题解答页9/9第四章词法分析1．构造下列正规式相应的DFA：(1)1(0
2、1)*101(2)1(1010*
3、1(010)*1)*0(3)a((a
4、b)*
5、ab*a)*b(4)b((ab)*
6、bb)*ab解：(1)1(0
7、1)*101对应的NFA为01231104110下表由子集法将NFA转换为DFA：II0=ε-closure(MoveTo(I,0))I1=ε-closure(MoveTo(I,1))A[0]B[1]B[1]B[1]C[1,2]C[1,2]D[1,3]C[1,2]D[1,
8、3]B[1]E[1,4]E[1,4]B[1]B[1]ABCD110E11000,11(2)1(1010*
9、1(010)*1)*0对应的NFA为024511010103610εε7981001εεε1下表由子集法将NFA转换为DFA：编译原理习题解答页9/9II0=ε-closure(MoveTo(I,0))I1=ε-closure(MoveTo(I,1))A[0]B[1,6]B[1,6]C[10]D[2,5,7]C[10]D[2,5,7]E[3,8]B[1,6]E[3,8]F[1,4,6,9]F[
10、1,4,6,9]G[1,2,5,6,9,10]D[2,5,7]G[1,2,5,6,9,10]H[1,3,6,9,10]I[1,2,5,6,7]H[1,3,6,9,10]J[1,6,9,10]K[2,4,5,7]I[1,2,5,6,7]L[3,8,10]I[1,2,5,6,7]J[1,6,9,10]J[1,6,9,10]D[2,5,7]K[2,4,5,7]M[2,3,5,8]B[1,6]L[3,8,10]F[1,4,6,9]M[2,3,5,8]N[3]F[1,4,6,9]N[3]O[4]O[4]P[
11、2,5]P[2,5]N[3]B[1,6]AB1C0D1E01F101H0G1I0K1J10L01M0011NOP011001(3)a((a
12、b)*
13、ab*a)*b(略)(4)b((ab)*
14、bb)*ab(略)2．已知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},构造相应的DFA。xy0z010010解：根据题意有NFA图如下编译原理习题解答页9/
15、9下表由子集法将NFA转换为DFA：II0=ε-closure(MoveTo(I,0))I1=ε-closure(MoveTo(I,1))A[x]B[z]A[x]B[z]C[x,z]D[y]C[x,z]C[x,z]E[x,y]D[y]E[x,y]E[x,y]F[x,y,z]A[x]F[x,y,z]F[x,y,z]E[x,y]01100BCEF00DA1101下面将该DFA最小化：(1)首先将它的状态集分成两个子集：P1={A,D,E},P2={B,C,F}(2)区分P2:由于F(F,1)=F(C,
16、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},P22={B}。(3)区分P1:由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有P11={A,E},P12={D}。(4)由于F(A,0)=B,F(E,0)=F,而B，F不等价，所以A，E可以区分。(5)综上所述，DFA可以区分为P={{A}，{B}，{D}，{E}，{C
17、，F}}。所以最小化的DFA如下：11010F0BE10DA03.将图4.16确定化：S0，1Z1V11U0Q0，1001图4.16解：下表由子集法将NFA转换为DFA：II0=ε-closure(MoveTo(I,0))I1=ε-closure(MoveTo(I,1))A[S]B[Q,V]C[Q,U]B[Q,V]D[V,Z]C[Q,U]C[Q,U]E[V]F[Q,U,Z]编译原理习题解答页9/9D[V,Z]G[Z]G[Z]E[V]G[Z]F[Q,U,Z]D[V,Z]F[Q,U,Z]G[Z]G[Z
18、]G[Z]AGDB0，10C110E010F010，14.把图4.17的(a)和(b)分别确定化和最小化：12435bbbbaaa0abaab01aa,ba(a)(b)解：(a):下表由子集法将NFA转换为DFA：IIa=ε-closure(MoveTo(I,a))Ib=ε-closure(MoveTo(I,b))A[0]B[0,1]C[1]B[0,1]B[0,1]C[1]C[1]A[0]可得图（a1），由于F(A,b)=F(B,b)=C,并且F(A,a)=F(B,a)=B,所以A
