资源描述
!-
第四章 词法分析
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
2
3
1
1
0
4
1
1
0
下表由子集法将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]
A
B
C
D
1
1
0
E
1
1
0
0
0,1
1
(2)1(1010* | 1(010)* 1)* 0对应的NFA为
0
2
4
5
1
1
0
10
1
0
3
6
1
0
ε
ε
7
9
8
1
0
0
1
ε
ε
ε
1
下表由子集法将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]
A
B
1
C
0
D
1
E
0
1
F
1
0
1
H
0
G
1
I
0
K
1
J
1
0
L
0
1
M
0
0
1
1
N
O
P
0
1
1
0
0
1
(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。
x
y
0
z
0
1
0
0
1
0
解：根据题意有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]
0
1
1
0
0
B
C
E
F
0
0
D
A
1
1
0
1
下面将该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如下：
1
1
0
1
0
F
0
B
E
1
0
D
A
0
3.将图4.16确定化：
S
0，1
Z
1
V
1
1
U
0
Q
0，1
0
0
1
图4.16
解：下表由子集法将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]
A
G
D
B
0，1
0
C
1
1
0
E
0
1
0
F
0
1
0，1
4.把图4.17的(a)和(b)分别确定化和最小化：
1
2
4
3
5
b
b
b
b
a
a
a
0
a
b
a
a
b
0
1
a
a,b
a
(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所在的行。）
A
a
b
C
a
B
b
a
A
b
C
a
a
（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}。
1
2
4
3
b
b
a
a
0
a
b
a
a
b
b
(11) 结论：该DFA的状态集可分为：P={ {0},{1,5},{2},{3},{4} },其中1,5等价。删去状态5，将原来引向5的引线引向与其等价的状态1，有图(b1)。
(b1)最小化的DFA
5．构造一个DFA，它接收Σ={0，1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。然后再构造该语言的正则文法。
解：根据题意，DFA所对应的正规式应为：(0|(10))*。所以，接收该串的NFA如下：
ε
0
1
2
1
0
0
下表由子集法将NFA转换为DFA：
I
I0 = ε-closure(MoveTo(I,0))
I1 = ε-closure(MoveTo(I,1))
A[0]
B[0,2]
C[1]
B[0,2]
B[0,2]
C[1]
C[1]
B[0,2]
1
1
0
0
0
B
C
A
显然，A，B等价，所以将上述DFA最小化后有：
0
C
1
A
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：
5
ε
7
e
d
4
2
1
.
3
d
d
ε
6
ε
s
d
d
.
0
ε
下表由子集法将NFA转换为DFA：
I
Id =ε-closure(MoveTo(I,d))
Ie=ε-closure(MoveTo(I,e))
Is=ε-closure(MoveTo(I,s))
I.=ε-closure(MoveTo(I,.))
A[0,1,4,6]
B[1,7]
C[5,6]
D[2,6]
B[1,7]
B[1,7]
D[2,6]
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]
E
D
.
d
d
C
G
d
B
d
.
A
e
e
s
F
d
d
d
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
Z
S
A
D
Q
B
b
b
b
a
b
a
b
b
b
a
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的终态，其他是非终态，可将状态集分成两个子集：
P1={1，2，3，6，7}，P2={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)查看P112={6，7}，由于输入a后为2，3，所以6，7是否等价由2，3是否等价决定。
(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
Ia
Ib
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
4
1
b
2
a
a
a
b
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．将图4.18的DFA最小化，并用正规式描述它所识别的语言：
a
7
2
b
c
b
d
b
1
3
4
c
6
a
a
b
b
d
5
b
图 4.18
解：
(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等价。
(2) 由于状态5没有输入字符b,所以与1，2，3，4都不等价。
(3) 综上所述，上图DFA的状态可最细分解为：P={{1，2}，{3，4}，{5}，{6，7}}。
a
b
b
1
3
c
6
b
d
5
a
该DFA用正规式表示为：
b*a(c|da)*bb*
10．构造下述文法G[S]的自动机：
SA0
AA0|S1|0
该自动机是确定的吗？若不确定，则对它确定化。该自动机相应的语言是什么？
解：
由于该文法的产生式SA0，AA0|S1中没有字符集VT的输入，所以不是确定的自动机。要将其他确定化，必须先用代入法得到它对应的正规式。把SA0代入产生式AS1有：A=A0|A01|0=A(0|01)|0=0(0|01)*。代入SA0有该文法的正规式：0(0|01)*0，所以，改写该文法为确定的自动机为：
0
W
X
0
Z
0
0
Y
1
由于状态A有3次输入0的重复输入，所以上图只是NFA，下面将它确定化：
下表由子集法将NFA转换为DFA：
I
I0 = ε-closure(MoveTo(I,0))
Ib = ε-closure(MoveTo(I,1))
A[W]
B[X]
B[X]
C[X,Y,Z]
C[X,Y,Z]
C[X,Y,Z]
B[X]
1
0
0
C
B
A
0
由上表可知DFA为：
展开阅读全文
相关搜索