确定有限状态自动机

在计算理论中，确定有限状态自动机或确定有限自动机（英语：deterministic finite automaton, DFA）是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表${\displaystyle \mathrm{\Sigma <!--\; \Sigma \; -->}}$的字符，它都能根据事先给定的转移函数转移到下一个状态（这个状态可以是先前那个状态）。

确定有限状态自动机${\displaystyle \mathcal{A}}$是由

所组成的5-元组。因此一个DFA可以写成这样的形式：${\displaystyle \mathcal{A}=\left(Q,\mathrm{\Sigma <!--\; \Sigma \; -->},\mathrm{\delta <!--\; \delta \; -->},s,F\right)}$。

确定有限状态自动机从起始状态开始，一个字符接一个字符地读入一个字符串${\displaystyle w\in <!--\; \in \; -->{\mathrm{\Sigma <!--\; \Sigma \; -->}}^{\ast <!--\; \ast \; -->}}$（这里的${\displaystyle {}^{\ast <!--\; \ast \; -->}}$指示Kleene星号算子。），并根据给定的转移函数一步一步地转移至下一个状态。在读完该字符串后，如果该自动机停在一个属于F的接受状态，那么它就接受该字符串，反之则拒绝该字符串。

为了在保证严谨的前提下，方便地叙述关于DFA的内容，我们定义如下扩展的转移函数：

对于一个确定有限状态自动机${\displaystyle \mathcal{A}=\left(Q,\mathrm{\Sigma <!--\; \Sigma \; -->},\mathrm{\delta <!--\; \delta \; -->},s,F\right)}$，如果${\displaystyle {\mathrm{\delta <!--\; \delta \; -->}}^{\ast <!--\; \ast \; -->}\left(s,w\right)\in <!--\; \in \; -->F}$，我们就说该自动机接受字符串w，反之则表明该自动机拒绝字符串w。

被一个确定有限自动机接受的语言（或者叫“被识别的语言”）定义为：${\displaystyle \mathcal{L}(\mathcal{A})=\{w\in <!--\; \in \; -->{\mathrm{\Sigma <!--\; \Sigma \; -->}}^{\ast <!--\; \ast \; -->}|\mathcal{A}}$接受字符串${\displaystyle w\}}$，也就是由所有被接受的字符串组成的集合。

除了数学上的严谨表述，通常为了讨论方便，也使用状态图直观地表示DFA。不难发现，对于一个给定的DFA，存在唯一一个对应的有向图（但是严格意义上一个有向图不能确定出唯一一个DFA）。有向图的每个结点对应一个状态，每条有向边对应一种转移。习惯上将结点画成两个圈表示接受状态，一个圈表示拒绝状态。用一条没有起点的边指向起始状态。

除了在表述上方便以外，在研究某些问题（如“给定的DFA的语言是否为无穷集合”）时，状态图也提供了有效的解法。

DFA是一种实际的计算模型，因为有平凡的线性时间、恒定空间的在线算法模拟在输入流上的DFA。给定两个DFA有有效算法找到识别它们所识别语言的并集、交集和补集的DFA。还有有效算法确定一个DFA是否接受任何给定字符串，一个DFA是否接受所有字符串，两个DFA是否识别同样的语言，和对特定正则语言找到状态数目最小的DFA（最小DFA）。

在另一方面，DFA在可识别的语言上有严格的限制—很多简单的语言，包括需要多于恒定空间来解决的任何问题，不能被DFA识别。经典的DFA不能识别的简单语言的例子是括号语言，就是由正确配对的括号组成的语言，比如 (()())。由形如anbn的字符串组成的语言，就是有限数目个a，随后是相等数目个b。可以证明没有DFA有足够状态来识别这种语言（通俗地说，因为需要至少2n个状态，而n是不恒定的）。

下面是一个确定有限状态自动机的例子。

确定有限状态自动机${\displaystyle \mathcal{A}=\left(Q,\mathrm{\Sigma <!--\; \Sigma \; -->},\mathrm{\delta <!--\; \delta \; -->},s,F\right)}$

状态${\displaystyle S_1}$表示在输入的字符串中有偶数个0，而${\displaystyle S_2}$表示有奇数个0。在输入中1不改变自动机的状态。当读完输入的字符串的时候，状态将显示输入的字符串是否包含偶数个0。

