现实中，计算机通常都有大量的易失存储器（RAM）和非多核易失存储器（硬盘或者SSD） ，有许多输入输出设备，还有能同时执行多个指令的处理器。有限状态机（finite state machine） ，也叫有限自动机（finite automaton） ，是一台计算机的极简模型，为了容易理解、推导并且容易用硬件或软件实现，它放弃了上面所有的这些特性。

状态、规则和输入

下面是一台有限自动机的结构图：

两个圆代表自动机的两个状态 1 和 2。凭空出现的箭头表明这台自动机从状态 1 开始，1 是它的起始状态。两个状态之间的箭头代表机器的规则：

  • 处于状态 1 并且读入字符 a 时，切换到状态 2；
  • 处于状态 2 并且读入字符 a 时，切换到状态 1。

这让我们有足够的信息研究机器如何处理一个输入流。

  • 这台机器从状态 1 开始。
  • 这台机器只有从输入流读入字符a 的规则，因此这是唯一能发生的事情。读取到 a 的时候，它会从状态 1 切换到状态 2。
  • 当这台机器又读取到了一个 a 时，它会切换回状态 1。

一旦回到状态 1，它又将开始重复自身，这就是这台机器的行为范围。我们可以认为当前状态的信息存在于机器内部, 它像一个“黑盒”一样运转，并不会展现其内部工作状况——这台无聊的机器毫无用处，没有任何能观察到的输出。即使这台机器一直在状态 1 和状态 2 之间切换，机器之外也没有一个人能看出来有什么事情在发生。因此在这种情况下，我们可能还要增加一个状态，这样就不用再为任何内部结构操心了。

备注：每台有限自动机没有通用的 CPU 执行任意程序，而是硬编码了一些规则集合，以决定在相应的输入下如何从一个状态切换到另一个状态。自动机先从一个特定的状态开始，然后从输入流中读入字符——按照规则它每次读取一个字符，有限自动机没有键盘、鼠标和接收输入的网络接口，只有一个外部的字符输入流可以一次读取一个字符。

输出

只是把一些状态标记成特别状态，并且认为机器的单比特输出提供了当前是否处于特别状态的信息。对于这台机器，我们将状态 2 作为特别状态，并在图中用双重的圆形表示它。

这些特定状态通常称为接受状态，表明这台机器对某个输入序列是接受还是拒绝。如果这台自动机从状态 1 开始并读入一个 a，它将会停留在状态 2，这是一个接受状态，因此我们可以说这台机器接受字符串 ‘a’。另外，如果它先读到一个 a，然后又读取了另一个 a，它将终止于状态 1，这不是一个接受状态，所以这台机器拒绝字符串 ‘aa’。事实上很容易看到，这台机器接受任何奇数个数的 a 组成的字符串：’a’、’aaa’、’aaaaa’ 都能被接受，但是 ‘aa’、’aaaa’ 和 ‘’（空字符串）会被拒绝。

确定性

很明显，这种自动机具有确定性：不管它当前处于什么状态，并且不管读入什么字符，最终所处的状态总是完全确定的。只要满足下面两个约束，就能保证这种确定性。

  • 没有冲突
    不存在这样的状态： 它的下一次转换状态因为有彼此冲突的规则而有二义性。
    （这意味着一个状态对于同样的输入，不能有多个规则。 ）

  • 没有遗漏　
    不存在这样的状态：它的下一次转换状态因为缺失规则而未知。 （这意味着每个状态都必须针对每个可能的输入字符有至少一个规则。 ）

总结

综上，如果遵循上述约定，这就是一台确定性有限自动机（DFA）。