有穷自动机（finite automation，FA），也叫做有限状态自动机，是一种在计算机学领域非常重要的计算模型。

1.有穷自动机

我们先看一个有穷自动机 M：

接下来，我们可以用形式化的方式来描述这个FA：M=(Q, Σ, δ, q0, F)

其中：

  • Q = {q1, q2, q3}

  • Σ = {0, 1}

  • δ 描述为

  • q1 是起始状态

  • F = {q2}

根据以上规则，我们已经可以定义一个 FA 了。其中：

  1. Q 表示的是该状态机所有的状态，即该 FA 所有的存在的状态都包含在此集合中

  2. Σ 表示的是所有的输入状态的集合，即所有可能的输入都包含在之中

  3. δ 描述的函数关系式，即从某一个状态转移到另一个状态时所遵循的规则

  4. q1 是起始状态，即该 FA 最开始的时候的状态

  5. F 是接受状态，或者也称为最终状态，无论一个状态机经过了怎样的变换，最后的一部转移必须转移到接受状态，否则就是非法的。符合这种转移要求的语言是可以被此台 FA 识别的，被称为正则语言。

2.确定型有穷自动机与非确定型有穷自动机

确定型有穷自动机（DFA）：每个状态对于字母表中的每一个符号总是恰好有一个转移箭头射出

非确定型有穷自动机（NFA）：一个状态对于字母表中的每一个符号可能有 0 个、1 个或多个箭头，NFA 中还可以存在有带有标号 ε 的箭头

  • 每一台 NFA 都可以转换成一台等价的 DFA，而构造 NFA 有时比直接构造 DFA 容易

  • 如果两台机器识别同样的语言，则称他们是等价的；每一台非确定型有穷自动机都等价于某一台确定型有穷自动机

参考文献：计算理论导引 机械工业出版社 2006-7