|
|
| 第1行： |
第1行： |
| 添加新语言时，需要以某种方式对其进行分类，以便更容易找到符合特定标准的语言。
| | '''有限状态自动机'''，简称 FSA，是一种简单的假想机器。它有时也被称为''有限状态机''、''有限自动机''或''有限状态转换器''。 |
|
| |
|
| 以下是在对语言进行分类时要考虑的特征列表。（关于''如何''应用分类的信息，请参阅[[mediawikiwiki:Help:Category|MediaWiki 文档的相关页面]]，但总结起来就是在页面底部写上 <tt><nowiki>[[Category:</nowiki>''分类名称'']]</tt>。）
| | ==定义== |
|
| |
|
| （如果下方列出的分类未链接，则表示该属性被认为不值得分类。）
| | （注意：FSA 用于各种目的——识别形式语言、建模系统的动态行为、表示视频游戏中的实体等——这些应用通常使用适合其问题域的略微不同的定义。我们将尝试在本页面上使用非常通用的定义，然后描述常见的变体。） |
|
| |
|
| 请注意，[[Esolang:Policy|站点政策]]规定，新分类应在[[Esolang talk:Categorization|Esolang talk:分类]]中讨论后再创建。
| | 在任何给定时间，FSA 可以处于有限数量的''状态''中的任何一种。它从外部源一个接一个地接收''输入信号''。当每个信号被接收时，FSA 根据输入信号和 FSA 的当前状态''转换''到另一个（可能相同的）状态。当没有更多输入信号需要处理时，可以认为 FSA 处于一个''最终状态''。 |
|
| |
|
| ==语言==
| | FSA 也可以被认为会产生''输出信号''，这些信号指向某个外部接收器。它可能在特定转换发生时（如在 Mealy 机中）或达到特定状态时（如在 Moore 机中）产生这些信号。（这两种情况是等价的，除了所需的状态数量。）输出信号可能与输入信号性质相同或不同。 |
| * [[:Category:Languages|分类:语言]]（这应出现在所有语言中，与例如[[:Category:Computational models|分类:计算模型]]相反）
| |
| ** [[:Category:Meta-languages|分类:元语言]]（例如 [[ALPACA]]）
| |
| ** [[:Category:Golfing language|分类:高尔夫语言]]
| |
| ** [[:Category:OISC|分类:OISC]]
| |
| ** [[:Category:Joke languages|分类:玩笑语言]]
| |
| ** [[:Category:Featured languages|分类:特色语言]]（见[[Esolang:Featured languages|Esolang:特色语言]]）
| |
| ** [[:Category:Markup Languages|分类:标记语言]]
| |
|
| |
|
| ==范式==
| | FSA 可以被认为能够在每次转换或状态时产生多个输出信号。或者，某些转换可能根本不依赖于输入信号，自动移动到新状态。（这两种情况也是等价的，除了所需的状态数量。） |
| * 命令式范式
| |
| * [[:Category:Functional paradigm|分类:函数式范式]]
| |
| * [[:Category:String-rewriting paradigm|分类:字符串重写范式]]
| |
| * [[:Category:Object-oriented paradigm|分类:面向对象范式]]
| |
| ** 基于类的范式
| |
| ** [[:Category:Prototype-based paradigm|分类:基于原型的范式]]
| |
| * [[:Category:Declarative paradigm|分类:声明式范式]]
| |
| * [[:Category:Cellular automata|分类:细胞自动机]]
| |
| * [[:Category:Particle automata|分类:粒子自动机]]
| |
| * [[:Category:Turning tarpits|分类:图灵焦油坑]] [原文如此]
| |
|
| |
|
| ==创建年份==
| | 所有状态对所有可能的输入信号都有转换。如果输入信号被认为是“非法的”，它不能被拒绝——FSA 仍然必须转换到某个状态。这通常通过拥有一个''非接受状态''来处理，所有状态在接收到“非法”输入信号时都转换到该状态，并且 FSA 永远无法“逃脱”该状态。这个状态通常从图中省略，只是隐含的。 |
| 这些分类说明语言是何时创建或首次发布的。见[[:Category:Years|分类:年份]]。
| |
|
| |
|
| {{yearcats}}
| | FSA 的行为可以是确定性的或非确定性的；一个非确定性的 FSA 可以同时处于多个状态；如果存在''某种''选择路径导致接受状态，它就接受输入。对于识别器，有一种算法可以消除非确定性，但通常会大大增加状态数量（最多 2<sup>''n''</sup>，其中 ''n'' 是非确定性自动机中的状态数）。 |
|
| |
|
| ==确定性== | | ==描述== |
| * 确定性的
| |
| * [[:Category:Nondeterministic|分类:非确定性的]]
| |
| ** [[:Category:Probabilistic|分类:概率性的]]
| |
|
| |
|
| ==内存==
| | FSA 可以描述为转换表，或者更直观地，描述为有向图，其中顶点是状态，边是从状态到状态的转换。边用转换发生的输入信号标注。输出信号可以标注在边上、顶点上，或两者上。 |
| * 基于变量、动态内存等
| |
| * [[:Category:Cell-based|分类:基于单元格的]]
| |
| * [[:Category:Stack-based|分类:基于堆栈的]]
| |
| * [[:Category:Queue-based|分类:基于队列的]]
| |
| * [[:Category:Deque-based|分类:基于双端队列的]]
| |
| * [[:Category:Tree-based|分类:基于树的]]
| |
| * [[:Category:Matrix-based|分类:基于矩阵的]]
| |
|
| |
|
| ==编写程序的可用性== | | ==语言识别== |
| * 可用的
| |
| * [[:Category:Unusable for programming|分类:无法用于编程的]]
| |
| * [[:Category:Usability unknown|分类:可用性未知]]
| |
| * [[:Category:Usability not set|分类:可用性未设置]]
| |
|
| |
|
| ==量子性==
| | 为了识别一个字符串是否属于形式语言（如[[regular expression|正则表达式]]）的一部分，信号是字符串的符号，最终状态决定 FSA 是否“接受”该字符串——即，与 FSA 关联的形式语言是否包含该字符串。这种 FSA 通常不产生输出，而只是以“接受”或“拒绝”状态结束，被称为'''接受器'''或'''识别器'''。 |
| * 非量子的
| |
| * [[:Category:Quantum computing|分类:量子计算]]
| |
|
| |
|
| ==并发性==
| | FSA 足够强大以识别某些字符串集合，但不能识别其他。例如，可以构造一个 FSA，它可以告诉你一个字符串是否以开括号开头并以闭括号结尾，无论该字符串有多长。然而，没有 FSA 可以告诉你这些括号是否正确嵌套（正则表达式也不能）——为此，你需要一个[[push-down automaton|下推自动机]]。 |
| * 非并发的
| |
| * [[:Category:Concurrent programming|分类:并发编程]]
| |
|
| |
|
| ==可逆性== | | ==计算能力== |
| * 不可逆的
| |
| * [[:Category:Reversible computing|分类:可逆计算]]
| |
|
| |
|
| ==计算类别==
| | FSA 具有较小但并非微不足道的计算能力——如上所述，它足以识别正则表达式。例如，它可以相加两个无界整数。 |
|
| |
|
| 对应于乔姆斯基层级的分类已被用作包容性分类，除了图灵完全类别。这意味着该类别是可以包容语言所有程序的最小计算模型。这对于图灵完全是相反的，因此图灵完全语言必须能够包容所有图灵机。
| | 许多更强大的计算模型在施加了简单限制后，被证明在计算上等同于 FSA。例如，只能向右移动的[[Turing machine|图灵机]]在计算上等同于 FSA。 |
|
| |
|
| * [[:Category:Turing complete|分类:图灵完全]] - 可以模拟任何[[Turing machine|图灵机]]的语言
| | 许多[[esoteric programming language|深奥编程语言]]属于与 FSA 相同的[[computational class|计算类别]]。 |
| ** [[:Category:Turing tarpits|分类:图灵焦油坑]]
| |
| * [[:Category:Linear bounded automata|分类:线性有界自动机]] - 可以由[[linear bounded automata|线性有界自动机]]模拟的语言
| |
| * [[:Category:Push-down automata|分类:下推自动机]] - 可以由[[pushdown automata|下推自动机]]模拟的语言
| |
| * [[:Category:Finite state automata|分类:有限状态自动机]] - 可以由[[finite state machine|有限状态机]]模拟的语言
| |
|
| |
|
| 其他分类：
| | ==历史== |
|
| |
|
| * [[:Category:Total|分类:完全]] - [[total|完全的]]语言，其中所有程序都停止
| | 可以在有限数量的内部状态之间转换的系统早已为人所知，但直到计算机科学早期历史相对较晚时才被正式研究。 |
| * [[:Category:Uncomputable|分类:不可计算]] - [[uncomputable|不可计算的]]语言，无法由图灵机模拟
| |
| * [[:Category:Unknown computational class|分类:未知计算类别]]
| |
|
| |
|
| ==输入/输出能力==
| | 以下引文来自 Rabin 和 Scott[1959, “Finite automata and their decision problems,” IBM Journal of Research and Development 3,2 (April, 1959), 114]： |
| * 有IO
| |
| * [[:Category:No IO|分类:无IO]]
| |
| * [[:Category:Output only|分类:仅输出]]
| |
| * [[:Category:Graphical Output|分类:图形输出]] ''（这个讨论过吗？）''
| |
| * [[:Category:Audio Output|分类:音频输出]] ''（这个讨论过吗？）''
| |
|
| |
|
| ==衍生语言==
| | ：“图灵机被广泛认为是数字计算机的抽象原型；然而，该领域的工作者越来越感到图灵机的概念过于笼统，无法作为实际计算机的准确模型。众所周知，即使是简单计算，也无法为图灵机在任何给定计算中所需的磁带量给出先验上界。正是这一特性使得图灵的概念不切实际。” |
| * 非衍生语言或不在此列表中
| |
| * [[:Category:Brainfuck derivatives|分类:Brainfuck 衍生语言]]
| |
| ** [[:Category:Brainfuck equivalents|分类:Brainfuck 等价语言]]
| |
| * [[:Category:Aubergine derivatives|分类:Aubergine 衍生语言]] ''（这个讨论过吗？）''
| |
|
| |
|
| ==维度==
| | ：“在过去几年中，有限自动机的概念出现在文献中。这些机器只有有限数量的内部状态，可用于内存和计算。有限性的限制似乎能更好地近似物理机器的概念。当然，这样的机器不能像图灵机那样做那么多事情，但能够计算任意一般递归函数的优势是值得怀疑的，因为在实际应用中很少出现这些函数。” |
| * [[:Category:Zero-dimensional|分类:零维]]
| |
| * 一维
| |
| * [[:Category:Multi-dimensional languages|分类:多维语言]]
| |
| ** [[:Category:Two-dimensional languages|分类:二维语言]]
| |
|
| |
|
| ==已实现==
| | [[Category:Computational models|分类:计算模型]] |
| * [[:Category:Implemented|分类:已实现]]
| |
| * [[:Category:Unimplemented|分类:未实现]]
| |
| | |
| ==源代码格式==
| |
| * 基于文本
| |
| ** [[:Category:Binary|分类:二进制]]
| |
| * [[:Category:Pattern-based|分类:基于模式]]
| |
| * [[:Category:CJK|分类:CJK]]（中文/日文/韩文字符）
| |
| * [[:Category:Non-textual|分类:非文本]]
| |
| ** [[:Category:Steganography|分类:隐写术]]（见[[Steganography|隐写术]]）
| |
| * [[:Category:Pseudonatural|分类:伪自然]]（程序类似于自然语言（即人类使用的语言）中的文本）
| |
| | |
| ==抽象级别==
| |
| * [[:Category:Low-level|分类:低级]]
| |
| * [[:Category:High-level|分类:高级]]
| |
| | |
| ==自修改==
| |
| * 不自修改
| |
| * [[:Category:Self-modifying|分类:自修改]]
| |
| | |
| ==主题==
| |
| * 无主题
| |
| * [[:Category:Thematic|分类:主题性]]
| |
| | |
| ==结构==
| |
| * 扁平
| |
| * [[:Category:Nested|分类:嵌套]]
| |
| * [[:Category:Flat-nested|分类:扁平嵌套]]
| |
| | |
| ==对代码的依赖==
| |
| * 代码型深奥语言
| |
| * [[:Category:No-code esolang|分类:无代码深奥语言]]
| |
| | |
| ==杂项==
| |
| * [[:Category:People|分类:人物]] 用于[[esoteric programmer|深奥程序员]]和其他知名人士
| |
| * [[:Category:Concepts|分类:概念]] 用于[[infinity|无限性]]、[[computational class|计算类别]]等
| |
| * [[:Category:Proofs|分类:证明]] 用于证明或尝试证明某事的页面
| |
| * [[:Category:Program forms|分类:程序形式]] 用于通常在深奥编程语言中实现的程序类别
| |
| * [[:Category:Programming techniques|分类:编程技术]] 用于讨论如何在深奥语言中编程的页面
| |
| * [[:Category:Data Types and Structures|分类:数据类型和结构]] 用于数据类型和结构
| |
| * [[:Category:Examples|分类:示例]] 用于主要包含代码示例的文章
| |
| * [[:Category:Implementations|分类:实现]] 用于深奥编程语言的实现以及常规语言的深奥实现
| |
| * [[:Category:Programming games|分类:编程游戏]] 用于基于编程或与编程相关的游戏，或与之相关的文章
| |
| * [[:Category:Esoteric subset|分类:深奥子集]] 用于作为其他语言（包括严肃语言和深奥语言）子集的深奥语言
| |
| | |
| ==另见==
| |
| * [[Special:Categories|特殊:分类]] -- 由 MediaWiki 软件生成的、本维基实际使用的所有分类列表
| |
| * [[Special:UncategorizedPages|特殊:未分类页面]] -- 自动生成的、缺少分类的页面列表
| |
有限状态自动机，简称 FSA，是一种简单的假想机器。它有时也被称为有限状态机、有限自动机或有限状态转换器。
定义
（注意：FSA 用于各种目的——识别形式语言、建模系统的动态行为、表示视频游戏中的实体等——这些应用通常使用适合其问题域的略微不同的定义。我们将尝试在本页面上使用非常通用的定义，然后描述常见的变体。）
在任何给定时间，FSA 可以处于有限数量的状态中的任何一种。它从外部源一个接一个地接收输入信号。当每个信号被接收时，FSA 根据输入信号和 FSA 的当前状态转换到另一个（可能相同的）状态。当没有更多输入信号需要处理时，可以认为 FSA 处于一个最终状态。
FSA 也可以被认为会产生输出信号，这些信号指向某个外部接收器。它可能在特定转换发生时（如在 Mealy 机中）或达到特定状态时（如在 Moore 机中）产生这些信号。（这两种情况是等价的，除了所需的状态数量。）输出信号可能与输入信号性质相同或不同。
FSA 可以被认为能够在每次转换或状态时产生多个输出信号。或者，某些转换可能根本不依赖于输入信号，自动移动到新状态。（这两种情况也是等价的，除了所需的状态数量。）
所有状态对所有可能的输入信号都有转换。如果输入信号被认为是“非法的”，它不能被拒绝——FSA 仍然必须转换到某个状态。这通常通过拥有一个非接受状态来处理，所有状态在接收到“非法”输入信号时都转换到该状态，并且 FSA 永远无法“逃脱”该状态。这个状态通常从图中省略，只是隐含的。
FSA 的行为可以是确定性的或非确定性的；一个非确定性的 FSA 可以同时处于多个状态；如果存在某种选择路径导致接受状态，它就接受输入。对于识别器，有一种算法可以消除非确定性，但通常会大大增加状态数量（最多 2n，其中 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]：
：“图灵机被广泛认为是数字计算机的抽象原型；然而，该领域的工作者越来越感到图灵机的概念过于笼统，无法作为实际计算机的准确模型。众所周知，即使是简单计算，也无法为图灵机在任何给定计算中所需的磁带量给出先验上界。正是这一特性使得图灵的概念不切实际。”
：“在过去几年中，有限自动机的概念出现在文献中。这些机器只有有限数量的内部状态，可用于内存和计算。有限性的限制似乎能更好地近似物理机器的概念。当然，这样的机器不能像图灵机那样做那么多事情，但能够计算任意一般递归函数的优势是值得怀疑的，因为在实际应用中很少出现这些函数。”
_icon.png
){kind=icon}
_wordmark.png)