${\displaystyle \mathcal{A}}$能识别的语言是${\displaystyle \mathcal{L}(\mathcal{A})=\{w|{\mathrm{\#<!--\; \#\; -->}}_0(w)\equiv <!--\; \equiv \; -->0(mod2)\}}$。用正则表达式表示为：${\displaystyle (1^{\ast <!--\; \ast \; -->}({01}^{\ast <!--\; \ast \; -->}0{)}^{\ast <!--\; \ast \; -->}{)}^{\ast <!--\; \ast \; -->}}$。

确定有限状态自动机的交，并，差，补，连接，替换，同态，逆同态等运算是封闭的，也就是说确定有限状态自动机通过这些运算产生的新的自动机也是确定有限状态自动机。

${\displaystyle \mathcal{A}=(Q,\mathrm{\Sigma <!--\; \Sigma \; -->},\mathrm{\delta <!--\; \delta \; -->},s,F)}$是一个DFA，那么由补运算产生的新DFA定义为：${\displaystyle \stackrel{¯<!--\; ¯\; -->}{\mathcal{A}}=(Q,\mathrm{\Sigma <!--\; \Sigma \; -->},\mathrm{\delta <!--\; \delta \; -->},s,Q-<!--\; -\; -->F)}$。显然只要将${\displaystyle \mathcal{A}}$中接受的状态设为不接受的状态，同时把不接受的状态设为接受的状态就得到${\displaystyle \stackrel{¯<!--\; ¯\; -->}{\mathcal{A}}}$。补运算的复杂度是：${\displaystyle O(\left|Q\right|)}$。

有两个DFA，${\displaystyle {\mathcal{A}}_1=(Q_1,\mathrm{\Sigma <!--\; \Sigma \; -->},{\mathrm{\delta <!--\; \delta \; -->}}_1,s_1,F_1)}$和${\displaystyle {\mathcal{A}}_2=(Q_2,\mathrm{\Sigma <!--\; \Sigma \; -->},{\mathrm{\delta <!--\; \delta \; -->}}_2,s_2,F_2)}$，那么由这两个DFA创造出来的新的自动机定义为：${\displaystyle \mathcal{B}=(Q_1\times <!--\; \times \; -->Q_2,\mathrm{\Sigma <!--\; \Sigma \; -->},{\mathrm{\delta <!--\; \delta \; -->}}_{\mathcal{B}},(s_1,s_2),M)}$。其中${\displaystyle M\subseteq <!--\; \subseteq \; -->Q_1\times <!--\; \times \; -->Q_2}$，${\displaystyle \left(s_1,s_2\right)}$为${\displaystyle \mathcal{B}}$的开始状态，${\displaystyle {\mathrm{\delta <!--\; \delta \; -->}}_{\mathcal{B}}}$为${\displaystyle \mathcal{B}}$的转移函数，且作如下定义：${\displaystyle \mathrm{\forall <!--\; \forall \; -->}{q}_1\in <!--\; \in \; -->Q_1,q_2\in <!--\; \in \; -->Q_2,\mathrm{\sigma <!--\; \sigma \; -->}\in <!--\; \in \; -->\mathrm{\Sigma <!--\; \Sigma \; -->}:{\mathrm{\delta <!--\; \delta \; -->}}_{\mathcal{B}}((q_1,q_2),\mathrm{\sigma <!--\; \sigma \; -->})=({\mathrm{\delta <!--\; \delta \; -->}}_1(q_1,\mathrm{\sigma <!--\; \sigma \; -->}),{\mathrm{\delta <!--\; \delta \; -->}}_2(q_2,\mathrm{\sigma <!--\; \sigma \; -->}))}$。

交运算和并运算的复杂度都是${\displaystyle O(\left|Q_1\right|\left|Q_2\right|\left|\mathrm{\Sigma <!--\; \Sigma \; -->}\right|)}$。

一个同态函数${\displaystyle h:{\mathrm{\Sigma <!--\; \Sigma \; -->}}^{\ast <!--\; \ast \; -->}\to <!--\; \to \; -->{\mathrm{\Gamma <!--\; \Gamma \; -->}}^{\ast <!--\; \ast \; -->}}$可以递归的定义为：

于是则有${\displaystyle h(uv)=h(u)h(v)}$。（以上所述中${\displaystyle \mathrm{ϵ<!--\; ϵ\; -->}}$为空字符，${\displaystyle u,v\in <!--\; \in \; -->{\mathrm{\Sigma <!--\; \Sigma \; -->}}^{\ast <!--\; \ast \; -->},\mathrm{\sigma <!--\; \sigma \; -->}\in <!--\; \in \; -->\mathrm{\Sigma <!--\; \Sigma \; -->}}$）

此外替换运算和逆同态运算的方法近似。

对于一个正则语言，接受该语言的等价类自动机是一个${\displaystyle (Q,\mathrm{\Sigma <!--\; \Sigma \; -->},\mathrm{\delta <!--\; \delta \; -->},s,F)}$的5-元组。其定义如下：

~_L被称为Nerode关系，是Myhill-Nerode定理的基础。简单的来说就是对于任意${\displaystyle x,y,z\in <!--\; \in \; -->{\mathrm{\Sigma <!--\; \Sigma \; -->}}^{\ast <!--\; \ast \; -->}}$，如果${\displaystyle xz\in <!--\; \in \; -->L\iff <!--\; \iff \; -->yz\in <!--\; \in \; -->L}$，那么x~_Ly。

对于任意给定的确定有限状态自动机都能找到一个与之计算能力等价的最小确定有限状态自动机，简称最小自动机。该最小自动机中状态的数量等于能识别相同语言的等价类自动机中等价关系的数量，我们可以称最小自动机和等价类自动机“实际上”是相等的，也就是同构。非正式的说法是：对于最小自动机上的任意状态都可以通过一个同构函数变换成等价类自动机上的一个状态。

能识别一个正则语言的等价类自动机是唯一的，因此能识别该语言的最小自动机也是唯一的。

定义一个非等价关系：${\displaystyle N:=\{(p,q)|p,q\in <!--\; \in \; -->Q,\mathrm{\exists <!--\; \exists \; -->}w\in <!--\; \in \; -->{\mathrm{\Sigma <!--\; \Sigma \; -->}}^{\ast <!--\; \ast \; -->}:{\mathrm{\delta <!--\; \delta \; -->}}^{\ast <!--\; \ast \; -->}(p,w)\in <!--\; \in \; -->F\leftrightarrow <!--\; \leftrightarrow \; -->{\mathrm{\delta <!--\; \delta \; -->}}^{\ast <!--\; \ast \; -->}(q,w)\notin <!--\; \notin \; -->F\}}$，如下步骤可以得到这个集合N：

以下是由一个任意DFA转换到一个最小DFA的步骤：

这样就得到了接受相同语言的最小自动机。复杂度为${\displaystyle O({\left|Q\right|}^2\left|\mathrm{\Sigma <!--\; \Sigma \; -->}\right|)}$。