2024年9月16日发(作者：宇绢子)
第4章练习P
72
作业布置：P
72
3，7，9，11
提示1：判断两个正规式是否相等，应判断两个正规式所产生
的正规集是否一样。完成此项任务需要经过四个阶段：
第一，画出正规式的NFA；
第二，由NFA变换到DFA；
第三，将DFA最小化；
第四，画出最小化DFA的有限自动机。
如果要判断的正规式的最小化DFA的有限自动机是一样的，则
正规式等价；反之，则不等价。
提示2：构造正规表达式的最小化的DFA方法是：
首先，按规则将正规表达式用NFA表示；
其次，使用ε-closure(Move())将NFA转变为DFA；
最后使用子集法将DFA最小化。
对于这类题目要多做练习，熟能生巧。
第 1 页 共 9 页
3.将下图确定化：
0
0，1
V
0
S Q
1
1
U
1
1
Z
0，1
0
解：下表由子集法将NFA转换为DFA：
I
A [S]
B [Q,V]
C [Q,U]
D [V,Z]
E [V]
F [Q,U,Z]
G [Z]
I
0
I
1
B [Q,V]
D [V,Z]
E [V]
G [Z]
G [Z]
D [V,Z]
G [Z]
C
1
A
0
1
0
0
D
0
1
F
1
E
0
C [Q,U]
C [Q,U]
F [Q,U,Z]
G [Z]
F [Q,U,Z]
G [Z]
G
0，1
0，1
B
7、给文法G[S]： SaA|bQ
AaA|bB|b
BbD|aQ
第 2 页 共 9 页
QaQ|bD|b
DbB|aA
EaB|bF
FbD|aE|b
构造相应的最小的DFA。
解：由于从S出发任何输入串都不能到达状态E和F，所以，
状态E，F为多余的状态，不予考虑。这样，可以写出文法G[S]对应
的NFA M：
NFA M={k, Σ, f, S, Z}
K={S, A, B, Q, D, Z} S={S} Z={Z}
F(S, a)=A f(S, b)=Q
F(A, a)=A f(A, b)=B
F(B, b)=D f(B, a)=Q
F(Q, a)=Q f(Q, b)=D f(Q,b)=Z
F(D, b)=B f(D, a)=A
NFA M的状态转换图为：
a
a
b
S
a
b
A
b
Z
b
Q
a
a
b
b
B
b
D
f(A,b)=Z
I
b
第 3 页 共 9 页
下表由子集法将NFA转换为DFA：
I I
a
[S]
[A]
[Q]
[B,Z]
[D,Z]
[D]
[B]
S
A
B
C*
D*
E
F
[A]
[A]
[Q]
[Q]
[A]
[A]
[Q]
A
A
B
B
A
A
B
[Q]
[B,Z]
[D,Z]
[D]
[B]
[B]
[D]
B
C
D
E
F
F
E
由上表可知：
(1)因为C、D是DFA的终态，其他是非终态，可将状态集分成
两个子集： P
1
={S, A, B, E, F}，P
2
={C, D}。
(2)因为{A, B}b={C, D}为终态，{S, E, F}b={B, E, F}为非终态，
所以P
1
可划分为：P
11
={S, E, F}，P
12
={A, B}。
(3)因为{S}b={B}，{E, F}b={E, F}，所以S与E、F不等价，P
11
可划分为：P
111
={S}，P
112
={E, F}。
(4)因为{A, B}a={A, B}，{A, B}b={C, D}，即状态A识别b到终
态，状态B也能识别同一个b到终态，则状态A、B等价，不可区
分。
说明：DFA最小化，即将其状态集合分割为一些不相交的状态
子集，并且任意两个不同状态子集中的状态均为可区分的，而同一
状态子集中的状态均为等价的。状态s与状态t的可区分是指状态s
与状态t不等价。而状态s与状态t的等价是指若从状态s出发能识
别某个字α而停于终态，则从t出发也能识别同一个字α而停于终
态；否则就是可区分的。
第 4 页 共 9 页
(5)因为{E, F}a={A, B}，{E, F}b={E, F}，所以E、F等价。
(6)因为{C, D}a={A, B}，{C, D}b={E, F}，所以C、D等价。
(7)综上所述，上图DFA的状态可最细分解为：P={{S}, {A, B},
{C, D}, {E, F}}。删除上表中的第3，5，7行，并将剩余行中的B、
D、F分别改为对应的等价状态为A、C、E有下表：
I
S
A
C*
D
A
A
A
A
这样可得最小化的DFA如下：
I
a
A
C
D
D
I
b
9、将下图的DFA最小化，并用正规式描述它所识别的语言：
1
b
a
c
3
d
c
b
6
5
b
d
a
b
b
7
b
2
a
4
第 5 页 共 9 页
解：
（1）因为6、7是DFA的终态，其他是非终态，可将状态集分
成两个子集：P1={1，2，3，4，5}，P2={6，7}。
（2）因为{6, 7}b={6}，而6、7又没有其他输入，所以6、7等
价。
（3）因为{3, 4}c={3}，{3, 4}d={5}，{3, 4}b={6, 7}，而6，7
等价，所以3、4等价。
（4）因为{1, 2}b={2}，{1, 2}a={3, 4}，而3、4等价，所以1、
2等价。
（5）由于状态5没有输入字符b，所以与1、2、3、4都不等价。
（6）综上所述，上图DFA的状态可最细分解为：P={{1, 2}, {3,
4}, {5}, {6, 7}}。
将状态集合{1, 2}, {3, 4}, {5}, {6, 7}重命名为S、A、B、C，对
应的状态转换矩阵为
S
A
B
C*
a
A
A
b
S
C
C
c
A
D
B
最小化的DFA为：
第 6 页 共 9 页
该DFA用正规式r表示为：
r=b
*
a(c|da)
*
bb*=b
*
a(c|da)
*
b
+
11．有一种用以证明两个正规表达式等价的方法，那就是构造
他们的最小DFA，表明这两个DFA是一样的（除了状态名不同外）。
使用此方法，证明下面的正规表达式是等价的。
（1）(a|b)*
（2）(a*|b*)*
（3）((ε|a)b*)*
解：
（1）正规式转换为NFA
第 7 页 共 9 页
第 8 页 共 9 页
第 9 页 共 9 页
2024年9月16日发(作者：宇绢子)
第4章练习P
72
作业布置：P
72
3，7，9，11
提示1：判断两个正规式是否相等，应判断两个正规式所产生
的正规集是否一样。完成此项任务需要经过四个阶段：
第一，画出正规式的NFA；
第二，由NFA变换到DFA；
第三，将DFA最小化；
第四，画出最小化DFA的有限自动机。
如果要判断的正规式的最小化DFA的有限自动机是一样的，则
正规式等价；反之，则不等价。
提示2：构造正规表达式的最小化的DFA方法是：
首先，按规则将正规表达式用NFA表示；
其次，使用ε-closure(Move())将NFA转变为DFA；
最后使用子集法将DFA最小化。
对于这类题目要多做练习，熟能生巧。
第 1 页 共 9 页
3.将下图确定化：
0
0，1
V
0
S Q
1
1
U
1
1
Z
0，1
0
解：下表由子集法将NFA转换为DFA：
I
A [S]
B [Q,V]
C [Q,U]
D [V,Z]
E [V]
F [Q,U,Z]
G [Z]
I
0
I
1
B [Q,V]
D [V,Z]
E [V]
G [Z]
G [Z]
D [V,Z]
G [Z]
C
1
A
0
1
0
0
D
0
1
F
1
E
0
C [Q,U]
C [Q,U]
F [Q,U,Z]
G [Z]
F [Q,U,Z]
G [Z]
G
0，1
0，1
B
7、给文法G[S]： SaA|bQ
AaA|bB|b
BbD|aQ
第 2 页 共 9 页
QaQ|bD|b
DbB|aA
EaB|bF
FbD|aE|b
构造相应的最小的DFA。
解：由于从S出发任何输入串都不能到达状态E和F，所以，
状态E，F为多余的状态，不予考虑。这样，可以写出文法G[S]对应
的NFA M：
NFA M={k, Σ, f, S, Z}
K={S, A, B, Q, D, Z} S={S} Z={Z}
F(S, a)=A f(S, b)=Q
F(A, a)=A f(A, b)=B
F(B, b)=D f(B, a)=Q
F(Q, a)=Q f(Q, b)=D f(Q,b)=Z
F(D, b)=B f(D, a)=A
NFA M的状态转换图为：
a
a
b
S
a
b
A
b
Z
b
Q
a
a
b
b
B
b
D
f(A,b)=Z
I
b
第 3 页 共 9 页
下表由子集法将NFA转换为DFA：
I I
a
[S]
[A]
[Q]
[B,Z]
[D,Z]
[D]
[B]
S
A
B
C*
D*
E
F
[A]
[A]
[Q]
[Q]
[A]
[A]
[Q]
A
A
B
B
A
A
B
[Q]
[B,Z]
[D,Z]
[D]
[B]
[B]
[D]
B
C
D
E
F
F
E
由上表可知：
(1)因为C、D是DFA的终态，其他是非终态，可将状态集分成
两个子集： P
1
={S, A, B, E, F}，P
2
={C, D}。
(2)因为{A, B}b={C, D}为终态，{S, E, F}b={B, E, F}为非终态，
所以P
1
可划分为：P
11
={S, E, F}，P
12
={A, B}。
(3)因为{S}b={B}，{E, F}b={E, F}，所以S与E、F不等价，P
11
可划分为：P
111
={S}，P
112
={E, F}。
(4)因为{A, B}a={A, B}，{A, B}b={C, D}，即状态A识别b到终
态，状态B也能识别同一个b到终态，则状态A、B等价，不可区
分。
说明：DFA最小化，即将其状态集合分割为一些不相交的状态
子集，并且任意两个不同状态子集中的状态均为可区分的，而同一
状态子集中的状态均为等价的。状态s与状态t的可区分是指状态s
与状态t不等价。而状态s与状态t的等价是指若从状态s出发能识
别某个字α而停于终态，则从t出发也能识别同一个字α而停于终
态；否则就是可区分的。
第 4 页 共 9 页
(5)因为{E, F}a={A, B}，{E, F}b={E, F}，所以E、F等价。
(6)因为{C, D}a={A, B}，{C, D}b={E, F}，所以C、D等价。
(7)综上所述，上图DFA的状态可最细分解为：P={{S}, {A, B},
{C, D}, {E, F}}。删除上表中的第3，5，7行，并将剩余行中的B、
D、F分别改为对应的等价状态为A、C、E有下表：
I
S
A
C*
D
A
A
A
A
这样可得最小化的DFA如下：
I
a
A
C
D
D
I
b
9、将下图的DFA最小化，并用正规式描述它所识别的语言：
1
b
a
c
3
d
c
b
6
5
b
d
a
b
b
7
b
2
a
4
第 5 页 共 9 页
解：
（1）因为6、7是DFA的终态，其他是非终态，可将状态集分
成两个子集：P1={1，2，3，4，5}，P2={6，7}。
（2）因为{6, 7}b={6}，而6、7又没有其他输入，所以6、7等
价。
（3）因为{3, 4}c={3}，{3, 4}d={5}，{3, 4}b={6, 7}，而6，7
等价，所以3、4等价。
（4）因为{1, 2}b={2}，{1, 2}a={3, 4}，而3、4等价，所以1、
2等价。
（5）由于状态5没有输入字符b，所以与1、2、3、4都不等价。
（6）综上所述，上图DFA的状态可最细分解为：P={{1, 2}, {3,
4}, {5}, {6, 7}}。
将状态集合{1, 2}, {3, 4}, {5}, {6, 7}重命名为S、A、B、C，对
应的状态转换矩阵为
S
A
B
C*
a
A
A
b
S
C
C
c
A
D
B
最小化的DFA为：
第 6 页 共 9 页
该DFA用正规式r表示为：
r=b
*
a(c|da)
*
bb*=b
*
a(c|da)
*
b
+
11．有一种用以证明两个正规表达式等价的方法，那就是构造
他们的最小DFA，表明这两个DFA是一样的（除了状态名不同外）。
使用此方法，证明下面的正规表达式是等价的。
（1）(a|b)*
（2）(a*|b*)*
（3）((ε|a)b*)*
解：
（1）正规式转换为NFA
第 7 页 共 9 页
第 8 页 共 9 页
第 9 页 共 9 页