第三章
7
构造下列正规式相应的DFA
(1)1(0|1)101(2)1(1010|1(010)1)0(3)0101010(4)(00|11)((01|10)(00|11)(01|10)(00|11))
复习概念：
- DFA没有输入空串之上的转换动作；
- 对于DFA，一个特定的符号输入，有且只能得到一个状态，而NFA就有可能得到一个状态集；
(1)
先将NFA画出
NFA转换为DFA
能发生转换的数据为
1
,
0
,
ϵ
1, 0, \epsilon
1,0,ϵ,初态为
0
0
0,且它的
ϵ
\epsilon
ϵ闭包为
{
0
}
\{0\}
{0}, 所以不妨先求出
I
=
0
的
I
0
与
I
1
I=0的I_0与I_1
I=0的I0与I1
I
0
I_0
I0表示，从
I
I
I的元素出发，只经过一次
0
0
0状态转化可以到达的元素集合
I
1
I_1
I1表示，从
I
I
I的元素出发，只经过一次
1
1
1状态转化可以到达的元素集合
I
I
I
I
0
I_0
I0
I
1
I_1
I1
{
0
}
\{0\}
{0}
∅
\empty
∅
{
1
,
2
,
3
}
\{1,2,3\}
{1,2,3}
这里产生了新的非空集合
{
1
,
2
,
3
}
\{1,2,3\}
{1,2,3},需要对该集合作为新的
I
I
I进行处理
I
I
I
I
0
I_0
I0
I
1
I_1
I1
{
1
,
2
,
3
}
\{1,2,3\}
{1,2,3}
{
2
,
3
}
\{2,3\}
{2,3}
{
2
,
3
,
4
}
\{2,3,4\}
{2,3,4}注意，
ϵ
\epsilon
ϵ变化直接默认放进去
于是产生了新的集合
{
2
,
3
}
\{2,3\}
{2,3}和
{
2
,
3
,
4
}
\{2,3,4\}
{2,3,4}，继续对新集合产生上述操作
最后得到全部 状态转换矩阵
I
I
I
I
0
I_0
I0
I
1
I_1
I1说明
{
0
}
\{0\}
{0}
∅
\empty
∅
{
1
,
2
,
3
}
\{1,2,3\}
{1,2,3}新集合
{
1
,
2
,
3
}
\{1,2,3\}
{1,2,3}
{
1
,
2
,
3
}
\{1,2,3\}
{1,2,3}
{
2
,
3
}
\{2,3\}
{2,3}
{
2
,
3
,
4
}
\{2,3,4\}
{2,3,4}新集合
{
2
,
3
}
\{2,3\}
{2,3}，
{
2
,
3
,
4
}
\{2,3,4\}
{2,3,4},1没有0的状态转移，删去
{
2
,
3
}
\{2,3\}
{2,3}
{
2
,
3
}
\{2,3\}
{2,3}
{
2
,
3
,
4
}
\{2,3,4\}
{2,3,4}无新集合
{
2
,
3
,
4
}
\{2,3,4\}
{2,3,4}
{
2
,
3
,
5
}
\{2,3,5\}
{2,3,5}
{
2
,
3
,
4
}
\{2,3,4\}
{2,3,4}新集合
{
2
,
3
,
5
}
\{2,3,5\}
{2,3,5}
{
2
,
3
,
5
}
\{2,3,5\}
{2,3,5}
{
2
,
3
}
\{2,3\}
{2,3}
{
2
,
3
,
4
,
6
}
\{2,3,4,6\}
{2,3,4,6}新集合
{
2
,
3
,
4
,
6
}
\{2,3,4,6\}
{2,3,4,6},注意5没有0的状态转移，删去
{
2
,
3
,
4
,
6
}
\{2,3,4,6\}
{2,3,4,6}
{
2
,
3
,
5
}
\{2,3,5\}
{2,3,5}
{
2
,
3
,
4
}
\{2,3,4\}
{2,3,4}无新集合
∅
\empty
∅
∅
\empty
∅
∅
\empty
∅无新集合
重命名
I
I
I
I
0
I_0
I0
I
1
I_1
I10
∅
\empty
∅1123223343425543
∅
\empty
∅
∅
\empty
∅
∅
\empty
∅
然后我们还需要最小化状态转换矩阵，我们对所有的状态有如下定义
- 多余状态：对于一个状态 S i S_i Si，若从开始状态出发，不可能到达状态 S i S_i Si，则 S i S_i Si为多余（无用）状态
- 死状态：对于一个状态 S i S_i Si，对于任意输入符号a，若转到它本身后，不可能从它到达终止状态，则称 S i S_i Si为死状态
- 等价状态：若 S i S_i Si为自动机的一个状态，我们把从 S i S_i Si出发能导出的所有符号串的集合记为 L ( S i ) L(S_i) L(Si). 若有 L ( S i ) = L ( S i j ) L(S_i) = L(S_ij) L(Si)=L(Sij).则称 S i S_i Si和 S j S_j Sj是等价状态。
- 可区别状态：自动机中两个状态 S i S_i Si和 S j S_j Sj，如果它们不等价，则称它们可区别 如何判断？ - 状态 S i S_i Si和 S j S_j Sj必须同时为终止状态或同时为非终止状态- 状态 S i S_i Si和 S j S_j Sj对于任意输入符 a ∈ Σ a∈Σ a∈Σ，必须转到等价的状态里
综上我们要去掉前两种状态，并合并等价状态
首先删去空集状态，其为死状态。
然后能到达
原NFA中6
状态的都是终态，也就是说重命名后的状态
5
为终态,记
{
5
}
\{5\}
{5}为
I
(
2
)
I^{(2)}
I(2);剩余状态
0,1,2,3,4
为非终态， 记
{
0
,
1
,
2
,
3
,
4
}
\{0,1,2,3,4\}
{0,1,2,3,4}为
I
(
1
)
I^{(1)}
I(1)；
不难发现
{
5
}
\{5\}
{5}无法划分,
I
0
(
1
)
=
{
2
,
4
}
I
1
(
1
)
=
{
1
,
3
,
5
}
I^{(1)}_0 = \{2,4\}\quad I^{(1)}_1 = \{1,3,5\}
I0(1)={2,4}I1(1)={1,3,5}
其中
{
1
,
3
,
5
}
\{1,3,5\}
{1,3,5}不包含于任何划分，需要拆分
I
(
1
)
I^{(1)}
I(1)
**注意到只有
4
经过
1
到达
5
,需要将
4
划分出来**
变成
{
0
,
1
,
2
,
3
}
记为
I
(
11
)
{
4
}
记为
I
(
12
)
\{0,1,2,3\}\quad记为I^{(11)}\\ \{4\}\quad 记为I^{(12)}
{0,1,2,3}记为I(11){4}记为I(12)
显然
I
(
12
)
I^{(12)}
I(12)无法划分，继续考察
I
(
11
)
I^{(11)}
I(11)
I
0
(
11
)
=
{
2
,
4
}
I
1
(
11
)
=
{
1
,
3
}
I^{(11)}_0 = \{2,4\}\quad I^{(11)}_1 = \{1, 3\}
I0(11)={2,4}I1(11)={1,3}
{
2
,
4
}
\{2,4\}
{2,4}不包含于任何划分
**注意到只有
3
经过
0
到达
4
,需要将
3
划分出来**
{
0
,
1
,
2
}
记为
I
(
t
m
p
)
{
3
}
记为
I
(
112
)
\{0,1,2\}\quad记为I^{(tmp)}\\ \{3\}\quad 记为I^{(112)}
{0,1,2}记为I(tmp){3}记为I(112)
I
0
(
t
m
p
)
=
{
2
}
I
1
(
t
m
p
)
=
{
1
,
3
}
I^{(tmp)}_0 = \{2\}\quad I^{(tmp)}_1 =\{1,3\}
I0(tmp)={2}I1(tmp)={1,3}
划分之后发现
{
1
,
3
}
\{1,3\}
{1,3}也不被包含于新的划分了，需要继续划分
I
(
t
m
p
)
I^{(tmp)}
I(tmp):0通过1转化为1，所以将0划分
{
1
,
2
}
记为
I
(
111
)
{
0
}
记为
I
(
113
)
\{1,2\} \quad 记为 I^{(111)} \\ \{0\}\quad记为I^{(113)}
{1,2}记为I(111){0}记为I(113)
最后得到划分
{
0
}
{
1
,
2
}
{
3
}
{
4
}
{
5
}
\{0\}\{1,2\}\{3\}\{4\}\{5\}
{0}{1,2}{3}{4}{5}
并重命名为 0，1，2，3，4
得到最简状态矩阵转换表
I
I
I
I
0
I_0
I0
I
1
I_1
I101112232314432
最简DFA如下
(2)
对于 1(1010*|1(010)*1)*0
被
()*
包围住的部分可以使用循环来表示
然后进入循环的部分两旁使用
ϵ
\epsilon
ϵ进行循环的离开
如 1010* 和 1(010)*1可以表示为如下NFA
整体的NFA如下
初始状态转换矩阵
I
I
I
I
0
I_0
I0
I
1
I_1
I1
{
0
}
\{0\}
{0}
∅
\empty
∅
{
1
,
2
,
12
}
\{1,2,12\}
{1,2,12}
{
1
,
2
,
12
}
\{1,2,12\}
{1,2,12}
{
13
}
\{13\}
{13}
{
3
,
7
,
8
,
9
}
\{3,7,8,9\}
{3,7,8,9}
{
13
}
\{13\}
{13}
∅
\empty
∅
∅
\empty
∅
{
3
,
7
,
8
,
9
}
\{3,7,8,9\}
{3,7,8,9}
{
4
,
10
}
\{4,10\}
{4,10}
{
2
,
12
}
\{2,12\}
{2,12}
{
4
,
10
}
\{4,10\}
{4,10}
∅
\empty
∅
{
5
,
6
,
2
,
12
,
11
}
\{5,6,2,12,11\}
{5,6,2,12,11}
{
2
,
12
}
\{2,12\}
{2,12}
{
13
}
\{13\}
{13}
{
3
,
7
,
8
,
9
}
\{3,7,8,9\}
{3,7,8,9}
{
2
,
5
,
6
,
12
,
11
}
\{2,5,6,12,11\}
{2,5,6,12,11}
{
2
,
6
,
8
,
9
,
12
,
13
}
\{2,6,8,9,12,13\}
{2,6,8,9,12,13}
{
3
,
7
,
8
,
9
}
\{3,7,8,9\}
{3,7,8,9}
{
2
,
6
,
8
,
9
,
12
,
13
}
\{2,6,8,9,12, 13\}
{2,6,8,9,12,13}
{
2
,
6
,
10
,
12
,
13
}
\{2,6,10,12,13\}
{2,6,10,12,13}
{
2
,
3
,
7
,
8
,
9
,
12
}
\{2,3,7,8,9,12\}
{2,3,7,8,9,12}
{
2
,
6
,
10
,
12
,
13
}
\{2,6,10,12,13\}
{2,6,10,12,13}
{
2
,
6
,
12
,
13
}
\{2,6,12,13\}
{2,6,12,13}
{
3
,
7
,
8
,
9
,
11
}
\{3,7,8,9,11\}
{3,7,8,9,11}
{
2
,
6
,
12
,
13
}
\{2,6,12,13\}
{2,6,12,13}
{
2
,
6
,
12
,
13
}
\{2,6,12,13\}
{2,6,12,13}
{
3
,
7
,
8
,
9
}
\{3,7,8,9\}
{3,7,8,9}
{
2
,
3
,
7
,
8
,
9
,
12
}
\{2,3,7,8,9,12\}
{2,3,7,8,9,12}
{
4
,
10
,
13
}
\{4,10,13\}
{4,10,13}
{
2
,
3
,
7
,
8
,
9
,
12
}
\{2,3,7,8,9,12\}
{2,3,7,8,9,12}
{
3
,
7
,
8
,
9
,
11
}
\{3,7,8,9,11\}
{3,7,8,9,11}
{
4
,
8
,
9
,
10
}
\{4,8,9,10\}
{4,8,9,10}
{
2
,
12
}
\{2,12\}
{2,12}
{
4
,
10
,
13
}
\{4,10,13\}
{4,10,13}
∅
\empty
∅
{
2
,
5
,
6
,
11
,
12
}
\{2,5,6,11,12\}
{2,5,6,11,12}
{
4
,
8
,
9
,
10
}
\{4,8,9,10\}
{4,8,9,10}
{
10
}
\{10\}
{10}
{
2
,
5
,
6
,
11
,
12
}
\{2,5,6,11,12\}
{2,5,6,11,12}
{
10
}
\{10\}
{10}
∅
\empty
∅
{
11
}
\{11\}
{11}
{
11
}
\{11\}
{11}
{
8
,
9
}
\{8,9\}
{8,9}
∅
\empty
∅
{
8
,
9
}
\{8,9\}
{8,9}
{
10
}
\{10\}
{10}
{
2
,
12
}
\{2,12\}
{2,12}
重命名
I
I
I
I
0
I_0
I0
I
1
I_1
I10∅11233454∅6523673781089119931012101113512∅61314614∅151516∅16145
终态集合
{
2
,
7
,
8
,
9
,
12
}
\{2,7,8,9,12\}
{2,7,8,9,12},
非终态集合
{
1
,
3
,
4
,
5
,
6
,
10
,
11
}
\{1,3,4,5,6,10,11\}
{1,3,4,5,6,10,11}
拆分后有
{
1
,
5
}
,
{
0
}
,
{
2
}
,
{
3
}
,
{
4
}
,
{
6
}
,
{
7
}
,
{
8
}
,
{
9
}
,
{
10
}
,
{
11
}
,
{
12
}
,
{
13
}
,
{
14
}
,
{
15
}
,
{
16
}
\{1, 5\} , \{0\} , \{2\}, \{3\} , \{4\} , \{6\} ,\{7\} , \{8\} , \{9\}, \{10\} , \{11\} , \{12\}, \{13\}, \{14\} , \{15\}, \{16\}
{1,5},{0},{2},{3},{4},{6},{7},{8},{9},{10},{11},{12},{13},{14},{15},{16}
1和5合并为1后，状态图如下
(3)
0101010的NFA如下图
初态
I
I
I集合为
{
0
,
1
,
2
}
\{0,1,2\}
{0,1,2}
I
I
I
I
0
I_0
I0
I
1
I_1
I1
{
0
,
1
,
2
}
\{0,1,2\}
{0,1,2}
{
1
,
2
}
\{1,2\}
{1,2}
{
3
,
4
,
5
}
\{3,4,5\}
{3,4,5}
{
1
,
2
}
\{1,2\}
{1,2}
{
1
,
2
}
\{1,2\}
{1,2}
{
3
,
4
,
5
}
\{3,4,5\}
{3,4,5}
{
3
,
4
,
5
}
\{3,4,5\}
{3,4,5}
{
4
,
5
}
\{4,5\}
{4,5}
{
6
,
7
,
8
}
\{6,7,8\}
{6,7,8}
{
4
,
5
}
\{4,5\}
{4,5}
{
4
,
5
}
\{4,5\}
{4,5}
{
6
,
7
,
8
}
\{6,7,8\}
{6,7,8}
{
6
,
7
,
8
}
\{6,7,8\}
{6,7,8}
{
7
,
8
}
\{7,8\}
{7,8}
{
9
,
10
,
11
}
\{9,10,11\}
{9,10,11}
{
7
,
8
}
\{7,8\}
{7,8}
{
7
,
8
}
\{7,8\}
{7,8}
{
9
,
10
,
11
}
\{9,10,11\}
{9,10,11}
{
9
,
10
,
11
}
\{9,10,11\}
{9,10,11}
{
10
,
11
}
\{10,11\}
{10,11}
∅
\empty
∅
{
10
,
11
}
\{10,11\}
{10,11}
{
10
,
11
}
\{10,11\}
{10,11}
∅
\empty
∅
重命名
I
I
I
I
0
I_0
I0
I
1
I_1
I101211223433445655667∅77∅
得到未化简DFA
非终态
{
0
,
1
,
2
,
3
,
4
,
5
}
\{0,1,2,3,4,5\}
{0,1,2,3,4,5};终态
{
6
,
7
}
\{6,7\}
{6,7}
显然
{
6
,
7
}
\{6,7\}
{6,7}无须划分
I
(
1
)
I^{(1)}
I(1)
I
0
(
1
)
I^{(1)}_0
I0(1)
I
1
(
1
)
I^{(1)}_1
I1(1)
{
0
,
1
,
2
,
3
,
4
,
5
}
\{0,1,2,3,4,5\}
{0,1,2,3,4,5}
{
1
,
3
,
5
}
\{1,3,5\}
{1,3,5}
{
2
,
4
,
6
}
\{2,4,6\}
{2,4,6}
{
2
,
4
,
6
}
\{2,4,6\}
{2,4,6}不包含于任何划分，需要将能转换为6的状态
4
，
5
4，5
4，5划分
I
(
11
)
=
{
0
,
1
,
2
,
3
}
I
(
12
)
=
{
4
,
5
}
I^{(11)} = \{0,1,2,3\}\quad I^{(12)} = \{4,5\}
I(11)={0,1,2,3}I(12)={4,5}
同理继续划分
I
(
11
)
I^{(11)}
I(11)
I
0
(
11
)
I^{(11)}_0
I0(11)
I
1
(
11
)
I^{(11)}_1
I1(11)
{
0
,
1
,
2
,
3
}
\{0,1,2,3\}
{0,1,2,3}
{
1
,
3
}
\{1,3\}
{1,3}
{
2
,
4
}
\{2,4\}
{2,4}将3与2划分出
I
(
11
)
I^{(11)}
I(11)
I
(
111
)
=
{
0
,
1
}
I
(
112
)
=
{
2
,
3
}
I^{(111)} = \{0,1\}\quad I^{(112)} = \{2,3\}
I(111)={0,1}I(112)={2,3}
最后的划分
{
0
,
1
}
{
2
,
3
}
{
4
,
5
}
{
6
,
7
}
\{0,1\}\quad\{2,3\}\quad\{4,5\}\quad\{6,7\}
{0,1}{2,3}{4,5}{6,7}
经检验，他们经0、1转换后的集合都包含于现有划分
I
I
I
I
0
I_0
I0
I
1
I_1
I1
{
0
,
1
}
\{0,1\}
{0,1}
{
1
}
⊆
{
0
,
1
}
\{1\}\sube\{0,1\}
{1}⊆{0,1}
{
2
}
⊆
{
2
,
3
}
\{2\}\sube\{2,3\}
{2}⊆{2,3}
{
2
,
3
}
\{2,3\}
{2,3}
{
3
}
⊆
{
2
,
3
}
\{3\}\sube\{2,3\}
{3}⊆{2,3}
{
4
}
⊆
{
4
,
5
}
\{4\}\sube\{4,5\}
{4}⊆{4,5}
{
4
,
5
}
\{4,5\}
{4,5}
{
5
}
⊆
{
4
,
5
}
\{5\}\sube\{4,5\}
{5}⊆{4,5}
{
6
}
⊆
{
6
,
7
}
\{6\}\sube\{6,7\}
{6}⊆{6,7}
{
6
,
7
}
\{6,7\}
{6,7}
{
6
}
⊆
{
6
,
7
}
\{6\}\sube\{6,7\}
{6}⊆{6,7}
更名得到最简DFA
(4)
NFA如下
I
I
I
I
0
I_0
I0
I
1
I_1
I1
{
0
,
1
,
4
,
5
,
19
}
\{0,1,4,5,19\}
{0,1,4,5,19}
{
2
,
6
}
\{2,6\}
{2,6}
{
3
,
8
}
\{3,8\}
{3,8}
{
2
,
6
}
\{2,6\}
{2,6}
{
1
,
4
,
5
,
19
}
\{1,4,5,19\}
{1,4,5,19}
{
7
,
9
,
12
}
\{7,9,12\}
{7,9,12}
{
3
,
8
}
\{3,8\}
{3,8}
{
7
,
9
,
12
}
\{7,9,12\}
{7,9,12}
{
1
,
4
,
5
,
19
}
\{1,4,5,19\}
{1,4,5,19}
{
1
,
4
,
5
,
19
}
\{1,4,5,19\}
{1,4,5,19}
{
2
,
6
}
\{2,6\}
{2,6}
{
3
,
8
}
\{3,8\}
{3,8}
{
7
,
9
,
12
}
\{7,9,12\}
{7,9,12}
{
10
,
13
}
\{10,13\}
{10,13}
{
11
,
15
}
\{11,15\}
{11,15}
{
10
,
13
}
\{10,13\}
{10,13}
{
9
,
12
}
\{9,12\}
{9,12}
{
5
,
14
,
16
,
19
}
\{5,14,16,19\}
{5,14,16,19}
{
11
,
15
}
\{11,15\}
{11,15}
{
5
,
14
,
16
,
19
}
\{5,14,16,19\}
{5,14,16,19}
{
9
,
12
}
\{9,12\}
{9,12}
{
9
,
12
}
\{9,12\}
{9,12}
{
10
,
13
}
\{10,13\}
{10,13}
{
11
,
15
}
\{11,15\}
{11,15}
{
5
,
14
,
16
,
19
}
\{5,14,16,19\}
{5,14,16,19}
{
6
,
17
}
\{6,17\}
{6,17}
{
8
,
18
}
\{8,18\}
{8,18}
{
6
,
17
}
\{6,17\}
{6,17}
{
5
,
16
,
19
}
\{5,16,19\}
{5,16,19}
{
7
,
9
,
12
}
\{7,9,12\}
{7,9,12}
{
8
,
18
}
\{8,18\}
{8,18}
{
7
,
9
,
12
}
\{7,9,12\}
{7,9,12}
{
5
,
16
,
19
}
\{5,16,19\}
{5,16,19}
{
5
,
16
,
19
}
\{5,16,19\}
{5,16,19}
{
6
,
17
}
\{6,17\}
{6,17}
{
8
,
18
}
\{8,18\}
{8,18}
重命名
I
I
I
I
0
I_0
I0
I
1
I_1
I1012134243312456578687756891091141041111910
非终态
{
1
,
2
,
4
,
5
,
6
,
7
,
9
,
10
}
\{1,2,4,5,6,7,9,10\}
{1,2,4,5,6,7,9,10};终态
{
0
,
3
,
8
,
11
}
\{0,3,8,11\}
{0,3,8,11}
划分过程略,最终化简
{
3
,
6
,
8
,
11
}
{
1
,
6
,
9
}
{
4
,
7
}
{
2
,
5
,
10
}
\{3,6,8,11\}\quad\{1,6,9\}\quad\{4,7\}\quad\{2,5,10\}
{3,6,8,11}{1,6,9}{4,7}{2,5,10}
8
(1) 01结尾的二进制数串
(
0
∣
1
)
∗
01
(0|1)^*01
(0∣1)∗01
(2) 被5整除的10进制整数
(
(
+
∣
−
)
(
(
(
1
∣
2
∣
3
∣
4
∣
5
∣
6
∣
7
∣
8
∣
9
)
(
0
∣
1
∣
2
∣
3
∣
4
∣
5
∣
6
∣
7
∣
8
∣
9
)
∗
(
0
∣
5
)
)
∣
5
)
)
∣
0
((+|-) (((1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)^*(0|5))|5))|0
((+∣−)(((1∣2∣3∣4∣5∣6∣7∣8∣9)(0∣1∣2∣3∣4∣5∣6∣7∣8∣9)∗(0∣5))∣5))∣0
解释
- 不被括号括住的分隔符的左边是
((+|-)(((1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)^*(0|5))|5)),内部可分为两部分 1. 第一部分(+|-)表示+整数，-负数2. 第二部分(((1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)^*(0|5))|5),可以根据分隔符继续分成两部分 1. 左边部分((1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)^*(0|5))表示至少为2位的能被5整除的正整数2. 5指单独的数字5 - 还有不被括号括住的分隔符的右边表示0
(3) 奇数个1或奇数个0的二进制数串
0
∗
1
(
0
∣
1
0
∗
1
)
∗
∣
1
∗
0
(
1
∣
0
1
∗
0
)
0^*1(0|10^*1)^*\ |\ 1^*0(1|01^*0)
0∗1(0∣10∗1)∗ ∣ 1∗0(1∣01∗0)
12 确定化、最小化下图的(a)(b)
(a)
I
I
I
I
a
I_a
Ia
I
b
I_b
Ib
{
0
}
\{0\}
{0}
{
0
,
1
}
\{0,1\}
{0,1}
{
1
}
\{1\}
{1}
{
0
,
1
}
\{0,1\}
{0,1}
{
0
,
1
}
\{0,1\}
{0,1}
{
1
}
\{1\}
{1}
{
1
}
\{1\}
{1}
{
0
}
\{0\}
{0}
∅
\empty
∅
重命名后为：
I
I
I
I
a
I_a
Ia
I
b
I_b
Ib01211221
∅
\empty
∅
非终态
{
2
}
\{2\}
{2};终态
{
0
,
1
}
\{0,1\}
{0,1}
{
0
,
1
}
a
=
{
1
}
⊆
{
0
,
1
}
\{0,1\}_a = \{1\} \sube \{0,1\}
{0,1}a={1}⊆{0,1}
{
0
,
1
}
b
=
{
2
}
⊆
{
2
}
\{0,1\}_b = \{2\} \sube \{2\}
{0,1}b={2}⊆{2}
已经是最优划分
最简DFA为
(b)
本题已经确定化了，需要进行最小化
考虑到划分
I
(
1
)
=
{
0
,
1
}
与
I
(
2
)
=
{
2
,
3
,
4
,
5
}
I^{(1)} = \{0,1\}与 I^{(2)} = \{2,3,4,5\}
I(1)={0,1}与I(2)={2,3,4,5}
I
a
(
2
)
=
{
0
,
1
,
3
,
5
}
I^{(2)}_a = \{0,1,3,5\}
Ia(2)={0,1,3,5}
需要划分为
I
(
21
)
=
{
2
,
3
}
I
(
22
)
=
{
4
,
5
}
I^{(21)} = \{2,3\}\quad I^{(22)} = \{4,5\}
I(21)={2,3}I(22)={4,5}
最终将$ {0,1}\quad {2,3}\quad {4,5}$重命名
14
构造DFS，令其满足
∑
=
{
0
,
1
}
∧
“每个
1
都有
0
直接跟在右边”的字符串
\sum = \{0,1\} \land “每个1都有0直接跟在右边”的字符串
∑={0,1}∧“每个1都有0直接跟在右边”的字符串
正规式
(0|10)^*
NFA
I
I
I
I
0
I_0
I0
I
1
I_1
I1
{
X
,
0
,
Y
}
\{X,0,Y\}
{X,0,Y}
{
0
,
Y
}
\{0,Y\}
{0,Y}
{
1
}
\{1\}
{1}
{
0
,
Y
}
\{0,Y\}
{0,Y}
{
0
,
Y
}
\{0,Y\}
{0,Y}
{
1
}
\{1\}
{1}
{
1
}
\{1\}
{1}
{
0
,
Y
}
\{0,Y\}
{0,Y}
∅
\empty
∅
重命名的DFA如下
观察划分
{
0
,
1
}
与
{
2
}
\{0,1\}与\{2\}
{0,1}与{2}
显然0，1可以进行合并，得到最简DFA
标签：
编辑器
本文转载自: https://blog.csdn.net/JamSlade/article/details/129735031
版权归原作者 JamSlade 所有， 如有侵权，请联系我们删除。
版权归原作者 JamSlade 所有， 如有侵权，请联系我们删除。