《编译原理（第三版）》陈意云著

第 二 章 课 后 习 题

T 2.3

叙述由下列正规式描述的语言

1. $0(0|1{)}^{\ast }0$

   正规式规定开头和结尾必须包括0，中间由0或1的闭包构成，可以看出该正规式描述的语言包含的串长度至少为2，所以总结为：以0开头和结尾的长度至少是2的串01.

2. $((\epsilon |0)1^{\ast }{)}^{\ast }$

   内层括号中是对空和0的选择，再与外面的1的闭包相连接，可能构成的串有：$\epsilon$、$1$、$\mathrm{1...1}$ 、$0$、$01$、$\mathrm{01...1}$，再加上外层的闭包，可以让 $0$ 的个数变成任意多且可以为空串的闭包，所以总结为：所有的01串（包含空串）.

3. $(0|1{)}^{\ast }0(0|1)(0|1)$

   $0(0|1)(0|1)$描述了长度为3，第一位为0的01串，在前面加上0或1的闭包使得串可以以任意二进制或空开头，所以结论为：至少包括三位且倒数第三位是0的01串.

4. $0{}^{\ast }10{}^{\ast }10{}^{\ast }10{}^{\ast }$

   三个1是必然存在于串中的，而剩下0的闭包则说明0的个数为任意多，所以结论为：含有三个1的01串.

5. $(00|11){}^{\ast }((01|10)(00|11){}^{\ast }(01|10)(00|11){}^{\ast }){}^{\ast }$

   第一个闭包可以选择00或11，后面的两个内层闭包所描述的语言与第一个闭包相同，外层闭包让其内部的串可以出现任意次。由于该正规式过于复杂，所以可以将其描述的语言简单概括为：含有偶数（含0个）个0和偶数（含0个）个1的01串.

---

T 2.4

为下列语言写出正规定义

1. 包含5个元音的所有字母串，其中每个元音只出现一次且按顺序排列。

   不含五个元音的任意字符：$[B-DF-HJ-NP-TV-Zb-df-hj-np-tv-z]$，记为$\alpha$

   故，$\alpha {}^{\ast }(a|A)\alpha {}^{\ast }(e|E)\alpha {}^{\ast }(i|I)\alpha {}^{\ast }(o|O)\alpha {}^{\ast }(u|U)\alpha {}^{\ast }$

2. 按词典序排列的所有字母串。

   $A{}^{\ast }a{}^{\ast }B{}^{\ast }b{}^{\ast }...Z{}^{\ast }z{}^{\ast }$

3. 某语言的注释，它是以$/\ast$开始并以$\ast /$结束的任意字符串，但它的任何前缀（本身除外）不以$\ast /$结尾。

   不含$/$，$\ast$的任意字符记为$\alpha$

   不含$\ast /$的任意字符串可以表示为$({\ast }^{\ast }{\alpha }^{+}{/}^{\ast }{)}^{\ast }$

   故，$/\ast ({\ast }^{\ast }{\alpha }^{+}{/}^{\ast }{)}^{\ast }\ast /$

4. 相邻数字都不相同的所有数字串。

5. 最多只有一处相邻数字相同的所有数字串。

6. 由偶数个0和偶数个1组成的所有01串。

   $(00|11){}^{\ast }((01|10)(00|11){}^{\ast }(01|10)(00|11){}^{\ast }){}^{\ast }$

7. 由偶数个0和奇数个1组成的所有01串。

   $1(00|11){}^{\ast }((01|10)(00|11){}^{\ast }(01|10)(00|11){}^{\ast }){}^{\ast }$

8. 不含字串011的01串。

   $(1{}^{\ast }(0{}^{+}1){}^{\ast })0{}^{\ast }$

9. 字母表 { a , b } \{a, b\} {a,b}上，$a$不会相邻出现的所有串。

   $b{}^{\ast }(a?b{}^{+}){}^{\ast }a?$

---

T 2.7

用算法 2.4 为下列正规式构造不确定有限自动机，给出它们处理输入串 $ababbab$ 的状态转化序列

1. $(a|b){}^{\ast }$

方式一：（算法 2.4）

$$\begin{gathered} ababbab:s\to 0\to 1\to 3\to 5\to 0\to 2\to 4\to 5\to 0\to 1\to 3\to 5\to 0\to 2 \\ \to 4\to 5\to 0\to 2\to 4\to 5\to 0\to 1\to 3\to 5\to 0\to 2\to 4\to 5\to f \end{gathered}$$

方式二：（分裂法）

$ababbab:s\to 0\to 1\to 0\to 1\to 0\to 1\to 0\to 1\to 0\to 1\to 0\to 1\to 0\to 1\to f$

方式三：

$ababbab:s\to 0\to 0\to 0\to 0\to 0\to 0\to 0\to 0\to f$

2. $(a{}^{\ast }|b{}^{\ast }){}^{\ast }$

