有穷自动机

有穷自动机（Finite Automaton, FA），也称为有限状态机（Finite State Machine, FSM），是计算理论中的一个基本概念，是一个根据输入的内容，再根据自身的转移规则来改变自身状态，进而确定是否识别该内容的模型。用于模拟和识别具有离散输入输出的系统。

确定性有穷自动机(DFA)

定义

确定性有穷自动机（Deterministic Finite Automaton, DFA）是一个5元组[math]\displaystyle{ (Q,\Sigma,\delta,q_0,F) }[/math]，其中

1. Q是一个有穷集合，称为状态集
2. [math]\displaystyle{ \Sigma }[/math]是一个有穷集合，称为字母表
3. [math]\displaystyle{ \delta：Q×\Sigma \rightarrow Q }[/math]是状态转移函数
4. [math]\displaystyle{ q_0\in Q }[/math]是起始状态
5. [math]\displaystyle{ F\subseteq Q }[/math]是接受状态集

一台确定性有穷自动机有如上五个部分组成，介绍如下：

1. 它有一个状态集，表示它有的全部状态
2. 它有一个输入字母表，指明所有允许的输入符号
3. 它有一个根据一个输入字符从一个状态到另一个状态的规则
4. 它有一个起始状态，表示处理所起始的状态
5. 它有一个接受状态集，表示处理表达为接受的状态

例子

[math]\displaystyle{ \begin{align} Q=\{q_0,q_1\}\\ \Sigma=\{0,1\}\\ \delta=\begin{Bmatrix} \delta(q_0,0)=q_1\\ \delta(q_0,1)=q_0\\ \delta(q_1,0)=q_1\\ \delta(q_1,1)=q_0 \end{Bmatrix}\\ F=\{q_1\} \end{align} }[/math]

用处

主要对于输入的字符串判定是否该确定性有穷自动机所识别的语言，对此表示接受及不接受。

而如上的确定性有穷自动机是识别以0结尾的串，对于以0结尾的串[math]\displaystyle{ x \in \Sigma^* }[/math]，表示接受，反之不接受。

确定性有穷自动机可以用来定义语言也可用于识别语言。

运算

假如现在有个确定性有穷自动机[math]\displaystyle{ \mathcal M_1=(Q,\Sigma,\delta,q_0,F) }[/math]

假如对于上面的确定性有穷自动机[math]\displaystyle{ \mathcal M_1 }[/math]，输入字符串[math]\displaystyle{ 010 }[/math]，此时从初始状态[math]\displaystyle{ q_0 }[/math]开始，读入第一个字符[math]\displaystyle{ 0 }[/math]，因为[math]\displaystyle{ \delta(q_0,0)=q_1 }[/math]，所以转移状态至[math]\displaystyle{ q_1 }[/math]，继续读入下一个字符[math]\displaystyle{ 1 }[/math]，因为[math]\displaystyle{ \delta(q_1,1)=q_0 }[/math]，所以转移状态至$q_0$，继续读入下一个字符[math]\displaystyle{ 0 }[/math]，因为[math]\displaystyle{ \delta(q_0,0)=1 }[/math]所以转移状态至[math]\displaystyle{ q_1 }[/math]，运算结束。因为最后停在状态[math]\displaystyle{ q_1 }[/math]，因为[math]\displaystyle{ q_1 \in F }[/math]，所以确定性有穷自动机[math]\displaystyle{ \mathcal M_1 }[/math]接受字符串[math]\displaystyle{ 010 }[/math]。

扩展转移函数

扩展[math]\displaystyle{ \delta }[/math]到字符串，定义扩展转移函数[math]\displaystyle{ \hat{\delta}:Q×\Sigma^* \rightarrow Q }[/math]为

[math]\displaystyle{ \hat{\delta}(q,w)=\begin{cases} q &w=\varepsilon \\ \delta(\hat{\delta}(q,x),a)&w=xa \end{cases} }[/math]

其中[math]\displaystyle{ q \in Q }[/math]，[math]\displaystyle{ a \in \Sigma }[/math]， [math]\displaystyle{ w,x \in \Sigma^* }[/math]

定理一

[math]\displaystyle{ \hat{\delta}(q,xy)=\hat{\delta}(\hat{\delta}(q,x),y) }[/math]

DFA的语言

若[math]\displaystyle{ M=(Q,\Sigma,\delta,q_0,F) }[/math]是一个确定性有穷自动机，则M接受的语言为

[math]\displaystyle{ \mathcal{L(M)}=\{w\in \Sigma^*|\hat{\delta}(q_0,w)\in F\} }[/math]

