确定性有限自动机

形式陈述 ​

在有限状态自动机公理库有限状态自动机Finite-state automaton · Finite automaton · Finite-state machine以有限状态压缩输入前缀信息、沿带标号转移读取有限字的通用自动机骨架。的共同骨架上，确定性有限自动机（DFA）把转移限定为总函数。它是五元组

$$M=(Q,\mathrm{\Sigma },\delta ,q_0,F),$$

其中 $Q$ 是有限状态集，$\mathrm{\Sigma }$ 是输入字母表，$\delta :Q\times \mathrm{\Sigma }\to Q$ 是总转移函数公理库函数Function · Map · Mapping由定义域、陪域和单值图共同组成，并把每个输入送到唯一输出的映射。，$q_0\in Q$ 是初态，$F\subseteq Q$ 是接受状态集。扩展转移递归定义为

$${\delta }^{\ast }(q,\epsilon )=q,{\delta }^{\ast }(q,wa)=\delta ({\delta }^{\ast }(q,w),a).$$

自动机识别的语言公理库形式语言Formal language · Language over an alphabet字母表上有限字符串集合的抽象，是自动机输入与计算问题编码的基本对象。为 $L(M)=\{w\in {\mathrm{\Sigma }}^{\ast }:{\delta }^{\ast }(q_0,w)\in F\}$。由于 $\delta$ 对每个状态—字符对都恰给出一个后继，每个输入字只有一条运行。若允许零个或多个后继，就进入 NFA 的关系式语义，不能继续沿用本页的单状态递推。

直觉 ​

DFA 从左到右只读输入一次，过去的全部信息被压缩进当前有限状态。状态不是“刚读到哪个字符”，而是未来判断仍需知道的历史摘要；对奇偶语言，摘要只需一个比特。有限状态意味着记忆容量不随输入增长，因此它能记模计数、有限后缀和有限协议阶段，却不能精确保存任意大的计数。转移函数是确定且总的，每读一个符号都恰有一个下一状态。

例子与边界 ​

识别二进制串中 1 个数为偶数的 DFA 只需状态 $q_e,q_o$。读 0 保持状态，读 1 在二者间切换，初态和唯一接受态为 $q_e$。输入 1011 依次经历 $q_e,q_o,q_o,q_e,q_o$，故拒绝。

边界语言 $\{0^n{1}^n:n\ge 0\}$ 要求记住任意多个前导 0 的精确数量，再与 1 比较；任何固定有限状态集最终都会混淆两个不同计数。自动机状态数可以很大，但只要与输入长度无关，仍无法提供无界记忆。

推论与应用 ​

DFA 恰好识别正则语言公理库正则语言Regular language能被某个有限自动机识别的形式语言。，并与 NFA、正则表达式公理库正则表达式Regular expression由空语言、空串、字符、并、连接和 Kleene 星有限构造的语言表达式。在表达能力上等价。自动机最小化公理库有限自动机最小化Finite automaton minimization合并不可区分状态以得到识别同一语言且状态数最少的 DFA。把状态压缩为不同未来行为的等价类。

词法分析、网络协议监控、硬件控制器和字符串扫描广泛使用有限状态机；状态积构造还可组合多个监视条件。运行时验证公理库运行时验证Runtime verification · Runtime monitoring · Trace monitoring在单次有限执行上消费事件，以有限状态、符号或参数化监控器给出违反、满足或尚不可判定的前缀结论。可以让有限自动机消费已观测事件并报告有限前缀是否匹配。

若对象是无限运行，则需Büchi 自动机公理库Büchi 自动机Büchi automaton · Nondeterministic Büchi automaton · NBA在无限字上运行，并以接受状态被无限多次访问作为接受条件的有限状态自动机。等 $\omega$-自动机，用“无限次访问接受状态”取代读完整个有限字后的终态接受；有限字 DFA 的定义与判定不能原样承担这一任务。

参考资料

• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Chapter 1.
• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Chapter 2.