有穷自动机

确定性有穷自动机

定义

1. 有穷状态集合$Q$
2. 有穷的输入符号集合$\Sigma$
3. 转移函数 $\delta$。以一个状态和一个输入符号作为变量，返回一个状态。
4. 初始状态 $q_0\in Q$。
5. 接受状态的集合$F$。$F$为$Q$的子集。

$$A=(Q,\Sigma ,\delta ,q_0,F)$$

DFA处理串

输入序列$a_1{a}_2{a}_3\dots a_n$，从出事状态$q_0$开始，逐个处理每个输入符号，得到状态$q_1,q_2,q_3,\dots ,q_n$，如果$q_n$属于$F$则接受输入，否则拒绝。

转移图

例：接受所有带子串01的串的DFA的转移图。

\usetikzlibrary{automata, positioning, arrows}
\tikzset{
	->, % makes the edges directed
	>=stealth, % makes the arrow heads bold
	node distance=2.5cm, % specifies the minimum distance between two nodes. Change if necessary.
	every state/.style={thick}, % sets the properties for each ’state’ node
	initial text=$Start$, % sets the text that appears on the start arrow
}
\begin{document}
	\begin{tikzpicture}
		\node[state, initial] (q0) {$q_0$};
		\node[state, right of=q0] (q2) {$q_2$};
		\node[state, accepting, right of=q2] (q1) {$q_1$};
		\draw (q0) edge[loop above] node{1} (q0)
			(q0) edge[above] node{0} (q2)
			(q1) edge[loop above] node{0,1} (q1)
			(q2) edge[loop above] node{0} (q2)
			(q2) edge[above] node{1} (q1);
	\end{tikzpicture}
\end{document}

转移表

	0	1
$q_0$	$q_2$	$q_0$
$q_1$	$q_1$	$q_1$
$q_2$	$q_2$	$q_1$

转移函数扩展到串

扩展转移函数$\hat{\delta }$。 接收状态$q$和串$w$，返回状态$p$，$p$是$q$开始处理输入序列$w$后达到的状态。

DFA的语言

$$L(A)=\{w|\hat{\delta }(q_0,w)属于F\}$$

如果某个语言 $L$ 是某个DFA A的 $L(A)$，则可以证明 $L$ 是一个正规语言。

Example

$\sigma ={\left\{0,1\right\}}^{\ast }$ 上的语言 $L=\left\{w|w中0和1的数目的奇偶性相同\right\}$ 是一个正规语言，可证 $L$ 是以下 DFA 的语言。

\usetikzlibrary{automata, positioning, arrows}
\tikzset{
	->, % makes the edges directed
	>=stealth, % makes the arrow heads bold
	node distance=2.5cm, % specifies the minimum distance between two nodes. Change if necessary.
	every state/.style={thick}, % sets the properties for each ’state’ node
	initial text=$Start$, % sets the text that appears on the start arrow
}
\begin{document}
	\begin{tikzpicture}
		\node [state, initial, accepting] (q0) {$q_0$};
		\node [state, right of=q0] (q1) {$q_1$};
		\node [state, below of=q0] (q2) {$q_2$};
		\node [state, accepting, right of=q2] (q3) {$q_3$};
		\draw (q0) edge[bend left, above] node{1} (q1)
			(q0) edge[bend left, right] node{0} (q2)
			(q1) edge[bend left, below] node{1} (q0)
			(q1) edge[bend left, right] node{0} (q3)
			(q2) edge[bend left, left] node{0} (q0)
			(q2) edge[bend left, above] node{1} (q3)
			(q3) edge[bend left, below] node{1} (q2)
			(q3) edge[bend left, left] node{0} (q1);
	\end{tikzpicture}
\end{document}

---

互归纳法：$P_0(n):{\delta }^{\prime }(q_0,w)=q_0$ 当且仅当 $w$ 有偶数个 0 和偶数个 1，$P_1(n),P_2(n),P_3(n)$ 类似。

DFA 的设计

以下例题默认 $\Sigma ={\left\{0,1\right\}}^{\ast }$。

例 1

$\Sigma ={\left\{0,1\right\}}^{\ast }$，所有以 00 结尾的串。

---

