《编译原理（第三版）》陈意云著
第 二 章 课 后 习 题
T 2.3
叙述由下列正规式描述的语言
0 ( 0 ∣ 1 ) ∗ 0 \space\space0\space\space(\space\space 0\space\space |\space\space 1\space\space)^{\space*\space\space}0 0 ( 0 ∣ 1 ) ∗ 0正规式规定开头和结尾必须包括0，中间由0或1的闭包构成，可以看出该正规式描述的语言包含的串长度至少为2，所以总结为：以0开头和结尾的长度至少是2的串01.( ( ε ∣ 0 ) 1 ∗ ) ∗ \space\space(\space\space (\space\space \varepsilon\space\space|\space\space0\space\space)\space\space1^{\space*\space\space}) ^{\space*} ( ( ε ∣ 0 ) 1 ∗ ) ∗内层括号中是对空和0的选择，再与外面的1的闭包相连接，可能构成的串有： ε \varepsilon ε、 1 1 1、 1...1 1...1 1...1 、 0 0 0、 01 01 01、 01...1 01...1 01...1，再加上外层的闭包，可以让 0 0 0 的个数变成任意多且可以为空串的闭包，所以总结为：所有的01串（包含空串）.( 0 ∣ 1 ) ∗ 0 ( 0 ∣ 1 ) ( 0 ∣ 1 ) \space\space(\space\space0\space\space|\space\space1\space\space)^{\space*\space\space}0\space\space(\space\space0\space\space|\space\space1\space\space)\space\space(\space\space0\space\space|\space\space1\space\space) ( 0 ∣ 1 ) ∗ 0 ( 0 ∣ 1 ) ( 0 ∣ 1 ) 0 ( 0 ∣ 1 ) ( 0 ∣ 1 ) 0\space\space(\space\space0\space\space|\space\space1\space\space)\space\space(\space\space0\space\space|\space\space1\space\space) 0 ( 0 ∣ 1 ) ( 0 ∣ 1 )描述了长度为3，第一位为0的01串，在前面加上0或1的闭包使得串可以以任意二进制或空开头，所以结论为：至少包括三位且倒数第三位是0的01串.0 ∗ 10 ∗ 10 ∗ 10 ∗ \space\space0\space^*\space10\space^*\space10\space^*\space10\space^* 0 ∗ 10 ∗ 10 ∗ 10 ∗三个1是必然存在于串中的，而剩下0的闭包则说明0的个数为任意多，所以结论为：含有三个1的01串.( 00 ∣ 11 ) ∗ ( ( 01 ∣ 10 ) ( 00 ∣ 11 ) ∗ ( 01 ∣ 10 ) ( 00 ∣ 11 ) ∗ ) ∗ \space\space(\space\space00\space\space|\space\space11\space\space)\space^*\space\space(\space\space(\space\space01\space\space|\space\space10\space\space)\space\space(\space\space00\space\space|\space\space11\space\space)\space^*\space\space(\space\space01\space\space|\space\space10\space\space)\space\space(\space\space00\space\space|\space\space11\space\space)\space^*\space\space)\space^* ( 00 ∣ 11 ) ∗ ( ( 01 ∣ 10 ) ( 00 ∣ 11 ) ∗ ( 01 ∣ 10 ) ( 00 ∣ 11 ) ∗ ) ∗第一个闭包可以选择00或11，后面的两个内层闭包所描述的语言与第一个闭包相同，外层闭包让其内部的串可以出现任意次。由于该正规式过于复杂，所以可以将其描述的语言简单概括为：含有偶数（含0个）个0和偶数（含0个）个1的01串.
T 2.4
为下列语言写出正规定义
- 包含5个元音的所有字母串，其中每个元音只出现一次且按顺序排列。不含五个元音的任意字符： [ B − D F − H J − N P − T V − Z b − d f − h j − n p − t v − z ] [B-DF-HJ-NP-TV-Zb-df-hj-np-tv-z] [B−DF−HJ−NP−TV−Zb−df−hj−np−tv−z]，记为 α \alpha α故， α ∗ ( a ∣ A ) α ∗ ( e ∣ E ) α ∗ ( i ∣ I ) α ∗ ( o ∣ O ) α ∗ ( u ∣ U ) α ∗ \alpha\space^\space\space(\space\space a\space\space|\space\space A\space\space)\space\space\alpha\space^\space\space(\space\space e\space\space|\space\space E\space\space)\space\space\alpha\space^\space\space(\space\space i\space\space|\space\space I\space\space)\space\space\alpha\space^\space\space(\space\space o\space\space|\space\space O)\space\space\alpha\space^\space\space(\space\space u\space\space|\space\space U\space\space)\space\space \alpha\space^ α ∗ ( a ∣ A ) α ∗ ( e ∣ E ) α ∗ ( i ∣ I ) α ∗ ( o ∣ O) α ∗ ( u ∣ U ) α ∗
- 按词典序排列的所有字母串。 A ∗ a ∗ B ∗ b ∗ . . . Z ∗ z ∗ A\space^\space\space a\space^\space\space B\space^\space\space b\space^\space\space...\space\space Z\space^\space\space z\space^ A ∗ a ∗ B ∗ b ∗ ... Z ∗ z ∗
- 某语言的注释，它是以 / ∗ /* /∗开始并以 ∗ / / ∗/结束的任意字符串，但它的任何前缀（本身除外）不以 ∗ / / ∗/结尾。不含 / / /， ∗ * ∗的任意字符记为 α \alpha α不含 ∗ / / ∗/的任意字符串可以表示为 ( ∗ ∗ α + / ∗ ) ∗ (^\alpha^+/^)^ (∗∗α+/∗)∗故， / ∗ ( ∗ ∗ α + / ∗ ) ∗ ∗ / /(^\alpha^+/^*)^**/ /∗(∗∗α+/∗)∗∗/
- 相邻数字都不相同的所有数字串。
- 最多只有一处相邻数字相同的所有数字串。
- 由偶数个0和偶数个1组成的所有01串。 ( 00 ∣ 11 ) ∗ ( ( 01 ∣ 10 ) ( 00 ∣ 11 ) ∗ ( 01 ∣ 10 ) ( 00 ∣ 11 ) ∗ ) ∗ (\space\space00\space\space|\space\space11\space\space)\space^\space\space(\space\space(\space\space01\space\space|\space\space10\space\space)\space\space(\space\space00\space\space|\space\space11\space\space)\space^\space\space(\space\space01\space\space|\space\space10\space\space)\space\space(\space\space00\space\space|\space\space11\space\space)\space^\space\space)\space^ ( 00 ∣ 11 ) ∗ ( ( 01 ∣ 10 ) ( 00 ∣ 11 ) ∗ ( 01 ∣ 10 ) ( 00 ∣ 11 ) ∗ ) ∗
- 由偶数个0和奇数个1组成的所有01串。 1 ( 00 ∣ 11 ) ∗ ( ( 01 ∣ 10 ) ( 00 ∣ 11 ) ∗ ( 01 ∣ 10 ) ( 00 ∣ 11 ) ∗ ) ∗ 1\space\space(\space\space00\space\space|\space\space11\space\space)\space^\space\space(\space\space(\space\space01\space\space|\space\space10\space\space)\space\space(\space\space00\space\space|\space\space11\space\space)\space^\space\space(\space\space01\space\space|\space\space10\space\space)\space\space(\space\space00\space\space|\space\space11\space\space)\space^\space\space)\space^ 1 ( 00 ∣ 11 ) ∗ ( ( 01 ∣ 10 ) ( 00 ∣ 11 ) ∗ ( 01 ∣ 10 ) ( 00 ∣ 11 ) ∗ ) ∗
- 不含字串011的01串。 ( 1 ∗ ( 0 + 1 ) ∗ ) 0 ∗ (\space\space1\space^\space\space(\space\space 0\space^+\space\space1\space\space)\space^\space\space)\space\space0\space^* ( 1 ∗ ( 0 + 1 ) ∗ ) 0 ∗
- 字母表 { a , b } {a, b} {a,b}上， a a a不会相邻出现的所有串。 b ∗ ( a ? b + ) ∗ a ? b\space^\space\space(\space\space a\space?\space\space b\space^+\space\space)\space^\space\space a\space? b ∗ ( a ? b + ) ∗ a ?
T 2.7
**用算法 2.4 为下列正规式构造不确定有限自动机，给出它们处理输入串
a
b
a
b
b
a
b
ababbab
ababbab 的状态转化序列**
( a ∣ b ) ∗ (\space\space a\space\space|\space\space b\space\space)\space^* ( a ∣ b ) ∗
方式一：（算法 2.4）
a
b
a
b
b
a
b
:
s
→
0
→
1
→
3
→
5
→
0
→
2
→
4
→
5
→
0
→
1
→
3
→
5
→
0
→
2
→
4
→
5
→
0
→
2
→
4
→
5
→
0
→
1
→
3
→
5
→
0
→
2
→
4
→
5
→
f
ababbab\space\space :\space\space s\rightarrow0\rightarrow1\rightarrow3\rightarrow5\rightarrow0\rightarrow2\rightarrow4\rightarrow5\rightarrow0\rightarrow1\rightarrow3\rightarrow5\rightarrow0\rightarrow2\\\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\rightarrow4\rightarrow5\rightarrow0\rightarrow2\rightarrow4\rightarrow5\rightarrow0\rightarrow1\rightarrow3\rightarrow5\rightarrow0\rightarrow2\rightarrow4\rightarrow5\rightarrow f
ababbab : s→0→1→3→5→0→2→4→5→0→1→3→5→0→2 →4→5→0→2→4→5→0→1→3→5→0→2→4→5→f
方式二：（分裂法）
a
b
a
b
b
a
b
:
s
→
0
→
1
→
0
→
1
→
0
→
1
→
0
→
1
→
0
→
1
→
0
→
1
→
0
→
1
→
f
ababbab\space\space :\space\space s\rightarrow0\rightarrow1\rightarrow0\rightarrow1\rightarrow0\rightarrow1\rightarrow0\rightarrow1\rightarrow0\rightarrow1\rightarrow0\rightarrow1\rightarrow0\rightarrow1\rightarrow f
ababbab : s→0→1→0→1→0→1→0→1→0→1→0→1→0→1→f
方式三：
a
b
a
b
b
a
b
:
s
→
0
→
0
→
0
→
0
→
0
→
0
→
0
→
0
→
f
ababbab\space\space :\space\space s\rightarrow0\rightarrow0\rightarrow0\rightarrow0\rightarrow0\rightarrow0\rightarrow0\rightarrow0\rightarrow f
ababbab : s→0→0→0→0→0→0→0→0→f
( a ∗ ∣ b ∗ ) ∗ (\space\space a\space^*\space\space|\space\space b\space^*\space\space)\space^* ( a ∗ ∣ b ∗ ) ∗
a
b
a
b
b
a
b
:
s
→
0
→
1
→
3
→
5
→
0
→
2
→
4
→
5
→
0
→
1
→
3
→
5
→
0
→
2
→
4
→
2
→
4
→
5
→
0
→
1
→
3
→
5
→
0
→
2
→
4
→
4
→
f
ababbab\space\space :\space\space s\rightarrow0\rightarrow1\rightarrow3\rightarrow5\rightarrow0\rightarrow2\rightarrow4\rightarrow5\rightarrow0\rightarrow1\rightarrow3\rightarrow5\rightarrow0\\\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\rightarrow2\rightarrow4\rightarrow2\rightarrow4\rightarrow5\rightarrow0\rightarrow1\rightarrow3\rightarrow5\rightarrow0\rightarrow2\rightarrow4\rightarrow4\rightarrow f
ababbab : s→0→1→3→5→0→2→4→5→0→1→3→5→0 →2→4→2→4→5→0→1→3→5→0→2→4→4→f
( ( ε ∣ a ) b ∗ ) ∗ (\space\space(\space\space \varepsilon\space\space |\space\space a\space\space)\space\space b\space^*\space\space)\space^* ( ( ε ∣ a ) b ∗ ) ∗
a
b
a
b
b
a
b
:
s
→
0
→
1
→
3
→
5
→
6
→
7
→
8
→
0
→
1
→
3
→
5
→
6
→
7
→
6
→
7
→
8
→
0
→
1
→
3
→
5
→
6
→
7
→
8
→
f
ababbab\space\space :\space\space s\rightarrow0\rightarrow1\rightarrow3\rightarrow5\rightarrow6\rightarrow7\rightarrow8\rightarrow0\rightarrow1\rightarrow3\rightarrow5\rightarrow6\\\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\rightarrow7\rightarrow6\rightarrow7\rightarrow8\rightarrow0\rightarrow1\rightarrow3\rightarrow5\rightarrow6\rightarrow7\rightarrow8\rightarrow f
ababbab : s→0→1→3→5→6→7→8→0→1→3→5→6 →7→6→7→8→0→1→3→5→6→7→8→f
( a ∣ b ) ∗ a b b ( a ∣ b ) ∗ (\space\space a \space\space | \space\space b\space\space) \space^*\space\space a\space\space b\space\space b\space\space(\space\space a \space\space | \space\space b \space\space)\space^* ( a ∣ b ) ∗ a b b ( a ∣ b ) ∗
a
b
a
b
b
a
b
:
s
→
0
→
1
→
3
→
5
→
6
→
7
→
8
→
9
→
10
→
11
→
13
→
15
→
10
→
12
→
14
→
15
→
f
ababbab\space\space :\space\space s\rightarrow0\rightarrow1\rightarrow3\rightarrow5\rightarrow6\rightarrow7\rightarrow8\rightarrow9\rightarrow10\rightarrow11\rightarrow13\rightarrow15\rightarrow10\rightarrow12\rightarrow14\rightarrow15\rightarrow f
ababbab : s→0→1→3→5→6→7→8→9→10→11→13→15→10→12→14→15→f
T 2.8
**用算法2.2把习题2.7中的第三问的NFA变换成DFA。给出它们处理输入串
a
b
a
b
b
a
b
ababbab
ababbab 的状态转换序列**
为了书写的方便，将上面 NFA 中的状态重新编号，得到下图：
上图的 NFA 等价的 DFA 的开始状态是
ε
−
c
l
o
s
u
r
e
(
0
)
\varepsilon-closure(0)
ε−closure(0)，记为
A
=
{
0
,
1
,
2
,
4
,
5
,
6
,
7
,
9
,
10
}
A=\{0,1,2,4,5,6,7,9,10\}
A={0,1,2,4,5,6,7,9,10}；
输入字母表是
{
a
,
b
}
\{a,b\}
{a,b} ，计算
ε
−
c
l
o
s
u
r
e
(
m
o
v
e
(
A
,
a
)
)
\varepsilon-closure(move(A,a))
ε−closure(move(A,a))，由于只有状态
2
2
2 能发生
a
a
a 转换，所以
m
o
v
e
(
A
,
a
)
=
{
3
}
move (A, a)=\{3\}
move(A,a)={3}，故
ε
−
c
l
o
s
u
r
e
(
m
o
v
e
(
A
,
a
)
)
=
ε
−
c
l
o
s
u
r
e
(
{
3
}
)
=
ε
−
c
l
o
s
u
r
e
(
3
)
=
{
1
,
2
,
3
,
4
,
5
,
6
,
7
,
9
,
10
}
\varepsilon-closure(move(A,a))=\varepsilon-closure(\{3\})=\varepsilon-closure(3)=\{1,2,3,4,5,6,7,9,10\}
ε−closure(move(A,a))=ε−closure({3})=ε−closure(3)={1,2,3,4,5,6,7,9,10}，称该集合为
B
B
B；
计算
ε
−
c
l
o
s
u
r
e
(
m
o
v
e
(
A
,
b
)
)
\varepsilon-closure(move(A,b))
ε−closure(move(A,b))，由于只有状态
7
7
7 能发生
b
b
b 转换，所以
m
o
v
e
(
A
,
b
)
=
8
move(A, b)={8}
move(A,b)=8，故
ε
−
c
l
o
s
u
r
e
(
m
o
v
e
(
A
,
b
)
)
=
ε
−
c
l
o
s
u
r
e
(
{
8
}
)
=
ε
−
c
l
o
s
u
r
e
(
8
)
=
{
1
,
2
,
4
,
5
,
6
,
7
,
8
,
9
,
10
}
\varepsilon-closure(move(A,b))=\varepsilon-closure(\{8\})=\varepsilon-closure(8)=\{1,2,4,5,6,7,8,9,10\}
ε−closure(move(A,b))=ε−closure({8})=ε−closure(8)={1,2,4,5,6,7,8,9,10}，称该集合为
C
C
C；
对新集合
B
B
B 和
C
C
C 重复上面的过程可以得到完整的转换表如下：
状态输入符号abABCBBCCBC
根据转换表得到等价的 DFA 如下：
a
b
a
b
b
a
b
:
A
→
B
→
C
→
B
→
C
→
C
→
B
→
C
ababbab\space\space :\space\space A\rightarrow B \rightarrow C \rightarrow B \rightarrow C \rightarrow C \rightarrow B \rightarrow C
ababbab : A→B→C→B→C→C→B→C
T 2.11
**可以从正规式的最简 DFA 同构来证明两个正规式等价。使用这种计数，证明正规式
(
a
∣
b
)
∗
(\space\space a\space\space|\space\space b\space\space)\space^*
( a ∣ b ) ∗、
(
a
∗
∣
b
∗
)
∗
(\space\space a\space^*\space\space|\space\space b\space^*\space\space)\space^*
( a ∗ ∣ b ∗ ) ∗ 和
(
(
ε
∣
a
)
b
∗
)
∗
(\space\space(\space\space \varepsilon\space\space |\space\space a\space\space)\space\space b\space^*\space\space)\space^*
( ( ε ∣ a ) b ∗ ) ∗ 等价**
与 T 2.8 类似，先将上面的 NFA 中的状态重新编号便于计算。
(
a
∣
b
)
∗
(\space\space a\space\space|\space\space b\space\space)\space^*
( a ∣ b ) ∗ 对应的 NFA：
(
a
∣
b
)
∗
(\space\space a\space\space|\space\space b\space\space)\space^*
( a ∣ b ) ∗ 对应的状态转换表：
A
=
{
0
,
1
,
2
,
4
,
7
}
A=\{0,1,2,4,7\}
A={0,1,2,4,7}
B
=
{
1
,
2
,
3
,
4
,
6
,
7
}
B=\{1,2,3,4,6,7\}
B={1,2,3,4,6,7}
C
=
{
1
,
2
,
4
,
5
,
6
,
7
}
C=\{1,2,4,5,6,7\}
C={1,2,4,5,6,7}
状态输入符号abABCBBCCBC
(
a
∣
b
)
∗
(\space\space a\space\space|\space\space b\space\space)\space^*
( a ∣ b ) ∗ 对应的 DFA：
(
a
∣
b
)
∗
(\space\space a\space\space|\space\space b\space\space)\space^*
( a ∣ b ) ∗ 对应的最简 DFA：
初始划分两个子集：接受状态子集
{
B
,
C
}
\{B,\space C\}
{B, C} 和非接受状态
{
A
}
\{A\}
{A}；
{
A
}
\{A\}
{A} 不可进一步划分，所以对
{
B
,
C
}
\{B,\space C\}
{B, C} 进一步划分；
m
o
v
e
(
{
B
,
C
}
,
a
)
=
{
B
}
move(\{B, \space C\},\space a)=\{B\}
move({B, C}, a)={B}
m
o
v
e
(
{
B
,
C
}
,
b
)
=
{
C
}
move(\{B, \space C\},\space b)=\{C\}
move({B, C}, b)={C}
这说明
{
B
,
C
}
\{B,\space C\}
{B, C} 是不可区分的子集，故无需进一步划分。
最终上图即为最简 DFA。
(
a
∗
∣
b
∗
)
∗
(\space\space a\space^*\space\space|\space\space b\space^*\space\space)\space^*
( a ∗ ∣ b ∗ ) ∗ 对应的 NFA：
(
a
∗
∣
b
∗
)
∗
(\space\space a\space^*\space\space|\space\space b\space^*\space\space)\space^*
( a ∗ ∣ b ∗ ) ∗ 对应的状态转换表：
A
=
{
0
,
1
,
2
,
4
,
7
}
A=\{0,1,2,4,7\}
A={0,1,2,4,7}
B
=
{
1
,
2
,
3
,
4
,
6
,
7
}
B=\{1,2,3,4,6,7\}
B={1,2,3,4,6,7}
C
=
{
1
,
2
,
4
,
5
,
6
,
7
}
C=\{1,2,4,5,6,7\}
C={1,2,4,5,6,7}
状态输入符号abABCBBCCBC
(
a
∗
∣
b
∗
)
∗
(\space\space a\space^*\space\space|\space\space b\space^*\space\space)\space^*
( a ∗ ∣ b ∗ ) ∗ 对应的 DFA：
(
a
∗
∣
b
∗
)
∗
(\space\space a\space^*\space\space|\space\space b\space^*\space\space)\space^*
( a ∗ ∣ b ∗ ) ∗ 对应的最简 DFA：
由于
(
a
∗
∣
b
∗
)
∗
(\space\space a\space^*\space\space|\space\space b\space^*\space\space)\space^*
( a ∗ ∣ b ∗ ) ∗ 对应的 DFA 与
(
a
∣
b
)
∗
(\space\space a\space\space|\space\space b\space\space)\space^*
( a ∣ b ) ∗ 对应的 DFA 完全一致，所以最终化简得到的 DFA 也是一样的，即上图。
(
(
ε
∣
a
)
b
∗
)
∗
(\space\space(\space\space \varepsilon\space\space |\space\space a\space\space)\space\space b\space^*\space\space)\space^*
( ( ε ∣ a ) b ∗ ) ∗ 的 DFA 在 T 2.8 中已经得到，由于其与
(
a
∣
b
)
∗
(\space\space a\space\space|\space\space b\space\space)\space^*
( a ∣ b ) ∗ 对应的 DFA 完全一致，所以最终化简得到的 DFA 也是一样的，即：
由于已知“最简 DFA 同构的正规式等价”可知，三者的最简 DFA 同构，所以三个正规式等价。
T 2.12
为下列正规式构造最简的 DFA
( a ∣ b ) ∗ a ( a ∣ b ) \space\space(\space\space a\space\space | \space\space b\space\space)\space^*\space\space a\space\space (\space\space a \space\space |\space\space b\space\space) ( a ∣ b ) ∗ a ( a ∣ b )
对应的 NFA 如下：
对应的转换表如下：
A
=
{
0
,
1
,
2
,
4
,
7
}
A=\{0,1,2,4,7\}
A={0,1,2,4,7}
B
=
{
1
,
2
,
3
,
4
,
6
,
7
,
8
,
9
,
11
}
B=\{1,2,3,4,6,7,8,9,11\}
B={1,2,3,4,6,7,8,9,11}
C
=
{
1
,
2
,
4
,
5
,
6
,
7
}
C=\{1,2,4,5,6,7\}
C={1,2,4,5,6,7}
D
=
{
1
,
2
,
3
,
4
,
6
,
7
,
8
,
9
,
10
,
11
,
13
,
14
}
D = \{1,2,3,4,6,7,8,9,10,11,13,14\}
D={1,2,3,4,6,7,8,9,10,11,13,14}
E
=
{
1
,
2
,
4
,
5
,
6
,
7
,
12
,
13
,
14
}
E=\{1,2,4,5,6,7,12,13,14\}
E={1,2,4,5,6,7,12,13,14}
状态输入符号abABCBDECBCDDEEBC
对应的 DFA 如下：
对应的最简 DFA 如下：
初始划分两个子集：接受状态子集
{
D
,
E
}
\{D,E\}
{D,E} 和非接受状态子集
{
A
,
B
,
C
}
\{A,B,C\}
{A,B,C}；
对于接受状态子集，输入字符
a
a
a，状态
D
D
D 和状态
E
E
E 分别变换到状态
D
D
D 和状态
B
B
B，二者不在同一子集中，所以需要划分成
{
D
}
\{D\}
{D}、
{
E
}
\{E\}
{E}；
对于非接受状态子集，输入字符
a
a
a，状态
A
A
A 和状态
C
C
C 均变换到状态
B
B
B，而状态
B
B
B 变换到状态
D
D
D，属于另一个子集，所以初步划分为
{
A
,
C
}
\{A,C\}
{A,C}、
{
B
}
\{B\}
{B}；输入字符
b
b
b，状态
A
A
A 和状态
C
C
C 均变换到状态
C
C
C，所以两个状态不可区分，无需进一步划分。
故，最终状态子集为
{
A
,
C
}
\{A,C\}
{A,C}、
{
B
}
\{B\}
{B}、
{
D
}
\{D\}
{D} 和
{
E
}
\{E\}
{E}。
为了绘制 DFA 方便，令
{
A
,
C
}
\{A,C\}
{A,C} 为状态
0
0
0，
{
B
}
\{B\}
{B} 为状态
1
1
1，
{
D
}
\{D\}
{D} 为状态
2
2
2，
{
E
}
\{E\}
{E} 为状态
3
3
3。
( a ∣ b ) ∗ a ( a ∣ b ) ( a ∣ b ) \space\space(\space\space a\space\space | \space\space b\space\space)\space^*\space\space a\space\space (\space\space a \space\space |\space\space b\space\space)\space\space(\space\space a \space\space |\space\space b\space\space) ( a ∣ b ) ∗ a ( a ∣ b ) ( a ∣ b )
方法一： 子集构造法得到的 NFA 如下：
对应的转换表如下：
A
=
{
0
,
1
,
2
,
4
,
7
}
A=\{0,1,2,4,7\}
A={0,1,2,4,7}
B
=
ε
−
c
l
o
s
u
r
e
(
{
3
,
8
}
)
=
{
1
,
2
,
3
,
4
,
6
,
7
,
8
,
9
,
11
}
B=\varepsilon-closure(\{3,8\})=\{1,2,3,4,6,7,8,9,11\}
B=ε−closure({3,8})={1,2,3,4,6,7,8,9,11}
C
=
ε
−
c
l
o
s
u
r
e
(
{
5
}
)
=
{
1
,
2
,
4
,
5
,
6
,
7
}
C=\varepsilon-closure(\{5\})=\{1,2,4,5,6,7\}
C=ε−closure({5})={1,2,4,5,6,7}
D
=
ε
−
c
l
o
s
u
r
e
(
{
3
,
8
,
10
}
)
=
{
1
,
2
,
3
,
4
,
6
,
7
,
8
,
9
,
10
,
11
,
13
,
14
,
16
}
D=\varepsilon-closure(\{3,8,10\})=\{1,2,3,4,6,7,8,9,10,11,13,14,16\}
D=ε−closure({3,8,10})={1,2,3,4,6,7,8,9,10,11,13,14,16}
E
=
ε
−
c
l
o
s
u
r
e
(
{
5
,
12
}
)
=
{
1
,
2
,
4
,
5
,
6
,
7
,
12
,
13
,
14
,
16
}
E=\varepsilon-closure(\{5,12\})=\{1,2,4,5,6,7,12,13,14,16\}
E=ε−closure({5,12})={1,2,4,5,6,7,12,13,14,16}
F
=
ε
−
c
l
o
s
u
r
e
(
{
3
,
8
,
10
,
15
}
)
=
{
1
,
2
,
3
,
4
,
6
,
7
,
8
,
9
,
10
,
11
,
13
,
14
,
15
,
16
,
18
,
19
}
F=\varepsilon-closure(\{3,8,10,15\})=\{1,2,3,4,6,7,8,9,10,11,13,14,15,16,18,19\}
F=ε−closure({3,8,10,15})={1,2,3,4,6,7,8,9,10,11,13,14,15,16,18,19}
G
=
ε
−
c
l
o
s
u
r
e
(
{
5
,
12
,
17
}
)
=
{
1
,
2
,
4
,
5
,
6
,
7
,
12
,
13
,
14
,
16
,
17
,
18
,
19
}
G=\varepsilon-closure(\{5,12,17\})=\{1,2,4,5,6,7,12,13,14,16,17,18,19\}
G=ε−closure({5,12,17})={1,2,4,5,6,7,12,13,14,16,17,18,19}
H
=
ε
−
c
l
o
s
u
r
e
(
{
3
,
8
,
15
}
)
=
{
1
,
2
,
3
,
4
,
6
,
7
,
8
,
9
,
11
,
15
,
18
,
19
}
H=\varepsilon-closure(\{3,8,15\})=\{1,2,3,4,6,7,8,9,11,15,18,19\}
H=ε−closure({3,8,15})={1,2,3,4,6,7,8,9,11,15,18,19}
I
=
ε
−
c
l
o
s
u
r
e
(
{
5
,
17
}
)
=
{
1
,
2
,
4
,
5
,
6
,
7
,
17
,
18
,
19
}
I=\varepsilon-closure(\{5,17\})=\{1,2,4,5,6,7,17,18,19\}
I=ε−closure({5,17})={1,2,4,5,6,7,17,18,19}
状态输入符号abABCBDECBCDFGEHIFFGGHIHDEIBC
方法二： 分裂法得到的 NFA 如下：
对应的转换表如下：
A
=
{
0
,
1
,
3
}
A=\{0,1,3\}
A={0,1,3}
B
=
ε
−
c
l
o
s
u
r
e
(
{
2
,
4
}
)
=
{
1
,
2
,
3
,
4
}
B=\varepsilon-closure(\{2,4\})=\{1,2,3,4\}
B=ε−closure({2,4})={1,2,3,4}
C
=
ε
−
c
l
o
s
u
r
e
(
{
2
}
)
=
{
1
,
2
,
3
}
C=\varepsilon-closure(\{2\})=\{1,2,3\}
C=ε−closure({2})={1,2,3}
D
=
ε
−
c
l
o
s
u
r
e
(
{
2
,
4
,
5
}
)
=
B
∪
{
5
}
=
{
1
,
2
,
3
,
4
,
5
}
D=\varepsilon-closure(\{2,4,5\})=B∪\{5\}=\{1,2,3,4,5\}
D=ε−closure({2,4,5})=B∪{5}={1,2,3,4,5}
E
=
ε
−
c
l
o
s
u
r
e
(
{
2
,
5
}
)
=
C
∪
{
5
}
=
{
1
,
2
,
3
,
5
}
E=\varepsilon-closure(\{2,5\})=C∪\{5\}=\{1,2,3,5\}
E=ε−closure({2,5})=C∪{5}={1,2,3,5}
F
=
ε
−
c
l
o
s
u
r
e
(
{
2
,
4
,
5
,
6
}
)
=
D
∪
{
6
}
=
{
1
,
2
,
3
,
4
,
5
,
6
}
F=\varepsilon-closure(\{2,4,5,6\})=D∪\{6\}=\{1,2,3,4,5,6\}
F=ε−closure({2,4,5,6})=D∪{6}={1,2,3,4,5,6}
G
=
ε
−
c
l
o
s
u
r
e
(
{
2
,
5
,
6
}
)
=
E
∪
{
6
}
=
{
1
,
2
,
3
,
5
,
6
}
G=\varepsilon-closure(\{2,5,6\})=E∪\{6\}=\{1,2,3,5,6\}
G=ε−closure({2,5,6})=E∪{6}={1,2,3,5,6}
H
=
ε
−
c
l
o
s
u
r
e
(
{
2
,
4
,
6
}
)
=
B
∪
{
6
}
=
{
1
,
2
,
3
,
4
,
6
}
H=\varepsilon-closure(\{2,4,6\})=B∪\{6\}=\{1,2,3,4,6\}
H=ε−closure({2,4,6})=B∪{6}={1,2,3,4,6}
I
=
ε
−
c
l
o
s
u
r
e
(
{
2
,
6
}
)
=
C
∪
{
6
}
=
{
1
,
2
,
3
,
6
}
I=\varepsilon-closure(\{2,6\})=C∪\{6\}=\{1,2,3,6\}
I=ε−closure({2,6})=C∪{6}={1,2,3,6}
状态输入符号abABCBDECBCDFGEHIFFGGHIHDEIBC
可以看出“子集构造法”和“分裂法”得到的状态转换表一样，所以化出的DFA也一致。
对应的 DFA 如下：
对应的最简 DFA 如下：
初始划分两个子集：接受状态子集
{
F
,
G
,
H
,
I
}
\{F,G,H,I\}
{F,G,H,I} 和非接受状态子集
{
A
,
B
,
C
,
D
,
E
}
\{A,B,C,D,E\}
{A,B,C,D,E}；
对于接受状态子集，分别输入字符
a
a
a 和字符
b
b
b，可将原集合划分为
{
F
,
G
}
\{F,G\}
{F,G} 和
{
H
,
I
}
\{H,I\}
{H,I}；
对于非接受状态子集，分别输入字符
a
a
a 和字符
b
b
b，可将原集合划分为
{
A
,
B
,
C
}
\{A,B,C\}
{A,B,C} 和
{
D
,
E
}
\{D,E\}
{D,E}；
对
{
F
,
G
}
\{F,G\}
{F,G} 集合进一步划分成
{
F
}
\{F\}
{F} 和
{
G
}
\{G\}
{G}；
对
{
H
,
I
}
\{H,I\}
{H,I} 集合进一步划分成
{
H
}
\{H\}
{H} 和
{
I
}
\{I\}
{I}；
对
{
A
,
B
,
C
}
\{A,B,C\}
{A,B,C} 集合进一步划分成
{
A
,
C
}
\{A, C\}
{A,C} 和
{
B
}
\{B\}
{B}；
对
{
D
,
E
}
\{D,E\}
{D,E} 集合进一步划分成
{
D
}
\{D\}
{D} 和
{
E
}
\{E\}
{E}；
故，最终状态子集为
{
A
,
C
}
\{A,C\}
{A,C}、
{
B
}
\{B\}
{B} 、
{
D
}
\{D\}
{D} 、
{
E
}
\{E\}
{E} 、
{
F
}
\{F\}
{F}、
{
G
}
\{G\}
{G} 、
{
H
}
\{H\}
{H} 和
{
I
}
\{I\}
{I}。
为了绘制 DFA 方便，令
{
A
,
C
}
\{A,C\}
{A,C} 为状态
0
0
0，
{
B
}
\{B\}
{B} 为状态
1
1
1，
{
D
}
\{D\}
{D} 为状态
2
2
2，
{
E
}
\{E\}
{E} 为状态
3
3
3，
{
F
}
\{F\}
{F} 为状态
4
4
4、
{
G
}
\{G\}
{G} 为状态
5
5
5 、
{
H
}
\{H\}
{H} 为状态
6
6
6、
{
I
}
\{I\}
{I} 为状态
7
7
7。
( a ∣ b ) ∗ a ( a ∣ b ) ( a ∣ b ) ( a ∣ b ) \space\space(\space\space a\space\space | \space\space b\space\space)\space^*\space\space a\space\space (\space\space a \space\space |\space\space b\space\space)\space\space(\space\space a \space\space |\space\space b\space\space)\space\space(\space\space a \space\space |\space\space b\space\space) ( a ∣ b ) ∗ a ( a ∣ b ) ( a ∣ b ) ( a ∣ b )
方法一： 子集构造法得到的 NFA 如下：
对应的转换表如下：
A
=
{
0
,
1
,
2
,
4
,
7
}
A=\{0,1,2,4,7\}
A={0,1,2,4,7}
B
=
ε
−
c
l
o
s
u
r
e
(
{
3
,
8
}
)
=
{
1
,
2
,
3
,
4
,
6
,
7
,
8
,
9
,
11
}
B=\varepsilon-closure(\{3,8\})=\{1,2,3,4,6,7,8,9,11\}
B=ε−closure({3,8})={1,2,3,4,6,7,8,9,11}
C
=
ε
−
c
l
o
s
u
r
e
(
{
5
}
)
=
{
1
,
2
,
4
,
5
,
6
,
7
}
C=\varepsilon-closure(\{5\})=\{1,2,4,5,6,7\}
C=ε−closure({5})={1,2,4,5,6,7}
D
=
ε
−
c
l
o
s
u
r
e
(
{
3
,
8
,
10
}
)
=
{
1
,
2
,
3
,
4
,
6
,
7
,
8
,
9
,
10
,
11
,
13
,
14
,
16
}
D=\varepsilon-closure(\{3,8,10\})=\{1,2,3,4,6,7,8,9,10,11,13,14,16\}
D=ε−closure({3,8,10})={1,2,3,4,6,7,8,9,10,11,13,14,16}
E
=
ε
−
c
l
o
s
u
r
e
(
{
5
,
12
}
)
=
{
1
,
2
,
4
,
5
,
6
,
7
,
12
,
13
,
14
,
16
}
E=\varepsilon-closure(\{5,12\})=\{1,2,4,5,6,7,12,13,14,16\}
E=ε−closure({5,12})={1,2,4,5,6,7,12,13,14,16}
F
=
ε
−
c
l
o
s
u
r
e
(
{
3
,
8
,
10
,
15
}
)
=
{
1
,
2
,
3
,
4
,
6
,
7
,
8
,
9
,
10
,
11
,
13
,
14
,
15
,
16
,
18
,
19
,
21
}
F=\varepsilon-closure(\{3,8,10,15\})=\{1,2,3,4,6,7,8,9,10,11,13,14,15,16,18,19,21\}
F=ε−closure({3,8,10,15})={1,2,3,4,6,7,8,9,10,11,13,14,15,16,18,19,21}
G
=
ε
−
c
l
o
s
u
r
e
(
{
5
,
12
,
17
}
)
=
{
1
,
2
,
4
,
5
,
6
,
7
,
12
,
13
,
14
,
16
,
17
,
18
,
19
,
21
}
G=\varepsilon-closure(\{5,12,17\})=\{1,2,4,5,6,7,12,13,14,16,17,18,19,21\}
G=ε−closure({5,12,17})={1,2,4,5,6,7,12,13,14,16,17,18,19,21}
H
=
ε
−
c
l
o
s
u
r
e
(
{
3
,
8
,
15
}
)
=
{
1
,
2
,
3
,
4
,
6
,
7
,
8
,
9
,
11
,
15
,
18
,
19
,
21
}
H=\varepsilon-closure(\{3,8,15\})=\{1,2,3,4,6,7,8,9,11,15,18,19,21\}
H=ε−closure({3,8,15})={1,2,3,4,6,7,8,9,11,15,18,19,21}
I
=
ε
−
c
l
o
s
u
r
e
(
{
5
,
17
}
)
=
{
1
,
2
,
4
,
5
,
6
,
7
,
17
,
18
,
19
,
21
}
I=\varepsilon-closure(\{5,17\})=\{1,2,4,5,6,7,17,18,19,21\}
I=ε−closure({5,17})={1,2,4,5,6,7,17,18,19,21}
J
=
ε
−
c
l
o
s
u
r
e
(
{
3
,
8
,
10
,
15
,
20
}
)
=
{
1
,
2
,
3
,
4
,
6
,
7
,
8
,
9
,
10
,
11
,
13
,
14
,
15
,
16
,
18
,
19
,
20
,
21
,
23
,
24
}
J=\varepsilon-closure(\{3,8,10,15,20\})=\{1,2,3,4,6,7,8,9,10,11,13,14,15,16,18,19,20,21,23,24\}
J=ε−closure({3,8,10,15,20})={1,2,3,4,6,7,8,9,10,11,13,14,15,16,18,19,20,21,23,24}
K
=
ε
−
c
l
o
s
u
r
e
(
{
5
,
12
,
17
,
22
}
)
=
{
1
,
2
,
4
,
5
,
6
,
7
,
12
,
13
,
14
,
16
,
17
,
18
,
19
,
21
,
22
,
23
,
24
}
K=\varepsilon-closure(\{5,12,17,22\})=\{1,2,4,5,6,7,12,13,14,16,17,18,19,21,22,23,24\}
K=ε−closure({5,12,17,22})={1,2,4,5,6,7,12,13,14,16,17,18,19,21,22,23,24}
L
=
ε
−
c
l
o
s
u
r
e
(
{
3
,
8
,
15
,
20
}
)
=
{
1
,
2
,
3
,
4
,
6
,
7
,
8
,
9
,
11
,
15
,
18
,
19
,
20
,
21
,
23
,
24
}
L=\varepsilon-closure(\{3,8,15,20\})=\{1,2,3,4,6,7,8,9,11,15,18,19,20,21,23,24\}
L=ε−closure({3,8,15,20})={1,2,3,4,6,7,8,9,11,15,18,19,20,21,23,24}
M
=
ε
−
c
l
o
s
u
r
e
(
{
5
,
17
,
22
}
)
=
{
1
,
2
,
4
,
5
,
6
,
7
,
17
,
18
,
19
,
21
,
22
,
23
,
24
}
M=\varepsilon-closure(\{5,17,22\})=\{1,2,4,5,6,7,17,18,19,21,22,23,24\}
M=ε−closure({5,17,22})={1,2,4,5,6,7,17,18,19,21,22,23,24}
N
=
ε
−
c
l
o
s
u
r
e
(
{
3
,
8
,
10
,
20
}
)
=
{
1
,
2
,
3
,
4
,
6
,
7
,
8
,
9
,
10
,
11
,
13
,
14
,
16
,
20
,
23
,
24
}
N=\varepsilon-closure(\{3,8,10,20\})=\{1,2,3,4,6,7,8,9,10,11,13,14,16,20,23,24\}
N=ε−closure({3,8,10,20})={1,2,3,4,6,7,8,9,10,11,13,14,16,20,23,24}
O
=
ε
−
c
l
o
s
u
r
e
(
{
5
,
12
,
22
}
)
=
{
1
,
2
,
4
,
5
,
6
,
7
,
12
,
13
,
14
,
16
,
22
,
23
,
24
}
O=\varepsilon-closure(\{5,12,22\})=\{1,2,4,5,6,7,12,13,14,16,22,23,24\}
O=ε−closure({5,12,22})={1,2,4,5,6,7,12,13,14,16,22,23,24}
P
=
ε
−
c
l
o
s
u
r
e
(
{
3
,
8
,
20
}
)
=
{
1
,
2
,
3
,
4
,
6
,
7
,
8
,
9
,
11
,
23
,
24
}
P=\varepsilon-closure(\{3,8,20\})=\{1,2,3,4,6,7,8,9,11,23,24\}
P=ε−closure({3,8,20})={1,2,3,4,6,7,8,9,11,23,24}
Q
=
ε
−
c
l
o
s
u
r
e
(
{
5
,
22
}
)
=
{
1
,
2
,
4
,
5
,
6
,
7
,
22
,
23
,
24
}
Q=\varepsilon-closure(\{5,22\})=\{1,2,4,5,6,7,22,23,24\}
Q=ε−closure({5,22})={1,2,4,5,6,7,22,23,24}
状态输入符号abABCBDECBCDFGEHIFJKGLMHNOIPQJJKKLMLNOMPQNFGOHIPDEQBC
可以看出“子集构造法”和“分裂法”得到的状态转换表一样，所以化出的DFA也一致。
方法二： 分裂法得到的 NFA 如下：
对应的转换表如下：
A
=
{
0
,
1
,
3
}
A=\{0,1,3\}
A={0,1,3}
B
=
ε
−
c
l
o
s
u
r
e
(
{
2
,
4
}
)
=
{
1
,
2
,
3
,
4
}
B=\varepsilon-closure(\{2,4\})=\{1,2,3,4\}
B=ε−closure({2,4})={1,2,3,4}
C
=
ε
−
c
l
o
s
u
r
e
(
{
2
}
)
=
{
1
,
2
,
3
}
C=\varepsilon-closure(\{2\})=\{1,2,3\}
C=ε−closure({2})={1,2,3}
D
=
ε
−
c
l
o
s
u
r
e
(
{
2
,
4
,
5
}
)
=
B
∪
{
5
}
=
{
1
,
2
,
3
,
4
,
5
}
D=\varepsilon-closure(\{2,4,5\})=B∪\{5\}=\{1,2,3,4,5\}
D=ε−closure({2,4,5})=B∪{5}={1,2,3,4,5}
E
=
ε
−
c
l
o
s
u
r
e
(
{
2
,
5
}
)
=
C
∪
{
5
}
=
{
1
,
2
,
3
,
5
}
E=\varepsilon-closure(\{2,5\})=C∪\{5\}=\{1,2,3,5\}
E=ε−closure({2,5})=C∪{5}={1,2,3,5}
F
=
ε
−
c
l
o
s
u
r
e
(
{
2
,
4
,
5
,
6
}
)
=
D
∪
{
6
}
=
{
1
,
2
,
3
,
4
,
5
,
6
}
F=\varepsilon-closure(\{2,4,5,6\})=D∪\{6\}=\{1,2,3,4,5,6\}
F=ε−closure({2,4,5,6})=D∪{6}={1,2,3,4,5,6}
G
=
ε
−
c
l
o
s
u
r
e
(
{
2
,
5
,
6
}
)
=
E
∪
{
6
}
=
{
1
,
2
,
3
,
5
,
6
}
G=\varepsilon-closure(\{2,5,6\})=E∪\{6\}=\{1,2,3,5,6\}
G=ε−closure({2,5,6})=E∪{6}={1,2,3,5,6}
H
=
ε
−
c
l
o
s
u
r
e
(
{
2
,
4
,
6
}
)
=
B
∪
{
6
}
=
{
1
,
2
,
3
,
4
,
6
}
H=\varepsilon-closure(\{2,4,6\})=B∪\{6\}=\{1,2,3,4,6\}
H=ε−closure({2,4,6})=B∪{6}={1,2,3,4,6}
I
=
ε
−
c
l
o
s
u
r
e
(
{
2
,
6
}
)
=
C
∪
{
6
}
=
{
1
,
2
,
3
,
6
}
I=\varepsilon-closure(\{2,6\})=C∪\{6\}=\{1,2,3,6\}
I=ε−closure({2,6})=C∪{6}={1,2,3,6}
J
=
ε
−
c
l
o
s
u
r
e
(
{
2
,
4
,
5
,
6
,
7
}
)
=
F
∪
{
7
}
=
{
1
,
2
,
3
,
4
,
5
,
6
,
7
}
J=\varepsilon-closure(\{2,4,5,6,7\})=F∪\{7\}=\{1,2,3,4,5,6,7\}
J=ε−closure({2,4,5,6,7})=F∪{7}={1,2,3,4,5,6,7}
K
=
ε
−
c
l
o
s
u
r
e
(
{
2
,
5
,
6
,
7
}
)
=
G
∪
{
6
}
=
{
1
,
2
,
3
,
5
,
6
,
7
}
K=\varepsilon-closure(\{2,5,6,7\})=G∪\{6\}=\{1,2,3,5,6,7\}
K=ε−closure({2,5,6,7})=G∪{6}={1,2,3,5,6,7}
L
=
ε
−
c
l
o
s
u
r
e
(
{
2
,
4
,
6
,
7
}
)
=
H
∪
{
7
}
=
{
1
,
2
,
3
,
4
,
6
,
7
}
L=\varepsilon-closure(\{2,4,6,7\})=H∪\{7\}=\{1,2,3,4,6,7\}
L=ε−closure({2,4,6,7})=H∪{7}={1,2,3,4,6,7}
M
=
ε
−
c
l
o
s
u
r
e
(
{
2
,
6
,
7
}
)
=
I
∪
{
7
}
=
{
1
,
2
,
3
,
6
,
7
}
M=\varepsilon-closure(\{2,6,7\})=I∪\{7\}=\{1,2,3,6,7\}
M=ε−closure({2,6,7})=I∪{7}={1,2,3,6,7}
N
=
ε
−
c
l
o
s
u
r
e
(
{
2
,
4
,
5
,
7
}
)
=
D
∪
{
7
}
=
{
1
,
2
,
3
,
4
,
5
,
7
}
N=\varepsilon-closure(\{2,4,5,7\})=D∪\{7\}=\{1,2,3,4,5,7\}
N=ε−closure({2,4,5,7})=D∪{7}={1,2,3,4,5,7}
O
=
ε
−
c
l
o
s
u
r
e
(
{
2
,
5
,
7
}
)
=
E
∪
{
7
}
=
{
1
,
2
,
3
,
5
,
7
}
O=\varepsilon-closure(\{2,5,7\})=E∪\{7\}=\{1,2,3,5,7\}
O=ε−closure({2,5,7})=E∪{7}={1,2,3,5,7}
P
=
ε
−
c
l
o
s
u
r
e
(
{
2
,
4
,
7
}
)
=
B
∪
{
7
}
=
{
1
,
2
,
3
,
4
,
7
}
P=\varepsilon-closure(\{2,4,7\})=B∪\{7\}=\{1,2,3,4,7\}
P=ε−closure({2,4,7})=B∪{7}={1,2,3,4,7}
Q
=
ε
−
c
l
o
s
u
r
e
(
{
2
,
7
}
)
=
C
∪
{
7
}
=
{
1
,
2
,
3
,
7
}
Q=\varepsilon-closure(\{2,7\})=C∪\{7\}=\{1,2,3,7\}
Q=ε−closure({2,7})=C∪{7}={1,2,3,7}
状态输入符号abABCBDECBCDFGEHIFJKGLMHNOIPQJJKKLMLNOMPQNFGOHIPDEQBC
对应的 DFA 如下：
对应的最简 DFA 如下：
初次划分：
{
A
,
B
,
C
,
D
,
E
,
F
,
G
,
H
,
I
}
\{A,B,C,D,E,F,G,H,I\}
{A,B,C,D,E,F,G,H,I} 和
{
J
,
K
,
L
,
M
,
N
,
O
,
P
,
Q
}
\{J,K,L,M,N,O,P,Q\}
{J,K,L,M,N,O,P,Q}
第二次划分：
{
A
,
B
,
C
,
D
,
E
}
\{A,B,C,D,E\}
{A,B,C,D,E}、
{
F
,
G
,
H
,
I
}
\{F,G,H,I\}
{F,G,H,I}、
{
J
,
K
,
L
,
M
}
\{J,K,L,M\}
{J,K,L,M} 和
{
N
,
O
,
P
,
Q
}
\{N,O,P,Q\}
{N,O,P,Q}
第三次划分：
{
A
,
B
,
C
}
\{A,B,C\}
{A,B,C}、
{
D
,
E
}
\{D,E\}
{D,E}、
{
F
,
G
}
\{F,G\}
{F,G}、
{
H
,
I
}
\{H,I\}
{H,I}、
{
J
,
K
}
\{J,K\}
{J,K}、
{
L
,
M
}
\{L,M\}
{L,M}、
{
N
,
O
}
\{N,O\}
{N,O} 和
{
P
,
Q
}
\{P,Q\}
{P,Q}
第四次划分：
{
A
,
C
}
\{A,C\}
{A,C}、
{
B
}
\{B\}
{B}、
{
D
}
\{D\}
{D}、
{
E
}
\{E\}
{E}、
{
F
}
\{F\}
{F}、
{
G
}
\{G\}
{G}、
{
H
}
\{H\}
{H}、
{
I
}
\{I\}
{I}、
{
J
}
\{J\}
{J}、
{
K
}
\{K\}
{K}、
{
L
}
\{L\}
{L}、
{
M
}
\{M\}
{M}、
{
N
}
\{N\}
{N}、
{
O
}
\{O\}
{O}、
{
P
}
\{P\}
{P} 和
{
Q
}
\{Q\}
{Q}
最终划分结果为：
{
A
,
C
}
\{A,C\}
{A,C}、
{
B
}
\{B\}
{B}、
{
D
}
\{D\}
{D}、
{
E
}
\{E\}
{E}、
{
F
}
\{F\}
{F}、
{
G
}
\{G\}
{G}、
{
H
}
\{H\}
{H}、
{
I
}
\{I\}
{I}、
{
J
}
\{J\}
{J}、
{
K
}
\{K\}
{K}、
{
L
}
\{L\}
{L}、
{
M
}
\{M\}
{M}、
{
N
}
\{N\}
{N}、
{
O
}
\{O\}
{O}、
{
P
}
\{P\}
{P} 和
{
Q
}
\{Q\}
{Q}
为了绘制 DFA 方便，令
{
A
,
C
}
\{A,C\}
{A,C} 为状态
0
0
0，
{
B
}
\{B\}
{B} 为状态
1
1
1，
{
D
}
\{D\}
{D} 为状态
2
2
2，
{
E
}
\{E\}
{E} 为状态
3
3
3，
{
F
}
\{F\}
{F} 为状态
4
4
4、
{
G
}
\{G\}
{G} 为状态
5
5
5 、
{
H
}
\{H\}
{H} 为状态
6
6
6、
{
I
}
\{I\}
{I} 为状态
7
7
7，
{
J
}
\{J\}
{J} 为状态
8
8
8，
{
K
}
\{K\}
{K} 为状态
9
9
9，
{
L
}
\{L\}
{L} 为状态
10
10
10，
{
M
}
\{M\}
{M} 为状态
11
11
11，
{
N
}
\{N\}
{N} 为状态
12
12
12、
{
O
}
\{O\}
{O} 为状态
13
13
13 、
{
P
}
\{P\}
{P} 为状态
14
14
14、
{
Q
}
\{Q\}
{Q} 为状态
15
15
15。
T 2.13
**构造一个 DFA，它接受
Σ
=
{
0
,
1
}
\Sigma=\{0,1\}
Σ={0,1} 上
0
0
0 和
1
1
1 的个数都是偶数的字符串**
对于一个01串，无论其 0 和 1 的个数有多少，总属于下面四种情况之一：
0：0和1的个数都是偶数；
1：0的个数是偶数，1的个数是奇数；
2：0的个数是奇数，1的个数是偶数；
3：0和1的个数都是奇数.
无论上述哪种情况，在01串后添加一个0或1后，总会处于另一种情况中，因此构造的 DFA 可以通过四个状态表示出来：
T 2.14
**构造一个 DFA，它接受
Σ
=
{
0
,
1
}
\Sigma=\{0,1\}
Σ={0,1} 上能被
5
5
5 整除的二进制数**
一个数对5取模，存在五种结果，结果为0、1、2、3、4。结果为0对应的是接受状态，其余是非接受状态。这样便可通过五个状态构造 DFA。
0：对5取模得0；
1：对5取模得1；
2：对5取模得2；
3：对5取模得3；
4：对5取模得4.
T 2.15
**构造一个最简的 DFA，它接受所有大于
101
101
101 的二进制整数**
根据题意，先简单地将状态分为六种，为
0
0
0、
1
1
1、
2
2
2、
3
3
3、
4
4
4、
5
5
5和大于
5
5
5的整数。
0：对应二进制整数为0；
1：对应二进制整数为1；
2：对应二进制整数为2；
3：对应二进制整数为3；
4：对应二进制整数为4；
5：对应二进制整数为5；
6：对应二进制整数大于5.
初步构造 DFA：
对上面的 DFA 进行化简：
初步划分为接受状态子集
{
6
}
\{6\}
{6} 和非接受状态子集
{
0
,
1
,
2
,
3
,
4
,
5
}
\{0,\space 1,\space2, \space 3,\space4,\space5\}
{0, 1, 2, 3, 4, 5}；
接受状态子集无法进一步划分；
对非接受状态子集进一步划分：
m
o
v
e
(
{
0
,
1
,
2
,
3
,
4
,
5
}
,
0
)
=
{
0
,
2
,
4
,
6
}
move(\{0,\space 1,\space2, \space 3,\space4,\space5\}, \space0)=\{0, \space 2, \space 4, \space 6\}
move({0, 1, 2, 3, 4, 5}, 0)={0, 2, 4, 6}，其中状态
0
0
0 转换到状态
0
0
0，状态
1
1
1 转换到状态
2
2
2，状态
2
2
2 转换到状态
4
4
4，状态
3
,
4
,
5
3,\space4,\space5
3, 4, 5 均转换到状态
6
6
6。
m
o
v
e
(
{
0
,
1
,
2
,
3
,
4
,
5
}
,
1
)
=
{
1
,
3
,
5
,
6
}
move(\{0,\space 1,\space2, \space 3,\space4,\space5\}, \space1)=\{1, \space 3, \space 5, \space 6\}
move({0, 1, 2, 3, 4, 5}, 1)={1, 3, 5, 6}，其中状态
0
0
0 转换到状态
1
1
1，状态
1
1
1 转换到状态
3
3
3，状态
2
2
2 转换到状态
5
5
5，状态
3
,
4
,
5
3,\space4,\space5
3, 4, 5 均转换到状态
6
6
6。
由于
0
,
1
,
2
,
3
,
4
,
5
0,\space1,\space2,\space 3,\space4,\space5
0, 1, 2, 3, 4, 5 属于同一个子集，所以
0
,
1
,
2
0,\space1,\space2
0, 1, 2 仍属于同一子集，而由于
3
,
4
,
5
3,\space4,\space5
3, 4, 5 转换到了另一个不同的子集中，所以
3
,
4
,
5
3,\space4,\space5
3, 4, 5 被归为新的一个子集，子集
{
0
,
1
,
2
}
\{0,\space1,\space2\}
{0, 1, 2} 和子集
{
3
,
4
,
5
}
\{3,\space4,\space5\}
{3, 4, 5} 代替了原先的子集
{
0
,
1
,
2
,
3
,
4
,
5
}
\{0,\space 1,\space2, \space 3,\space4,\space5\}
{0, 1, 2, 3, 4, 5}；
现在全部子集为
{
6
}
\{6\}
{6} 、
{
0
,
1
,
2
}
\{0,\space1,\space2\}
{0, 1, 2} 和
{
3
,
4
,
5
}
\{3,\space4,\space5\}
{3, 4, 5}，分别对子集
{
0
,
1
,
2
}
\{0,\space1,\space2\}
{0, 1, 2} 和子集
{
3
,
4
,
5
}
\{3,\space4,\space5\}
{3, 4, 5} 进一步划分：
m
o
v
e
(
{
0
,
1
,
2
}
,
0
)
=
{
0
,
2
,
4
}
move(\{0,\space 1,\space2\}, \space0)=\{0, \space 2, \space 4\}
move({0, 1, 2}, 0)={0, 2, 4}，其中状态
0
0
0 转换到状态
0
0
0，状态
1
1
1 转换到状态
2
2
2，状态
2
2
2 转换到状态
4
4
4。
m
o
v
e
(
{
0
,
1
,
2
}
,
1
)
=
{
1
,
3
,
5
}
move(\{0,\space 1,\space2\}, \space1)=\{1, \space 3, \space 5\}
move({0, 1, 2}, 1)={1, 3, 5}，其中状态
0
0
0 转换到状态
1
1
1，状态
1
1
1 转换到状态
3
3
3，状态
2
2
2 转换到状态
5
5
5。
在输入字符为
0
0
0的情况下，状态
0
0
0 和 状态
1
1
1 均转换到同一集合
{
0
,
1
,
2
}
\{0,\space 1,\space2\}
{0, 1, 2} 中，但是状态
2
2
2 转换到了另一个集合
{
3
,
4
,
5
}
\{3,\space4,\space5\}
{3, 4, 5} 中，所以状态
2
2
2 将被划分到与状态
0
0
0 和状态
1
1
1 不同的子集中；在输入字符为
1
1
1的情况下，状态
0
0
0 转换到子集
{
0
,
1
,
2
}
\{0,\space 1,\space2\}
{0, 1, 2} 中，而状态
1
1
1 转移到子集
{
3
,
4
,
5
}
\{3,\space4,\space5\}
{3, 4, 5} 中，根据子集划分的要求“两个状态
s
s
s 和
t
t
t 被划分到同一子集中，当且仅当对任意输入符号
α
\alpha
α，状态
s
s
s 和
t
t
t 转换到本次划分前的同一子集中”，所以状态
0
0
0 和 状态
1
1
1 也要被划分到不同子集。故，经过本次划分，得到全部子集
{
0
}
\{0\}
{0}、
{
1
}
\{1\}
{1}、
{
2
}
\{2\}
{2}、
{
3
,
4
,
5
}
\{3,\space4,\space5\}
{3, 4, 5} 和
{
6
}
\{6\}
{6}。
m
o
v
e
(
{
3
,
4
,
5
}
,
0
)
=
m
o
v
e
(
{
3
,
4
,
5
}
,
1
)
=
{
6
}
move(\{3,\space4,\space5\}, \space0) = move(\{3,\space4,\space5\}, \space1) = \{6\}
move({3, 4, 5}, 0)=move({3, 4, 5}, 1)={6}，所以无需进一步划分。
最终得到全部子集
{
0
}
\{0\}
{0}、
{
1
}
\{1\}
{1}、
{
2
}
\{2\}
{2}、
{
3
,
4
,
5
}
\{3,\space4,\space5\}
{3, 4, 5} 和
{
6
}
\{6\}
{6}。令
A
=
{
0
}
A=\{0\}
A={0}，
B
=
{
1
}
B=\{1\}
B={1}，
C
=
{
2
}
C=\{2\}
C={2}，
D
=
{
3
,
4
,
5
}
D=\{3,\space4,\space5\}
D={3, 4, 5}，
E
=
{
6
}
E=\{6\}
E={6}，最简 DFA 如下：
标签：
编辑器
本文转载自: https://blog.csdn.net/weixin_46221946/article/details/128263047
版权归原作者 不牌不改 所有， 如有侵权，请联系我们删除。
版权归原作者 不牌不改 所有， 如有侵权，请联系我们删除。