用户:LynChern/Sandbox：修订间差异

2026年4月12日 (日) 00:42的版本

一个有限状态自动机，缩写为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, "有限自动机及其决策问题," IBM Journal of Research and Development 3,2 (April, 1959), 114]：

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

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

@@ 第1行： / 第1行： @@
-:''本文是关于计算机科学概念的，关于深奥虚拟机，请见[[UM-32]]。''
+一个'''有限状态自动机'''，缩写为FSA，是一种简单的假想机器形式。它有时也被称为''有限状态机''、''有限自动机''或''有限状态转换器''。
-'''通用机'''是模拟其类别中其他机器的程序。最常见的通用机是通用[[Turing machine|图灵机]]，它们是模拟[[Turing-complete|图灵完备]]系统行为的图灵机程序。
-通用机包含以下部分：
+==定义==
-* 机器；指一种语言（例如 [[Brainfuck]]、Python、[[lambda calculus|λ演算]]）、机器（图灵机、[[Minsky machine|明斯基机]]）或其他计算模型。
-* 程序描述；一个固定的、有限的描述，由机器执行的若干符号或状态组成。
-* 一些输入程序描述；由固定程序对其进行求值。通用机可以通过保持机器和固定程序描述不变，使用任意的输入程序重新运行。
-传统上，通用图灵机会在其纸带上获得输入程序描述，机器启动时其纸带以某种方式预先初始化了给定程序。通过某些输入指令“交互式”接受输入的通用机也是可以接受的。因此，通用机可以在缺乏I/O的语言中实现，前提是存在一种约定的方式，在机器运行之前可以初始化存储机制。
+（注意：FSA被用于各种目的——识别形式语言、建模系统的动态行为、在视频游戏中表示实体等——这些应用通常使用适合其问题域的略微不同的定义。我们将尝试在本页使用一个非常通用的定义，然后描述常见的变体。）
-通用机对其实现语言的[[:Category:Computational class|计算类别]]有影响。在大多数情况下，如果在给定语言中编写了一个图灵完备的通用机，那么该语言本身也是图灵完备的。然而，这并不绝对正确。有可能创建一种语言，其中唯一有效的程序就是通用机。如果情况如此，该机器或语言被认为是[[ℒ|ℒ完备]]的。这样的系统是否图灵完备存在争议。一方面，是的，该系统可以模拟一个图灵完备的系统。另一方面，只有在被模拟机器的程序作为描述提供给该机器时才能这样做，没有办法将给定的机器翻译成底层机器的程序描述，只能将其翻译成被模拟机器的描述。
+在任何给定时间，FSA可以处于有限数量的''状态''中的任何一个。它从一个外部源逐个接收''输入信号''。当每个信号被接收时，FSA根据输入信号和FSA的当前状态''转换''到另一个（可能是相同的）状态。当没有更多的输入信号需要处理时，FSA可以被认为是留在一个''最终状态''。
-== 弱通用机 ==
+FSA也可能被认为产生''输出信号''，这些信号指向某个外部接收器。它可能在特定转换发生时（如在Mealy机中）或当达到特定状态时（如在Moore机中）产生这些信号。（这两种情况是等价的，除了所需的状态数量。）输出信号可能与输入信号性质相同或不同。
-某些通用机需要特定的初始条件或其系统的推广才能具有通用性。其中一个例子是Wolfram提出的(2, 3)通用图灵机。该机器通过模拟[[cyclic tag|循环标签]]实现通用性，但现有证明依赖于状态的无限非周期初始配置。图灵机的正式定义要求字母表中存在一个空白符号，所有单元格都初始化为该符号，这意味着在经过任何有限步之后，纸带上永远只有1个符号具有无限出现次数（即空白符号）。需要等效于图灵机纸带被初始化为多个不同空白符号（从而有多个符号具有无限出现次数）的条件的通用机违反了这一要求，因为图灵机永远无法将其纸带配置成那样（但或许能使其等效）。
+FSA可以被认为能够在每次转换或状态中产生多个输出信号。或者，一些转换可能根本不依赖于输入信号，自动移动到新状态。（这两种情况也是等价的，除了所需的状态数量。）
-需要这种空白配置的通用机可称为''弱通用机''。只有弱通用机是可能的系统可被视为''弱图灵完备''。
+所有状态对于所有可能的输入信号都有一个转换。如果一个输入信号被认为是“非法的”，它不能被拒绝——FSA仍然必须转换到某个状态。这通常通过一个''非接受状态''来处理，该状态通过“非法”输入信号从所有状态转换到，并且FSA永远无法“逃脱”该状态。这个状态通常在图中被省略，只是隐含的。
-图灵机纸带的某些初始配置是[[:Category:Uncomputable|不可计算]]的。考虑一个纸带，其中每个向右的单元格编号（距离0的距离）对应于图灵完备语言中程序描述的编码，单元格根据程序是否停机被初始化为0或1。这台机器可以解决图灵机停机问题，因此是不可计算的。
+FSA的行为可以是确定性的或非确定性的；一个非确定性FSA可以同时处于多个状态；如果存在''某些''选择路径导致接受状态，它就接受一个输入。对于识别器，有一个算法可以移除非确定性，但通常会大大增加状态数量（最多2<sup>''n''</sup>，其中''n''是非确定性自动机中的状态数）。
-然而，并非所有初始配置都是不可计算的。只有一个符号的配置当然是可计算的，因为这等同于图灵机正式定义中的空白符号。一维棋盘格图案（...ABAB...）也是可计算的，其行为可以被一台具有空白符号Z且程序具有偶数和奇数分支的图灵机模拟。当遇到Z时，偶数分支将Z替换为A并切换到奇数分支，而奇数分支将Z替换为B并切换到偶数分支。请注意，虽然此机器的行为等效于用棋盘格初始化的机器，但纸带永远不会相同（因为总是有无穷多个Z和有限的A、B）。此通用过程适用于任何周期性图案。
+==描绘==
-虽然不可计算的图案是非周期性的，但非周期性图案不一定不可计算。考虑图案010010001...，其中每个连续的1前面有递增数量的零。这个图案是非周期性的，但一台拥有它的图灵机可以被一台具有空白纸带的图灵机模拟。空白符号是Z。开始时，此图案的有限部分被复制到n个零后跟1的位置。在最后一个1之后，放置n+1个A。在此初始常数部分之后，在执行过程中，当遇到A时，机器进入一个循环：将A替换为0，然后在第一个Z之后放置一个对应的A。一旦所有A都被移动，在末尾再放置一个A，并将A前面的Z与1交换。这个可计算的过程无需进行无限的初始工作就能再现非周期性图案。
+FSA可以描绘为转换表，或更直观地，作为有向图，其中顶点是状态，边是状态之间的转换。边用转换发生的输入信号标注。输出信号可以在边、顶点或两者上标注。
-依赖于不可计算初始化系统的通用机也是不可计算的。因此，当使用弱通用机证明图灵等价性时，必须证明它们能够被一台模拟通用机所在外部系统（包括图案生成）的图灵机所模拟。
+==语言识别==
-== 通用机示例 ==
+为了识别一个字符串是否属于形式语言的一部分，例如[[regular expression|正则表达式]]，信号是字符串的符号，最终状态决定FSA是否“接受”该字符串——即，与FSA关联的形式语言是否包含该字符串。这种FSA通常不产生输出，而仅仅结束于“接受”或“拒绝”状态，被称为'''接受器'''或'''识别器'''。
-* [[UT19]]，一个19符号通用[[tag system|2标签系统]]
-* [[Grill Tag#Turing machine implementation|一个实现[[Grill Tag]]的2状态、14符号图灵机]]
-* [[Gregušová-Korec universal Minsky machine|Gregušová-Korec通用明斯基机]]，一个37或32指令的[[Minsky machine|明斯基机]]
-== 外部资源 ==
+FSA足够强大以识别某些字符串集合，但不足以识别其他。例如，可以构造一个FSA，它能告诉你一个字符串是否以开括号开头并以闭括号结尾，无论该字符串有多长。然而，没有FSA能告诉你这些括号是否正确嵌套（正则表达式也不能）——为此，你需要一个[[push-down automaton|下推自动机]]。
-* [http://brainfuck.org/urmutm.txt 适用于URM的通用图灵机] 一个适用于修改版[[Minsky machine|明斯基机]]的5寄存器机器
-[[Category:概念]]
+==计算能力==
+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|计算模型]]