\usetikzlibrary{automata, positioning, arrows}
\tikzset{
	->, % makes the edges directed
	>=stealth, % makes the arrow heads bold
	node distance=2.5cm, % specifies the minimum distance between two nodes. Change if necessary.
	every state/.style={thick}, % sets the properties for each ’state’ node
	initial text=$Start$, % sets the text that appears on the start arrow
}
\begin{document}
	\begin{tikzpicture}
		\node [state, initial] (q0) {$q_0$};
		\node [state, right of=q0] (q1) {$q_1$};
		\node [state, right of=q1] (q2) {$q_2$};
		\draw (q0) edge[bend left, above] node{0} (q1)
			(q1) edge[bend left, below] node{1} (q0)
			(q1) edge[above] node{0} (q2)
			(q0) edge[loop above, above] node{1} (q0)
			(q2) edge[bend left, below] node{1} (q0)
			(q2) edge[loop above, above] node{0} (q2);
	\end{tikzpicture}
\end{document}

例 2

$$L=\left\{x\in {\left\{0,1\right\}}^{\ast }\wedge x中至少包含一个子串010\right\}$$

---

\usetikzlibrary{automata, positioning, arrows}
\tikzset{
	->, % makes the edges directed
	>=stealth, % makes the arrow heads bold
	node distance=2.5cm, % specifies the minimum distance between two nodes. Change if necessary.
	every state/.style={thick}, % sets the properties for each ’state’ node
	initial text=$Start$, % sets the text that appears on the start arrow
}
\begin{document}
	\begin{tikzpicture}
		\node [state, initial] (q0) {$q_0$};
		\node [state, right of=q0] (q1) {$q_1$};
		\node [state, right of=q1] (q2) {$q_2$};
		\node [state, right of=q2, accepting] (q3) {$q_3$};
		\draw (q0) edge[bend left, above] node{0} (q1)
			(q1) edge[above] node{1} (q2)
			(q2) edge[above] node{0} (q3)
			(q3) edge[loop above, above] node{0,1} (q3)
			(q0) edge[loop above, above] node{1} (q0)
			(q1) edge[loop above, above] node{0} (q1)
			(q2) edge[bend left, below] node{1} (q0);
	\end{tikzpicture}
\end{document}

例 3

$L=\left\{x\in {\left\{0,1\right\}}^{\ast }\wedge x中不包含子串010\right\}$

---

正难则反！可以从补集入手考虑

\usetikzlibrary{automata, positioning, arrows}
\tikzset{
	->, % makes the edges directed
	>=stealth, % makes the arrow heads bold
	node distance=2.5cm, % specifies the minimum distance between two nodes. Change if necessary.
	every state/.style={thick}, % sets the properties for each ’state’ node
	initial text=$Start$, % sets the text that appears on the start arrow
}
\begin{document}
	\begin{tikzpicture}
		\node [state, initial, accepting] (q0) {$q_0$};
		\node [state, right of=q0, accepting] (q1) {$q_1$};
		\node [state, right of=q1, accepting] (q2) {$q_2$};
		\node [state, right of=q2] (q3) {$q_3$};
		\draw (q0) edge[bend left, above] node{0} (q1)
			(q1) edge[above] node{1} (q2)
			(q2) edge[above] node{0} (q3)
			(q3) edge[loop above, above] node{0,1} (q3)
			(q0) edge[loop above, above] node{1} (q0)
			(q1) edge[loop above, below] node{0} (q1)
			(q2) edge[bend left, below] node{1} (q0);
	\end{tikzpicture}
\end{document}

例 4

长度至少为 2 且头两个字符不同。

---

\usetikzlibrary{automata, positioning, arrows}
\tikzset{
	->, % makes the edges directed
	>=stealth, % makes the arrow heads bold
	node distance=2.5cm, % specifies the minimum distance between two nodes. Change if necessary.
	every state/.style={thick}, % sets the properties for each ’state’ node
	initial text=$Start$, % sets the text that appears on the start arrow
}
\begin{document}
	\begin{tikzpicture}
		\node [state, initial] (q0) {$q_0$};
		\node [state, right of=q0, yshift=2cm] (q1) {$q_1$};
		\node [state, right of=q0, yshift=-2cm] (q2) {$q_2$};
		\node [state, right of=q1, yshift=-2cm, accepting] (q3) {$q_3$};
		\node [state, right of=q0] (q4) {$q_4$};
		\draw (q0) edge[left] node{0} (q1)
			(q0) edge[left] node{1} (q2)
			(q1) edge[left] node{0} (q4)
			(q2) edge[left] node{1} (q4)
			(q1) edge[right] node{1} (q3)
			(q2) edge[right] node{0} (q3)
			(q3) edge[loop right, right] node{0,1} (q3)
			(q4) edge[loop right, right] node{0,1} (q4);
	\end{tikzpicture}