非确定性有穷自动机（NFA）

定义

非确定性有穷自动机（NonDeterministic Finite Automata, NFA）是一个5元组[math]\displaystyle{ (Q,\Sigma,\delta,q_0,F) }[/math]，其中

1. Q是一个有穷集合，称为状态集
2. [math]\displaystyle{ \Sigma }[/math]是一个有穷集合，称为字母表
3. [math]\displaystyle{ \delta：Q×\Sigma \rightarrow \mathcal P(Q) }[/math]是状态转移函数[math]\displaystyle{ (\mathcal P(Q)=\{S|S\subseteq Q\}) }[/math]
4. [math]\displaystyle{ q_0\in Q }[/math]是起始状态
5. [math]\displaystyle{ F\subseteq Q }[/math]是接受状态集

一台非确定性有穷自动机有如上五个部分组成，介绍如下：

1. 它有一个状态集，表示它有的全部状态
2. 它有一个输入字母表，指明所有允许的输入符号
3. 它有一个根据一个输入字符从一个状态到零个或多个状态的规则
4. 它有一个起始状态，表示处理所起始的状态
5. 它有一个接受状态集，表示处理表达为接受的状态性有穷自动机

例子

假如现在有个非确定性有穷自动机[math]\displaystyle{ \mathcal M_2=(Q,\Sigma,\delta,q_0,F) }[/math]

[math]\displaystyle{ \begin{align} Q=\{q_0,q_1,q_2\}\\ \Sigma=\{0,1\}\\ \delta=\begin{Bmatrix} \delta(q_0,0)=\{q_0,q_1\}\\ \delta(q_0,1)=\{q_0\}\\ \delta(q_1,0)=\varnothing\\ \delta(q_1,1)=\{q_2\}\\ \delta(q_2,0)=\varnothing\\ \delta(q_2,1)=\varnothing\\ \end{Bmatrix}\\ F=\{q_2\} \end{align} }[/math]

用处

主要对于输入的字符串判定是否该非确定性有穷自动机所识别的语言，对此表示接受及不接受

而如上的确定性有穷自动机是识别以[math]\displaystyle{ 01 }[/math]结尾的串，对于以[math]\displaystyle{ 01 }[/math]结尾的串[math]\displaystyle{ x \in \Sigma^* }[/math]，表示接受，反之不接受

非确定性有穷自动机可以用来定义语言也可用于识别语言

运算

假如对于上面的确定性有穷自动机[math]\displaystyle{ \mathcal M_2 }[/math]，输入字符串[math]\displaystyle{ 010 }[/math]，此时从初始状态[math]\displaystyle{ q_0 }[/math]开始，读入第一个字符[math]\displaystyle{ 0 }[/math]，因为[math]\displaystyle{ \delta(q_0,0)=\{q_0,q_1\} }[/math]，此时有[math]\displaystyle{ 2 }[/math]个转移方向：

1. 转移状态至[math]\displaystyle{ q_0 }[/math]，读入下一个字符1，因为[math]\displaystyle{ \delta(q_0,1)=\{q_0\} }[/math]，所以转移状态至[math]\displaystyle{ q_0 }[/math]，读入下一个字符0，因为[math]\displaystyle{ \delta(q_0,0)=\{q_0,q_1\} }[/math]，此时有[math]\displaystyle{ 2 }[/math]个转移方向：
   1. 转移状态至[math]\displaystyle{ q_0 }[/math]，因为[math]\displaystyle{ q_0 \notin F }[/math]，所以不接受
   2. 转移状态至[math]\displaystyle{ q_1 }[/math]，因为[math]\displaystyle{ q_1 \notin F }[/math]，所以不接受
2. 转移状态至[math]\displaystyle{ q_1 }[/math]，读入下一个字符1，因为[math]\displaystyle{ \delta(q_1,1)=\{q_2\} }[/math]，所以转移状态至[math]\displaystyle{ q_2 }[/math]，读入下一个字符0，因为[math]\displaystyle{ \delta(q_2,0)=\varnothing }[/math]，对于空集（就是没有规定这个状态对于这个输入的转移），我们认为此时等同于不接受

因为最后结果都是不接受，所以我们认为该非确定性有穷自动机不接受该串

如果有结果是接受，才认为该非确定性有穷自动机接受该串

扩展转移函数

扩展[math]\displaystyle{ \delta }[/math]到字符串，定义扩展转移函数[math]\displaystyle{ \hat{\delta}:Q×\Sigma^* \rightarrow \mathcal P(Q) }[/math]为