$$\begin{gathered} ababbab:s\to 0\to 1\to 3\to 5\to 0\to 2\to 4\to 5\to 0\to 1\to 3\to 5\to 0 \\ \to 2\to 4\to 2\to 4\to 5\to 0\to 1\to 3\to 5\to 0\to 2\to 4\to 4\to f \end{gathered}$$

3. $((\epsilon |a)b{}^{\ast }){}^{\ast }$

$$\begin{gathered} ababbab:s\to 0\to 1\to 3\to 5\to 6\to 7\to 8\to 0\to 1\to 3\to 5\to 6 \\ \to 7\to 6\to 7\to 8\to 0\to 1\to 3\to 5\to 6\to 7\to 8\to f \end{gathered}$$

4. $(a|b){}^{\ast }abb(a|b){}^{\ast }$

$ababbab:s\to 0\to 1\to 3\to 5\to 0\to 2\to 4\to 5\to 6\to 7\to 8\to 9\to 10\to 11\to 13\to 15\to 10\to 12\to 14\to 15\to f$

---

T 2.8

用算法2.2把习题2.7中的第三问的NFA变换成DFA。给出它们处理输入串 $ababbab$ 的状态转换序列

为了书写的方便，将上面 NFA 中的状态重新编号，得到下图：

上图的 NFA 等价的 DFA 的开始状态是 $\epsilon -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} ，计算 $\epsilon -closure(move(A,a))$，由于只有状态 $2$ 能发生 $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$；

计算 $\epsilon -closure(move(A,b))$，由于只有状态 $7$ 能发生 $b$ 转换，所以 $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$；

对新集合 $B$ 和 $C$ 重复上面的过程可以得到完整的转换表如下：

状态	输入符号
	a	b
A	B	C
B	B	C
C	B	C

根据转换表得到等价的 DFA 如下：

$ababbab:A\to B\to C\to B\to C\to C\to B\to C$

---

T 2.11

可以从正规式的最简 DFA 同构来证明两个正规式等价。使用这种计数，证明正规式 $(a|b){}^{\ast }$、$(a{}^{\ast }|b{}^{\ast }){}^{\ast }$ 和 $((\epsilon |a)b{}^{\ast }){}^{\ast }$ 等价

与 T 2.8 类似，先将上面的 NFA 中的状态重新编号便于计算。

$(a|b){}^{\ast }$ 对应的 NFA：

$(a|b){}^{\ast }$ 对应的状态转换表：

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}

状态	输入符号
	a	b
A	B	C
B	B	C
C	B	C

$(a|b){}^{\ast }$ 对应的 DFA：

$(a|b){}^{\ast }$ 对应的最简 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{}^{\ast }|b{}^{\ast }){}^{\ast }$ 对应的 NFA：

$(a{}^{\ast }|b{}^{\ast }){}^{\ast }$ 对应的状态转换表：

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}

状态	输入符号
	a	b
A	B	C
B	B	C
C	B	C

$(a{}^{\ast }|b{}^{\ast }){}^{\ast }$ 对应的 DFA：

$(a{}^{\ast }|b{}^{\ast }){}^{\ast }$ 对应的最简 DFA：

由于 $(a{}^{\ast }|b{}^{\ast }){}^{\ast }$ 对应的 DFA 与 $(a|b){}^{\ast }$ 对应的 DFA 完全一致，所以最终化简得到的 DFA 也是一样的，即上图。

---

$((\epsilon |a)b{}^{\ast }){}^{\ast }$ 的 DFA 在 T 2.8 中已经得到，由于其与 $(a|b){}^{\ast }$ 对应的 DFA 完全一致，所以最终化简得到的 DFA 也是一样的，即：

由于已知“最简 DFA 同构的正规式等价”可知，三者的最简 DFA 同构，所以三个正规式等价。

---

T 2.12

为下列正规式构造最简的 DFA

1. $(a|b){}^{\ast }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}

状态	输入符号
	a	b
A	B	C
B	D	E
C	B	C
D	D	E
E	B	C

对应的 DFA 如下：

对应的最简 DFA 如下：

初始划分两个子集：接受状态子集 { D , E } \{D,E\} {D,E} 和非接受状态子集 { A , B , C } \{A,B,C\} {A,B,C}；

对于接受状态子集，输入字符 $a$，状态 $D$ 和状态 $E$ 分别变换到状态 $D$ 和状态 $B$，二者不在同一子集中，所以需要划分成 { D } \{D\} {D}、 { E } \{E\} {E}；

对于非接受状态子集，输入字符 $a$，状态 $A$ 和状态 $C$ 均变换到状态 $B$，而状态 $B$ 变换到状态 $D$，属于另一个子集，所以初步划分为 { A , C } \{A,C\} {A,C}、 { B } \{B\} {B}；输入字符 $b$，状态 $A$ 和状态 $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$， { B } \{B\} {B} 为状态 $1$， { D } \{D\} {D} 为状态 $2$， { E } \{E\} {E} 为状态 $3$。