\end{document}

例 5

子串 01 出现的次数为奇数。

---

初始状态为子串 01 出现次数为偶数。

\usetikzlibrary{automata, positioning, arrows}
\tikzset{
	->, % makes the edges directed
	>=stealth, % makes the arrow heads bold
	node distance=2.5cm, % specifies the minimum distance between two nodes. Change if necessary.
	every state/.style={thick}, % sets the properties for each ’state’ node
	initial text=$Start$, % sets the text that appears on the start arrow
}
\begin{document}
	\begin{tikzpicture}
		\node [state, initial] (q0) {$q_0$};
		\node [state, right of=q0] (q1) {$q_1$};
		\node [state, right of=q1, accepting] (q2) {$q_2$};
		\node [state, right of=q2, accepting] (q3) {$q_3$};
		\draw (q0) edge[above] node{0} (q1)
			(q1) edge[above] node{1} (q2)
			(q2) edge[above] node{0} (q3)
			(q3) edge[bend left, below] node{1} (q0)
			(q0) edge[loop above, above] node{1} (q0)
			(q1) edge[loop above, above] node{0} (q1)
			(q2) edge[loop above, above] node{1} (q2)
			(q3) edge[loop above, above] node{0} (q3);
	\end{tikzpicture}
\end{document}

例 6

包含相同个数的 0 和 1 且每个前缀的 0 和 1 个数之差不超过 1

---

初始状态 0 和 1 个数相等。

\usetikzlibrary{automata, positioning, arrows}
\tikzset{
	->, % makes the edges directed
	>=stealth, % makes the arrow heads bold
	node distance=2.5cm, % specifies the minimum distance between two nodes. Change if necessary.
	every state/.style={thick}, % sets the properties for each ’state’ node
	initial text=$Start$, % sets the text that appears on the start arrow
}
\begin{document}
	\begin{tikzpicture}
		\node [state, initial, accepting] (q0) {$q_0$};
		\node [state, right of=q0, yshift=2cm] (q1) {$q_1$};
		\node [state, right of=q0, yshift=-2cm] (q2) {$q_2$};
		\node [state, right of=q1, yshift=-2cm] (q3) {$q_3$};
		\draw (q0) edge[bend left, left] node{0} (q1)
			(q0) edge[bend left, right] node{1} (q2)
			(q1) edge[bend left, right] node{1} (q0)
			(q2) edge[bend left, left] node{0} (q0)
			(q1) edge[right, bend left] node{0} (q3)
			(q2) edge[right, bend right] node{1} (q3)
			(q3) edge[loop right, right] node{0,1} (q3);
	\end{tikzpicture}
\end{document}

例 7

包含子串 01 但不包含子串 11

---

\usetikzlibrary{automata, positioning, arrows}
\tikzset{
	->, % makes the edges directed
	>=stealth, % makes the arrow heads bold
	node distance=2.5cm, % specifies the minimum distance between two nodes. Change if necessary.
	every state/.style={thick}, % sets the properties for each ’state’ node
	initial text=$Start$, % sets the text that appears on the start arrow
}
\begin{document}
	\begin{tikzpicture}
		\node [state, initial] (q0) {$q_0$};
		\node [state, right of=q0, yshift=1cm] (q1) {$q_1$};
		\node [state, right of=q0, yshift=-1cm] (q2) {$q_2$};
		\node [state, right of=q1, accepting] (q3) {$q_3$};
		\node [state, right of=q2] (q4) {$q_4$};
		\node [state, right of=q3, accepting] (q5) {$q_5$};
		\draw (q0) edge[left] node{0} (q1)
			(q0) edge[left] node{1} (q2)
			(q1) edge[above] node{1} (q3)
			(q1) edge[loop above, above] node{0} (q1)
			(q2) edge[left] node{0} (q1)
			(q2) edge[above] node{1} (q4)
			(q4) edge[loop right, right] node{0,1} (q4)
			(q3) edge[bend left, above] node{0} (q5)
			(q5) edge[bend left, below] node{1} (q3)
			(q3) edge[right] node{1} (q4)
			(q5) edge[loop right, right] node{0} (q5);
	\end{tikzpicture}
