首页 > 美文阅读

编译原理第4章答案

更新时间:2023-07-14 16:11:38 阅读：评论：0

第四章词法分析

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转换为DFA：

I	I0 = ε-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,3]	B[1]	E[1,4]
E[1,4]	B[1]	B[1]

(2)1(1010* | 1(010)* 1)* 0对应的NFA为

下表由子集法将NFA转换为DFA：

I	I0 = ε-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[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[2,5]
P[2,5]	N[3]	B[1,6]

(3)a((a|b)*|ab*a)* 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图如下

下表由子集法将NFA转换为DFA：

刘徽胸闷气短怎么缓解

I	I0 = ε-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]

下面将该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}。

(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.将图确定化：

图

解：下表由子集法将NFA转换为DFA：

I	I0 经常放臭屁= ε-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]
D[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]	G[Z]

4.把图的(a)和(b)分别确定化和最小化：

(a) (b)春风三月

解：

(a):

下表由子集法将NFA转换为DFA：

I	Ia = ε-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,B等价，可将DFA最小化，即：删除B，将原来引向B的引线引向与其等价的状态A，有图(a2)。（DFA的最小化，也可看作将上表中的B全部替换为A，然后删除B所在的行。）

（a1）确定化的DFA （a2）最小化的DFA

（b）:该图已经是DFA。下面将该DFA最小化：

(6) 首先将它的状态集分成两个子集：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)冷菜菜谱。

本文发布于:2023-07-14 16:11:38，感谢您对本站的认可！

本文链接：https://www.wtabcd.cn/fanwen/fan/82/1096403.html

上一篇：LATTICE 非常详细的时序约束(中文教程)

下一篇：编译原理LR分析（主要是LR（0）分析）

标签：终态状态子集

留言与评论（共有 0 条评论）