---

2. $(a|b){}^{\ast }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}

状态	输入符号
	a	b
A	B	C
B	D	E
C	B	C
D	F	G
E	H	I
F	F	G
G	H	I
H	D	E
I	B	C

方法二： 分裂法得到的 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}

状态	输入符号
	a	b
A	B	C
B	D	E
C	B	C
D	F	G
E	H	I
F	F	G
G	H	I
H	D	E
I	B	C

可以看出“子集构造法”和“分裂法”得到的状态转换表一样，所以化出的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$ 和字符 $b$，可将原集合划分为 { F , G } \{F,G\} {F,G} 和 { H , I } \{H,I\} {H,I}；

对于非接受状态子集，分别输入字符 $a$ 和字符 $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$， { B } \{B\} {B} 为状态 $1$， { D } \{D\} {D} 为状态 $2$， { E } \{E\} {E} 为状态 $3$， { F } \{F\} {F} 为状态 $4$、 { G } \{G\} {G} 为状态 $5$ 、 { H } \{H\} {H} 为状态 $6$、 { I } \{I\} {I} 为状态 $7$。

---

3. $(a|b){}^{\ast }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}

状态	输入符号
	a	b
A	B	C
B	D	E
C	B	C
D	F	G
E	H	I
F	J	K
G	L	M
H	N	O
I	P	Q
J	J	K
K	L	M
L	N	O
M	P	Q
N	F	G
O	H	I
P	D	E
Q	B	C

可以看出“子集构造法”和“分裂法”得到的状态转换表一样，所以化出的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}

状态	输入符号
	a	b
A	B	C
B	D	E
C	B	C
D	F	G
E	H	I
F	J	K
G	L	M
H	N	O
I	P	Q
J	J	K
K	L	M
L	N	O
M	P	Q
N	F	G
O	H	I
P	D	E
Q	B	C

对应的 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$， { B } \{B\} {B} 为状态 $1$， { D } \{D\} {D} 为状态 $2$， { E } \{E\} {E} 为状态 $3$， { F } \{F\} {F} 为状态 $4$、 { G } \{G\} {G} 为状态 $5$ 、 { H } \{H\} {H} 为状态 $6$、 { I } \{I\} {I} 为状态 $7$， { J } \{J\} {J} 为状态 $8$， { K } \{K\} {K} 为状态 $9$， { L } \{L\} {L} 为状态 $10$， { M } \{M\} {M} 为状态 $11$， { N } \{N\} {N} 为状态 $12$、 { O } \{O\} {O} 为状态 $13$ 、 { P } \{P\} {P} 为状态 $14$、 { Q } \{Q\} {Q} 为状态 $15$。

---

T 2.13

构造一个 DFA，它接受 Σ = { 0 , 1 } \Sigma=\{0,1\} Σ={0,1} 上 $0$ 和 $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取模，存在五种结果，结果为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$ 的二进制整数

根据题意，先简单地将状态分为六种，为$0$、$1$、$2$、$3$、$4$、$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$，状态 $1$ 转换到状态 $2$，状态 $2$ 转换到状态 $4$，状态 $3,4,5$ 均转换到状态 $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$ 转换到状态 $1$，状态 $1$ 转换到状态 $3$，状态 $2$ 转换到状态 $5$，状态 $3,4,5$ 均转换到状态 $6$。

由于 $0,1,2,3,4,5$ 属于同一个子集，所以 $0,1,2$ 仍属于同一子集，而由于 $3,4,5$ 转换到了另一个不同的子集中，所以 $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$，状态 $1$ 转换到状态 $2$，状态 $2$ 转换到状态 $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$ 转换到状态 $1$，状态 $1$ 转换到状态 $3$，状态 $2$ 转换到状态 $5$。

在输入字符为$0$的情况下，状态 $0$ 和 状态 $1$ 均转换到同一集合 { 0 ,   1 ,   2 } \{0,\space 1,\space2\} {0, 1, 2} 中，但是状态 $2$ 转换到了另一个集合 { 3 ,   4 ,   5 } \{3,\space4,\space5\} {3, 4, 5} 中，所以状态 $2$ 将被划分到与状态 $0$ 和状态 $1$ 不同的子集中；在输入字符为$1$的情况下，状态 $0$ 转换到子集 { 0 ,   1 ,   2 } \{0,\space 1,\space2\} {0, 1, 2} 中，而状态 $1$ 转移到子集 { 3 ,   4 ,   5 } \{3,\space4,\space5\} {3, 4, 5} 中，根据子集划分的要求“两个状态 $s$ 和 $t$ 被划分到同一子集中，当且仅当对任意输入符号 $\alpha$，状态 $s$ 和 $t$ 转换到本次划分前的同一子集中”，所以状态 $0$ 和 状态 $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 如下：