\end{document}

注意不要漏掉 $q_5$ 的状态

例 8

所有能被 3 整除的二进制数

---

设 3 个节点分别表示当前的串模 3 余 0，1，2.

\usetikzlibrary{automata, positioning, arrows}
\tikzset{
	->, % makes the edges directed
	>=stealth, % makes the arrow heads bold
	node distance=2.5cm, % specifies the minimum distance between two nodes. Change if necessary.
	every state/.style={thick}, % sets the properties for each ’state’ node
	initial text=$Start$, % sets the text that appears on the start arrow
}
\begin{document}
	\begin{tikzpicture}
		\node [state, initial] (s) {$s$};
		\node [state, accepting, right of=s] (q0) {$q_0$};
		\node [state, below of=q0] (q1) {$q_1$};
		\node [state, below of=s] (q2) {$q_2$};
		\draw (s) edge[above] node{0} (q0)
			(s) edge[above] node{1} (q1)
			(q0) edge[bend left, right] node{1} (q1)
			(q0) edge[loop above, above] node{0} (q0)
			(q1) edge[left, bend left] node{1} (q0)
			(q1) edge[below, bend left] node{0} (q2)
			(q2) edge[above, bend left] node{0} (q1)
			(q2) edge[loop left, left] node{1} (q2);
	\end{tikzpicture}
\end{document}

非确定型有穷自动机

定义

1. 有穷状态集合 $Q$
2. 有穷的输入符号集合$\Sigma$
3. 转移函数 $\delta$。以一个状态和一个输入符号作为变量，返回一个状态集合（可以为空）。
4. 初始状态。
5. 接受状态的集合$F$。$F$为$Q$的子集。

$$A=(Q,\Sigma ,\delta ,q_0,F)$$

NFA 与 DFA 的区别

DFA 中的 $\delta$ 的返回值是恰好的一个状态，而 NFA 中的 $\delta$ 是一个状态集合。

扩展转移函数

扩展转移函数 $\hat{\delta }$ 接收状态 $q$ 和输入符号串 $w$，返回一个状态集合。

NFA 的语言

设一个 NFA $A=(Q,\Sigma ,\delta ,q_0,F)$ ，定义 A 的语言为

$$L(A)=\left\{w|w\in {\Sigma }^{\ast }\wedge {\delta }^{\prime }(q_0,w)\cap F\ne \varnothing \right\}$$

设 $L$ 是 $\Sigma$ 上的语言，若存在 NFA A 满足 $L=L(A)$，则可以证明 L 是一个正规语言。

NFA 的设计

以下默认 $\Sigma =\left\{0,1\right\}$

例 1

所有长度至少为 2 且头两个字符不同的串

---

NFA 不要求每个状态对每个不同的输入都有一个对应的状态。

\usetikzlibrary{automata, positioning, arrows}
\tikzset{
	->, % makes the edges directed
	>=stealth, % makes the arrow heads bold
	node distance=2.5cm, % specifies the minimum distance between two nodes. Change if necessary.
	every state/.style={thick}, % sets the properties for each ’state’ node
	initial text=$Start$, % sets the text that appears on the start arrow
}
\begin{document}
	\begin{tikzpicture}
		\node [state, initial] (q0) {$q_0$};
		\node [state, right of=q0, yshift=2cm] (q1) {$q_1$};
		\node [state, right of=q0, yshift=-2cm] (q2) {$q_2$};
		\node [state, right of=q1, yshift=-2cm, accepting] (q3) {$q_3$};
		\draw (q0) edge[left] node{0} (q1)
			(q0) edge[left] node{1} (q2)
			(q1) edge[right] node{1} (q3)
			(q3) edge[loop right, right] node{0,1} (q3)
			(q2) edge[right] node{0} (q3);
	\end{tikzpicture}