[math]\displaystyle{ \hat{\delta}(q,w)=\begin{cases} \{q\} &w=\varepsilon \\ \bigcup_{p \in \hat{\delta}(q,x)}\delta(p,a)&w=xa \end{cases} }[/math]

其中[math]\displaystyle{ q \in Q }[/math]，[math]\displaystyle{ a \in \Sigma }[/math]， [math]\displaystyle{ w,x \in \Sigma^* }[/math]

NFA的语言

若[math]\displaystyle{ \mathcal M=(Q,\Sigma,\delta,q_0,F) }[/math]是一个非确定性有穷自动机，则[math]\displaystyle{ \mathcal M }[/math]接受的语言为

[math]\displaystyle{ \mathcal {L(M)}=\{w\in \Sigma^*|\hat{\delta}(q_0,w)\cap F\not = \varnothing\} }[/math]

带空转移的非确定性有穷自动机

带空转移的非确定性有穷自动机（[math]\displaystyle{ \varepsilon }[/math]-NFA）是一个5元组[math]\displaystyle{ (Q,\Sigma,\delta,q_0,F) }[/math]，其中

1. Q是一个有穷集合，称为状态集
2. [math]\displaystyle{ \Sigma }[/math]是一个有穷集合，称为字母表
3. [math]\displaystyle{ \delta：Q×(\Sigma \cup \{\varepsilon\}) \rightarrow \mathcal P(Q) }[/math]是状态转移函数 [math]\displaystyle{ (\mathcal P(Q)=\{S|S\subseteq Q\}) }[/math]
4. [math]\displaystyle{ q_0\in Q }[/math]是起始状态
5. [math]\displaystyle{ F\subseteq Q }[/math]是接受状态集

一台非确定性有穷自动机有如上五个部分组成，介绍如下：

1. 它有一个状态集，表示它有的全部状态
2. 它有一个输入字母表，指明所有允许的输入符号
3. 它有一个根据零个或一个输入字符从一个状态到零个或多个状态的规则
4. 它有一个起始状态，表示处理所起始的状态
5. 它有一个接受状态集，表示处理表达为接受的状态

状态的[math]\displaystyle{ \varepsilon }[/math]-闭包

状态[math]\displaystyle{ q }[/math]的[math]\displaystyle{ \varepsilon }[/math]-闭包([math]\displaystyle{ \varepsilon }[/math]-[math]\displaystyle{ \mathcal {Closure} }[/math])，记为[math]\displaystyle{ E_{CLOSE}(q) }[/math]，表示从[math]\displaystyle{ q }[/math]经过[math]\displaystyle{ \varepsilon \varepsilon \cdots \varepsilon }[/math]序列可达的全部状态集合，定义为

[math]\displaystyle{ \begin{cases} q \in E_{CLOSE}(q)\\ \forall p \in E_{CLOSE}(q),r \in \delta(p,\varepsilon) \rightarrow r \in E_{CLOSE}(q) \end{cases} }[/math]

状态集[math]\displaystyle{ Q }[/math]的[math]\displaystyle{ \varepsilon }[/math]-闭包为

[math]\displaystyle{ E_{CLOSE}(Q)=\bigcup_{q\in Q}E_{CLOSE}(q) }[/math]

用处

与NFA相同

运算

遇到[math]\displaystyle{ \varepsilon }[/math]时，就不消耗输入的字符就进行状态转移，其他与NFA相同

扩展转移函数

扩展[math]\displaystyle{ \delta }[/math]到字符串，定义扩展转移函数[math]\displaystyle{ \hat{\delta}:Q×\Sigma^* \rightarrow 2^Q }[/math]为

[math]\displaystyle{ \hat{\delta}(q,w)=\begin{cases} E_{CLOSE}(q) &w=\varepsilon \\ E_{CLOSE}(\bigcup_{p \in \hat{\delta}(q,x)}\delta(p,a))&w=xa \end{cases} }[/math]

其中[math]\displaystyle{ q \in Q }[/math]，[math]\displaystyle{ a \in \Sigma }[/math]，[math]\displaystyle{ w,x \in \Sigma^* }[/math]

[math]\displaystyle{ \varepsilon }[/math]-NFA的语言

若[math]\displaystyle{ \mathcal M=(Q,\Sigma,\delta,q_0,F) }[/math]是一个带空转移的非确定性有穷自动机，则[math]\displaystyle{ \mathcal M }[/math]接受的语言为

定理二

如果语言[math]\displaystyle{ \mathcal L }[/math]被[math]\displaystyle{ \varepsilon }[/math]-NFA接受，当且仅当[math]\displaystyle{ \mathcal L }[/math]被DFA接受。