查看“︁用户:LynChern/Sandbox”︁的源代码

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

==定义==

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

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

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

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

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

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

==描绘==

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

==语言识别==

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

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

==计算能力==

FSA拥有较小但不容忽视的计算能力——如上所述，足以识别正则表达式。例如，它可以相加两个无界范围的整数。

许多更强大的计算模型在施加微小限制后，结果在计算上等价于FSA。例如，一个只能向右移动的[[Turing machine|图灵机]]在计算上等价于FSA。

许多[[esoteric programming language|深奥编程语言]]属于与FSA相同的[[computational class|计算类别]]。

==历史==

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

以下引用来自Rabin和Scott[1959, "有限自动机及其决策问题," IBM Journal of Research and Development 3,2 (April, 1959), 114]：

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

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

[[Category: Computational models|计算模型]]