\end{document}

例 2

所有长度至少为 3 且第二和第三个字符不同的串

---

\usetikzlibrary{automata, positioning, arrows}
\tikzset{
	->, % makes the edges directed
	>=stealth, % makes the arrow heads bold
	node distance=2.5cm, % specifies the minimum distance between two nodes. Change if necessary.
	every state/.style={thick}, % sets the properties for each ’state’ node
	initial text=$Start$, % sets the text that appears on the start arrow
}
\begin{document}
	\begin{tikzpicture}
		\node [state, initial] (q0) {$q_0$};
		\node [state, right of = q0] (q1) {$q_1$};
		\node [state, right of = q1, yshift = 2cm] (q2) {$q_2$};
		\node [state, right of = q1, yshift = -2cm] (q3) {$q_3$};
		\node [state, right of = q2, yshift = -2cm, accepting] (q4) {$q_4$};
		\draw (q0) edge[above] node{0,1} (q1)
			(q1) edge[left] node{0} (q2)
			(q1) edge[left] node{1} (q3)
			(q2) edge[right] node{1} (q4)
			(q3) edge[right] node{0} (q4)
			(q4) edge[loop right, right] node{0,1} (q4);
	\end{tikzpicture}
\end{document}

例 3

长度至少为 2 且后两个字符不同且不含 2 的 0、1 和 2 组成的串

---

\usetikzlibrary{automata, positioning, arrows}
\tikzset{
	->, % makes the edges directed
	>=stealth, % makes the arrow heads bold
	node distance=2.5cm, % specifies the minimum distance between two nodes. Change if necessary.
	every state/.style={thick}, % sets the properties for each ’state’ node
	initial text=$Start$, % sets the text that appears on the start arrow
}
\begin{document}
	\begin{tikzpicture}
		\node [state, initial] (q0) {$q_0$};
		\node [state, right of = q0, yshift = 2cm] (q1) {$q_1$};
		\node [state, right of = q0, yshift = -2cm] (q2) {$q_2$};
		\node [state, right of = q1, yshift = -2cm, accepting] (q3) {$q_3$};
		\draw (q0) edge[loop above, above] node{0,1,2} (q0)
			(q0) edge[left] node{0} (q1)
			(q0) edge[left] node{1} (q2)
			(q1) edge[right] node{1} (q3)
			(q2) edge[right] node{0} (q3);
	\end{tikzpicture}
\end{document}

DFA 与 NFA 对比

	DFA	NFA
分析歧义	无	有
设计难度	高	低

DFA 和 NFA 的等价性

Theorem

$L$ 是一个 DFA 的语言 $\iff L$ 是一个 NFA 的语言

Proof

从 DFA 构造等价的 NFA： $D=(Q,\Sigma ,{\delta }_D,q_0,F)$，$N=(Q,\Sigma ,{\delta }_S,q_0,F)$，若 ${\delta }_D(q,a)=p$ 则令 ${\delta }_N(q,a)=\left\{p\right\}$，易证 ${\delta }_D(q_0,w)=p\iff {\delta }_N(q_0,w)=\left\{p\right\}$

从 NFA 构造等价的 DFA（子集构造法）： $N=Q_N,\Sigma ,{\delta }_N,q_0,F_N$ 定义 $D=(Q_D,\Sigma ,{\delta }_D,\{q_0\},F_D)$，其中

• $Q_D=\left\{S|S\subseteq Q_N\right\}$
• $F_D=\{S|S\subseteq Q_N\wedge S\cap F_N\ne \varnothing \}$
• ${\delta }_D(S,a)={\bigcup }_{q\in S}{\delta }_N(q,a)$ 易证 ${\delta }_D^{\prime }(\{q_0\},w)={\delta }_N^{\prime }(q_0,w)$

例 1

	0	1
$\to p$	$\{q\}$	$\varnothing$
$q$	$\{q\}$	$\{q,r\}$
$\ast r$	$\varnothing$	$\varnothing$
转换后可能有多个状态不可达，可以删去

	0	1
$\varnothing$	$\varnothing$	$\varnothing$
$\to \{p\}$	$\{q\}$	$\varnothing$
$\{q\}$	$\{q\}$	$\{q,r\}$
$\ast \{q,r\}$	$\{q\}$	$\{q,r\}$

