用户:LynChern/Sandbox

有限状态自动机，简称 FSA，是一种简单的假想机器。它有时也被称为有限状态机、有限自动机或有限状态转换器。

定义

（注意：FSA 用于各种目的——识别形式语言、建模系统的动态行为、表示视频游戏中的实体等——这些应用通常使用适合其问题域的略微不同的定义。我们将尝试在本页面上使用非常通用的定义，然后描述常见的变体。）

在任何给定时间，FSA 可以处于有限数量的状态中的任何一种。它从外部源一个接一个地接收输入信号。当每个信号被接收时，FSA 根据输入信号和 FSA 的当前状态转换到另一个（可能相同的）状态。当没有更多输入信号需要处理时，可以认为 FSA 处于一个最终状态。

FSA 也可以被认为会产生输出信号，这些信号指向某个外部接收器。它可能在特定转换发生时（如在 Mealy 机中）或达到特定状态时（如在 Moore 机中）产生这些信号。（这两种情况是等价的，除了所需的状态数量。）输出信号可能与输入信号性质相同或不同。

FSA 可以被认为能够在每次转换或状态时产生多个输出信号。或者，某些转换可能根本不依赖于输入信号，自动移动到新状态。（这两种情况也是等价的，除了所需的状态数量。）

所有状态对所有可能的输入信号都有转换。如果输入信号被认为是“非法的”，它不能被拒绝——FSA 仍然必须转换到某个状态。这通常通过拥有一个非接受状态来处理，所有状态在接收到“非法”输入信号时都转换到该状态，并且 FSA 永远无法“逃脱”该状态。这个状态通常从图中省略，只是隐含的。

FSA 的行为可以是确定性的或非确定性的；一个非确定性的 FSA 可以同时处于多个状态；如果存在某种选择路径导致接受状态，它就接受输入。对于识别器，有一种算法可以消除非确定性，但通常会大大增加状态数量（最多 2ⁿ，其中 n 是非确定性自动机中的状态数）。

描述

FSA 可以描述为转换表，或者更直观地，描述为有向图，其中顶点是状态，边是从状态到状态的转换。边用转换发生的输入信号标注。输出信号可以标注在边上、顶点上，或两者上。

语言识别

为了识别一个字符串是否属于形式语言（如正则表达式）的一部分，信号是字符串的符号，最终状态决定 FSA 是否“接受”该字符串——即，与 FSA 关联的形式语言是否包含该字符串。这种 FSA 通常不产生输出，而只是以“接受”或“拒绝”状态结束，被称为接受器或识别器。

FSA 足够强大以识别某些字符串集合，但不能识别其他。例如，可以构造一个 FSA，它可以告诉你一个字符串是否以开括号开头并以闭括号结尾，无论该字符串有多长。然而，没有 FSA 可以告诉你这些括号是否正确嵌套（正则表达式也不能）——为此，你需要一个下推自动机。

计算能力

FSA 具有较小但并非微不足道的计算能力——如上所述，它足以识别正则表达式。例如，它可以相加两个无界整数。

许多更强大的计算模型在施加了简单限制后，被证明在计算上等同于 FSA。例如，只能向右移动的图灵机在计算上等同于 FSA。

许多深奥编程语言属于与 FSA 相同的计算类别。

历史

可以在有限数量的内部状态之间转换的系统早已为人所知，但直到计算机科学早期历史相对较晚时才被正式研究。

以下引文来自 Rabin 和 Scott[1959, “Finite automata and their decision problems,” IBM Journal of Research and Development 3,2 (April, 1959), 114]：

：“图灵机被广泛认为是数字计算机的抽象原型；然而，该领域的工作者越来越感到图灵机的概念过于笼统，无法作为实际计算机的准确模型。众所周知，即使是简单计算，也无法为图灵机在任何给定计算中所需的磁带量给出先验上界。正是这一特性使得图灵的概念不切实际。”

：“在过去几年中，有限自动机的概念出现在文献中。这些机器只有有限数量的内部状态，可用于内存和计算。有限性的限制似乎能更好地近似物理机器的概念。当然，这样的机器不能像图灵机那样做那么多事情，但能够计算任意一般递归函数的优势是值得怀疑的，因为在实际应用中很少出现这些函数。”