第四
(1) 1(0|1)101
* *
章 词法分析
1．构造下列正规式相应的DFA：
(2) 1(1010| 1(010)1)0 (3) a((a|b)|aba) b (4) b((ab)| bb)ab 解：
(1)1(0|1)101对应的NFA为
下表转换为
0 1 0 1 1 I A[0] B[1] C[1,2] D[1,3] E[1,4]
0 * * *
(2)1(1010| 1(010)1)0对应的NFA为 A 1 B 1 0 0 ε C ε 1 1 4 0 0,1 1 0 ε 0 7 8 1 9 ε I A[0] C[10] E[3,8] G[1,2,5,6,9,10] H[1,3,6,9,10] J[1,6,9,10] I0 = ε-closure(MoveTo(I,0)) I1 = ε-closure(MoveTo(I,1)) B[1,6] D[2,5,7] B[1,6] F[1,4,6,9] D[2,5,7] I[1,2,5,6,7] K[2,4,5,7] ε 1 5 D 1 E
下表由子
1 6 0 10 集法将NFA转换为DFA：
B[1] D[1,3] B[1] B[1] I0 = ε-closure(MoveTo(I,0)) I1 = ε-closure(MoveTo(I,1)) B[1] C[1,2] C[1,2] E[1,4] B[1] 1 2 0 3 1 4 由子集法将NFADFA：
*
*
*
*
*
*
*
*
0 1 1 1 2 0 3 B[1,6] C[10] D[2,5,7] E[3,8] F[1,4,6,9] G[1,2,5,6,9,10] H[1,3,6,9,10] I[1,2,5,6,7] J[1,6,9,10] K[2,4,5,7] L[3,8,10] M[2,3,5,8] N[3] O[4] P[2,5] L[3,8,10] J[1,6,9,10] M[2,3,5,8] N[3] P[2,5] N[3] I[1,2,5,6,7] D[2,5,7] B[1,6] F[1,4,6,9] F[1,4,6,9] O[4] B[1,6] 1 1 A 1 B 0 C 1 G 1 D 0 1 E 1 F 0 1 1 0 I 1 0 1 H 0 L 0 K 0 J 0 0 M 1 1 P 0 O 0 1 N
*
*
*
*
*
(3)a((a|b)|aba) b (略) (4)b((ab)| 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。 解：根据题意有NFA图如下
0 下表由子集法将NFA1 转换为DFA： A[x] B[z] C[x,z] D[y] E[x,y] F[x,y,z]
下面将该DFA最小化：
(1) 首先将它的状态集分成两个子集：P1={A,D,E},P2={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},P22={B}。
1 A 0
B
0 I x 0 z 0 0 1 I0 = ε-closure(MoveTo(I,0)) y B[z] C[x,z] C[x,z] E[x,y] F[x,y,z] F[x,y,z] 0
1 C
0 D 1
1 0
I1 = ε-closure(MoveTo(I,1)) A[x] D[y] E[x,y] A[x] E[x,y] 0 1
0 F
E (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，F}}。所以最小化的DFA如下：
3.将图4.16确定化：
0 解：下表由子集法将NFA转换为DFA： I A[S] B[Q,V] C[Q,U] D[V,Z] E[V] F[Q,U,Z] G[Z]
4.把图4.17别确定化和最
a A 1 1 C S V 图4.16 0 0 I1 = ε-closure(MoveTo(I,1)) 0，1 Z C[Q,U] C[Q,U] 1 U 1 F[Q,U,Z] G[Z] F[Q,U,Z] G[Z] 0 1 F 1 b 0，1 a b 4 b E 的(a)和(b)分小化：
G 2 b b 5 a 0，1 b 3 a (b)
A 1 0 B 1 1 D 0 0 E 1 0 F 0 I= ε-closure(MoveTo(I,0)) 0，0 1 B[Q,V] Q 1 D[V,Z] E[V] G[Z] 1 G[Z] D[V,Z] G[Z] 0 0 0 a,b (a) 0 0 解： 1 B 0 a D a (a): a 下表由1 法将NFA转换为DFA： a I A[0] B[0,1] C[1]
B[0,1] B[0,1] A[0] 子集
Ia = ε-closure(MoveTo(I,a)) Ib = ε-closure(MoveTo(I,b)) C[1] C[1] 可得图（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所在的行。） （a1）确（a2）最（b）:下面将
A b a C a B b a
定化的小化的该图已该DFA
b A a C a
DFA 经是DFA。最小化：
(6) 首
DFA
先将它的状态集分成两个子集：P1={0},P2={1,2,3,4,5}
(7) 区分P2：由于F(4,a)=0属于终态集，而其他状态输入a后都是非终态集，所以区分P2如下：
P21={4},P22={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},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属于P222,所以2，3可区分。P222区分为P2221{2}，
P2222{3}。
(11) 结论：该DFA的状态集可分为：P={ {0},{1,5},{2},{3},{4} },其中1,5等价。删去状态5，将原
来引向5的引线引向与其等价的状态1，有图(b1)。 (b1)最小化的DFA
5．构造一个DFA，它接收Σ条件的字符串：每个1都有0构造该语言的正则文法。 解：根据题意，DFA所对应(0|(10))。所以，接收该串
I A[0] B[0,2] C[1]
对应的正规文法为： G[A]：
A?1C|0A|ε C?0A
6．设无符号数的正规式为θ：
θ=dd|dd.dd|.dd|dde(s|ε)dd|e(s|ε)dd|.dde(s|ε)dd|dd.dde(s|ε)dd
*
*
*
*
*
*
*
*
*
*
*
*
*
0 a a 1 b b 2 b a 3 ={0，1}上所有满足如下a 直接跟在右边。然后再
的正规式应为：
4 0 2 的NFA如下：
b a ε b 1 0 0 1 下表由子集法将NFA转换为DFA：
I0 = ε-closure(MoveTo(I,0)) B[0,2] B[0,2] B[0,2] 1 0 I1 = ε-closure(MoveTo(I,1)) C[1] C[1] 1 C A 显然，A，B等价，所以将上述DFA最小化后有： 0 A 1 0 0 C B 0
化简θ,画出θ的DFA，其中d={0,1,2,…9},s={+,-}
解：把原正规式的每2，3项，4，5项，6，7项分别合并后化简有：
θ=dd|d.dd|de(s|ε)dd|d.dde(s|ε)dd=dd|d.dd|(d|d.dd)e(s|ε)dd=(ε|d.|(d|d.dd)e(s|ε))dd
*
*
*
*
*
*
*
* *
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
=(ε|d.|d(ε|.dd)e(s|ε))dd
下面构应的
0
d 1 . 2 d ε d 3 ε . 4 ε e 5 ε s 6 d d 7 造化简后的θ对NFA：
相关推荐：
loading