例 2

	0	1
$\to p$	$\{p,q\}$	$\{p\}$
$q$	$\{r\}$	$\{r\}$
$r$	$\{s\}$	$\varnothing$
$\ast s$	$\{s\}$	$\{s\}$

	0	1
$\to \{p\}$	$\{p,q\}$	$\{p\}$
$\{p,q\}$	$\{p,q,r\}$	$\{p,r\}$
$\{p,r\}$	$\{p,q,s\}$	$\{p\}$
$\{p,s\}$	$\{p,q,s\}$	$\{p,s\}$
$\ast \{p,q,r\}$	$\{p,q,r,s\}$	$\{p,r\}$
$\ast \{p,r,s\}$	$\{p,q,s\}$	$\{p,s\}$
$\ast \{p,q,s\}$	$\{p,q,r,s\}$	$\{p,r,s\}$
$\ast \{p,q,r,s\}$	$\{p,q,r,s\}$	$\{p,r,s\}$

最坏情况下，由 NFA 转化为 DFA 的状态数为指数级增长。

带 $ϵ$ 转移的 NFA

定义

五元组 $A=(Q,\Sigma ,\delta ,q_0,F)$，转移函数 $\delta$ 可以接受 $\Sigma \cup \{ϵ\}$ 作为输入。

$ϵ$ -闭包

状态 $q$ 的 $ϵ$ -闭包记为 $ECLOSE(q)$，表示从 $q$ 开始经所有的 $ϵ$ 路径可以到达的状态（包括 $q$ 自身）的集合。

扩展转移函数

• ${\delta }^{\prime }(q,ϵ)=ECLOSE(q)$
• 若 $w=xa$，其中 $x\in {\Sigma }^{\ast },a\in \Sigma$，设 ${\delta }^{\prime }(q,x)=\{p_1,\dots ,p_k\}$ 且 ${\bigcup }_{i=1}^k\delta (p_i,a)=\{r_1,\dots ,r_m\}$，则 ${\delta }^{\prime }(q,w)={\bigcup }_{i=1}^{m}ECLOSE(r_i)$

$ϵ-NFA$ 的设计

例 1

长度至少为 1，前三个符号中至少有一个 0

---

\usetikzlibrary{automata, positioning, arrows}
\tikzset{
	->, % makes the edges directed
	>=stealth, % makes the arrow heads bold
	node distance=2.5cm, % specifies the minimum distance between two nodes. Change if necessary.
	every state/.style={thick}, % sets the properties for each ’state’ node
	initial text=$Start$, % sets the text that appears on the start arrow
}
\begin{document}
	\begin{tikzpicture}
		\node [state, initial] (q0) {$q_0$};
		\node [state, right of = q0] (q1) {$q_1$};
		\node [state, right of = q1] (q2) {$q_2$};
		\node [state, right of = q2, accepting] (q3) {$q_3$};
		\draw (q0) edge[above] node{$\epsilon$,0,1} (q1)
			(q1) edge[above] node{$\epsilon$,0,1} (q2)
			(q2) edge[above] node{0} (q3)
			(q3) edge[loop above] node{0,1} ();
	\end{tikzpicture}
\end{document}

例 2

长度至少为 1，后三个符号里至少有一个不是 2 的 0、1 和 2 组成的串

---

\usetikzlibrary{automata, positioning, arrows}
\tikzset{
	->, % makes the edges directed
	>=stealth, % makes the arrow heads bold
	node distance=2.5cm, % specifies the minimum distance between two nodes. Change if necessary.
	every state/.style={thick}, % sets the properties for each ’state’ node
	initial text=$Start$, % sets the text that appears on the start arrow
}
\begin{document}
	\begin{tikzpicture}
		\node [state, initial] (q0) {$q_0$};
		\node [state, right of = q0] (q1) {$q_1$};
		\node [state, right of = q1] (q2) {$q_2$};
		\node [state, right of = q2, accepting] (q3) {$q_3$};
		\draw (q0) edge[loop above, above] node{0,1,2} ()
			(q0) edge[above] node{0,1} (q1)
			(q1) edge[above] node{$\epsilon$,0,1,2} (q2)
			(q2) edge[above] node{$\epsilon$,0,1,2} (q3);
	\end{tikzpicture}
