编译原理第4章答案.docx
- 文档编号:2551243
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:9
- 大小:229.36KB
编译原理第4章答案.docx
《编译原理第4章答案.docx》由会员分享,可在线阅读,更多相关《编译原理第4章答案.docx(9页珍藏版)》请在冰点文库上搜索。
第四章 词法分析
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为
0
1
1
0
1
0
1
2
3
4
1
下表由子集法将
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]
0
0
1
1
0
1
A
B
C
D
E
1
1
0,1
(2)1(1010*|1(010)*1)*0对应的NFA为
ε
ε
1
1
0
1
0
1
0
0
1
2
3
4
5
6
1
0
1
ε
ε
0
0
1
9
7
8
ε
下表由子集法将 NFA转换为DFA:
I
I
=
ε-closure(MoveTo(I,0))
I
1
=ε-closure(MoveTo(I,1))
0
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]
1
L
1
1
1
1
0
0
1
1
0
1
0
B
I
K
A
D
E
F
M
0
0
1
1
0
0
0
C
1
1
G
H
J
0
1
0
1
N
P
O
0
(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图如下
0
1
0
x y
0
1
0 z
0
下表由子集法将
NFA转换为DFA:
I
I
=ε-closure(MoveTo(I,0))
I
1=ε-closure(MoveTo(I,1))
0
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]
1
1
0
0
0
0
0
A
B
C
D
E
F
0
1
1
1
下面将该DFA最小化:
(1)
首先将它的状态集分成两个子集:
P={A,D,E},P={B,C,F}
1
2
(2)
区分P:
由于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,
2
而D,E不等价(见下步),从而B与C,F可以区分。
有
P={C,F},P={B}。
21
22
(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如下:
1
1
1
1
0
0
0
0
A
B
D
E
F
0
3.将图确定化:
0
V
0
0
0,1
1
0,1
S
Q
Z
1
1
U
1
图
解:
下表由子集法将
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]
C
0
E
0
1
1
A
1
F
1
G
0,1
0
0
0,1
0
B
D
4.把图的(a)和(b)分别确定化和最小化:
b
b
0
2
3
a
a
a,b
b
a
0
1
a
a
b
a
1
4
5
b
a
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所在的行。
)
B
a
a
a
b
C
A
b
A
b
C
a
a
(a1)确定化的DFA
(a2)最小化的DFA
(b):
该图已经是DFA。
下面将该
DFA最小化:
(6)
首先将它的状态集分成两个子集:
P1={0},P2={1,2,3,4,5}
(7)
区分P:
由于F(4,a)=0
属于终态集,而其他状态输入
a
后都是非终态集,所以区分
P
如下:
2
2
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)
区分P:
由于F(1,b)=F(5,b)=4,即F(1,a)=1,F(5,a)=5,所以1,5
等价。
221
(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)。
b
b
0
2
3
b
a
a
a
a
1
b
4
a
b
(b1)最小化的DFA
5.构造一个DFA,它接收Σ={0,1}上所有满足如下条件的字符串:
每个
1都有0直接跟在右边。
然后再构造该
语言的正则文法。
解:
根据题意,DFA所对应的正规式应为:
(0|(10))*。
所以,接收该串的
NFA如下:
ε
1
1
0
0
2
下表由子集法将NFA转换为DFA:
0
I
I
=ε-closure(MoveTo(I,0))
I
1=ε-closure(MoveTo(I,1))
0
A[0]
B[0,2]
C[1]
B[0,2]
B[0,2]
C[1]
C[1]
B[0,2]
1
A
1
C
0
0
B
0
显然,A,B等价,所以将上述
DFA最小化后有:
0
A
1
C
0
对应的正规文法为:
G[A]:
A1C|0A|ε
C0A
6.设无符号数的正规式为θ:
θ=dd*|dd*.dd*|.dd*|dd*e(s|ε)dd*|e(s|ε)dd*|.dd*e(s|ε)dd*|dd*.dd*e(s|ε)dd*
化简θ,画出θ的解:
把原正规式的每
DFA,其中d={0,1,2, ⋯9},s={+,-
2,3项,4,5项,6,7项分别合并后化简有:
θ=dd*|d*.dd*|d*e(s|ε)dd*|d*.dd*e(s|ε)dd*=dd*|d*.dd*|(d*|d*.dd*)e(s|ε)dd*
=(ε|d*.|(d*|d*.dd*)e(s|ε))dd*
=(ε|d*.|d*(ε|.dd*)e(s|ε))dd*
下面构造化简后的θ对应的 NFA:
0
ε
d
.
d
1
ε
e
ε
6
d
4
5
7
.
d
s
d
ε
3
2
下表由子集法将
NFA转换为DFA:
I
Id=ε-closure(MoveTo(I,d))
Ie=ε-closure(MoveTo(I,e))
Is=ε-closure(MoveTo(I,s))
A[0,1,4,6]
B[1,7]
C[5,6]
B[1,7]
B[1,7]
C[5,6]
E[7]
F[6]
D[2,6]
G[3,4,7]
E[7]
E[7]
F[6]
E[7]
G[3,4,7]
G[3,4,7]
C[5,6]
C
s
F
e
d
d
d
A
d
e
E
d
B
.
.
I.=ε-closure(MoveTo(I,.))
D[2,6]
D[2,6]
D
d
d
G
7.给文法 G[S]:
SaA|bQ
AaA|bB|b
BbD|aQ
QaQ|bD|b
DbB|aA
EaB|bF
FbD|aE|b
构造相应的最小的DFA。
解:
由于从S出发任何输入串都不能到达状态
E和F,所以,状态
E,F为多余的状态,不予考虑。
这样,可以
写出文法G[S]对应的NFA:
a
a
b
S
a
b
b
D
A
B
b
b
Z
a
b
b
Q
a
下表由子集法将
NFA转换为DFA:
I
Ia=ε-closure(MoveTo(I,a))
Ib=ε-closure(MoveTo(I,b))
1[S]
2[A]
3[Q]
2[A]
2[A]
4[B,Z]
3[Q]
3[Q]
5[D,Z]
4[B,Z]
3[Q]
6[D]
5[D,Z]
2[A]
7[B]
6[D]
2[A]
7[B]
7[B]
3[Q]
6[D]
由上表可知:
(1)因为4,5是DFA的终态,其他是非终态,可将状态集分成两个子集:
1
2
P={1,2,3,
6,7},P={4,5}
(2)在P1中因为2,3输入b后是终态,而
1,6,7输入b后是非终态,所以
P1可区分为:
P11={1,6,7},P12={2,3}
(3)在P11中由于1输入b后为3,6输入b后为7,而3,7分属P11和P12,所以1与6不等价,同理,1与7不等价。
所以P11可区分为:
P111={1},P112={6,7}
(4)查看P={6,7},由于输入a后为
2,3,所以6,7是否等价由
2,3是否等价决定。
112
(5)查看P12={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有下表:
I
I
a
I
b
1[S]
2[A]
2[A]
2[A]
2[A]
4[B,Z]
4[B,Z]
2[A]
6[D]
6[D]
2[A]
6[D]
这样可得最小化的 DFA如下:
a
1
a
b
2
4
a
b
a
b
6
b
8.给出下述文法所对应的正规式:
S0A|1B
A1S|1
B0S|0
解:
把后两个产生式代入第一个产生式有:
S=01|01S
S=10|10S
有:
S=01S|10S|01|10=(01|10)S|(01|10)=(01|10)
*(01|10)
即:
(01|10)*(01|10)为所求的正规式。
9.将图的 DFA最小化,并用正规式描述它所识别的语言:
c
a b
1 3 6 b
d
b c
5
d b
a
a b
2 4 7
b
图
解:
(1)
因为6,7是DFA的终态,其他是非终态,可将状态集分成两个子集:
P1={1,2,3,4,5},P2={6,
7}。
(2)
由于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等价。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 答案