\end{document}

即后三个符号中至少有一个是 0 或 1

例 3

长度至少为 2 且第 2 到第 4 个符号中至少有一个不是 2 的 0、1、2 组成的串

---

\usetikzlibrary{automata, positioning, arrows}
\tikzset{
	->, % makes the edges directed
	>=stealth, % makes the arrow heads bold
	node distance=2.5cm, % specifies the minimum distance between two nodes. Change if necessary.
	every state/.style={thick}, % sets the properties for each ’state’ node
	initial text=$Start$, % sets the text that appears on the start arrow
}
\begin{document}
	\begin{tikzpicture}
		\node [state, initial] (q0) {$q_0$};
		\node [state, right of = q0] (q1) {$q_1$};
		\node [state, right of = q1] (q2) {$q_2$};
		\node [state, right of = q2] (q3) {$q_3$};
		\node [state, right of = q3, accepting] (q4) {$q_4$};
		\draw (q0) edge[above] node{0,1,2} (q1)
			(q1) edge[above] node{$\epsilon$,0,1,2} (q2)
			(q2) edge[above] node{$\epsilon$,0,1,2} (q3)
			(q3) edge[above] node{0} (q4)
			(q4) edge[loop above, above] node{0,1,2} (q4);
	\end{tikzpicture}
\end{document}

例 4

长度至少为 4 且前五位至少有一个子串 102，后五位至少有一个子串 021 的 0、1、2 组成的串

---

需考虑全部情况

• 102 出现在 021 前且没有重叠
• 102 出现在 021 前且重叠：1021
• 102 出现在 021 后且整个串长度为 5！02102

例 5

长度至少为 3 且每个连续的 3 位必为 012、120 或 201

---

容易漏掉长度至少为 3 的条件

DFA 和 $ϵ-NFA$ 的等价性

Theorem

$L$ 是一个 DFA 的语言 $\iff L$ 是一个 $ϵ-NFA$ 的语言

Proof

从 DFA 构造等价的 $ϵ-NFA$：容易构造 从 $ϵ-NFA$ 构造等价的 DFA（修改的子集构造法）： $E=(Q_E,\Sigma ,{\delta }_E,q_0,F_E)$ 定义 $D=(Q_D,\Sigma ,{\delta }_D,q_D,F_D)$

• $Q_D=\{S|S\subseteq Q_E\wedge S=ECLOSE(S)\}$
• $q_D=ECLOSE(q_0)$
• 若 $S=\{p_1,\dots ,p_k\},{\bigcup }_{i=1}^k{\delta }_E(p_i,a)=\{r_1,\dots ,r_m\}$ ，定义 ${\delta }_D(S,a)={\bigcup }_{j=1}^{m}ECLOSE(r_j)$
• $F_D=\{S|S\in Q_D\wedge S\cap F_E\ne \varnothing \}$

DFA 的最小化

设 DFA $D=(Q,\Sigma ,\delta ,q_0,F)$，定义 $Q$ 上的一个二元关系 $R$ 为

$$pRq\iff \forall p,q\in Q,w\in {\Sigma }^{\ast },{\delta }^{\prime }(p,w)\in F\iff {\delta }^{\prime }(q,w)\in F$$

可验证该关系为二元关系。 若 $\delta (r,a)=p,\delta (s,a)=q$ 则

• $p$ 和 $q$ 可区别 $\Rightarrow r$ 和 $s$ 可区别
• $r$ 和 $s$ 不可区别 $\Rightarrow p$ 和 $q$ 不可区别
• $r$ 和 $s$ 可由 $ax$ 区别 $\Rightarrow$ $p$ 和 $q$ 可由 $x$ 区别

计算状态集划分：填表法

递归标记可区别的状态偶对。

• 基础：若 $p$ 为终态，$q$ 为非终态，标记 $p$ 和 $q$ 可区别
• 归纳：若 $p$ 和 $q$ 可区别，$\delta (r,a)=p,\delta (s,a)=q$，则标记 $r$ 和 $s$ 可区别 通过合并等价状态优化 DFA：
• 删去所有从初始状态不可达的节点
• 使用填表算法
• 仅保留可区别的点，将所有不可区别的点合并

例 1