有限状态机（英語：finite-state machine，縮寫：FSM）又稱有限状态自动机（英語：finite-state automaton，縮寫：FSA），简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学计算模型。 状态存储关于过去的信息，就是说：它反映从系统开始到现在时...

在计算理论中，确定有限状态自动机或确定有限自动机（英語：deterministic finite automaton, DFA）是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表 Σ {\displaystyle \Sigma }...

在计算理论中，非确定有限状态自动机或非确定有限自动机（NFA）是对每个状态和输入符号对可以有多个可能的下一个状态的有限状态自动机。这区别于确定有限状态自动机（DFA），它的下一个可能状态是唯一确定的。尽管DFA和NFA有不同的定义，在形式理论中可以证明它们是等价的；就是说，对于任何给定NFA，都可以...

Q,\Sigma ,\delta \rangle } 被称为半自动机。半自动机位于自动机底下，它们就是忽略了开始状态和接受状态的自动机。开始状态和接受状态的补充概念允许自动机做半自动机不能做的事情: 它们可以识别形式语言。确定有限自动机 ⟨ Q , Σ , δ , q 0 , F ⟩ {\displaystyle...

在自动机理论（计算机科学的一个分支）中，确定有限状态自动机最小化是将给定的确定有限状态自动机（DFA, Deterministic Finite Automaton）改造为等价且拥有最少状态的DFA的过程。这里，两个DFA等价意味着他们识别相同的正则语言。各自动机理论的教材中，已经给出了若干已知的最小化算法。...

細胞自動機（英語：Cellular automaton），又稱格狀自動機、元胞自動機，是一種離散模型，在可计算性理論、數學及理論生物學都有相關研究。它是由無限個有規律、堅硬的方格組成，每格均處於一種有限狀態。整個格網可以是任何有限維的。同時也是離散的。每格於t時的態由t-1時的一集有限...

在自动机理论中，确定下推自动机（英語：Deterministic pushdown automaton，縮寫：DPDA）是可以使用了持有数据的栈的确定有限状态自动机。术语“下推”来自原型机械自动机物理上接触穿孔卡片来阅读其内容的下推动作。术语“确定下推自动机”当前指称识别确定上下文无关语言的抽象计算设备。...

在量子计算，量子有限自动机 (QFA) or 量子状态机 是 概率自动机 或 马尔可夫决策过程的量子模拟.。它们提供了现实世界 量子计算机的数学抽象。可以定义几种类型的自动机，包括一次测量和多次测量自动机。量子有限自动机也可以理解为 有限类型子位移的量子化, 或 马尔可夫链的量子化。反过来，QFA是几何有限自动机或拓扑有限自动机的特例。...

在自动机理论和时序逻辑中，状态转移表是展示有限半自动机或有限状态自动机基于当前状态和其他输入，要移动到什么状态（或在非确定有限状态自动机情况下那些状态）的表格。“状态表”本质上是其中某些输入是当前状态，而输出包含与其他输出在一起的下一个状态的真值表。 状态表是指定“状态机”的多种方式之一，其他方式包括状态图，和“特征等式”。...

自动机编程（英語：Automata-based programming）是編程範式中的一種，是指程式或其中的部份是以有限狀態機（FSM）為模型的程式，有些程式則會用其他型式（也更複雜）的自動機為其模型。 有限狀態機編程（英語：FSM-based programming）大致上等同於自动机...

DFA可能指 确定有限状态自动机（Deterministic Finite Automaton） 可裝配性設計（Design For Assembly） 差別錯誤分析（Differential Fault Analysis） 指定轉讓（Designated For Assignment） 德明信基金（Dimensional...

输入“符号”或指示符的有限搜集Σ（Booth, Hopcroft和Ullman, Sipser）。对于确定有限状态自动机（DFA），非确定有限状态自动机（NFA），广义非确定有限状态自动机（GNFA），或Moore机，输入被标记在每个边上，通常靠近发起状态。对于Mealy机，用斜杠“/”分隔的输入和输出都标记在每个边上：...

在计算理论中，摩尔型有限状态机（英語：Moore machine）是指输出只由当前的状态所确定的有限状态自动机。摩尔型有限状态机的状态图对每个状态包含一个输出信号，相对于米利型有限状态机，它映射机器中的“转移”到输出。 摩尔型有限状态机的名字来自它的提出者，写了《Gedanken-experiments...

在自动机理论中，下推自动机（英語：Pushdown automaton）是使用了包含数据的栈的有限自动机。 下推自动机比有限自动机复杂：除了有限状态组成部分外，还包括一个长度不受限制的栈；下推自动机的状态迁移不但要参考有限状态部分，也要参照栈当前的状态；状态迁移不但包括有限状态...

正则语言又称正规语言是满足下述相互等价的一组条件的一类形式语言： 可被确定有限状态自动机识别； 可被非确定有限状态自动机识别； 可被只读图灵机识别； 可用正则表达式描述； 可用正则文法生成。 可用前缀文法生成。 所有的有限语言都是正则的。 字母表{a, b}上包含偶数个a的所有字串构成的语言是正则的。...

methods）开始兴起，对格子气自动机方法的研究则趋缓了。 细胞自动机模型中，晶格格点具有有限的离散状态。在格子气自动机模型中，这些离散状态用以表示具有不同速度的粒子。流体模拟在离散的时间序列中演进，在每个时间步长后，格点的状态可由该时间步长前此格点与相邻格点的状态确定。 每个格点以一系列布尔值来描述给定位置上各速度方向是否有粒子存在。...

字母表在形式语言、自动机和半自动机的使用中很重要。在大多数情况下，为了定义自动机实例，如确定有限状态自动机（DFA），需要指定一个字母表，从这个字母表建立自动机的输入字符串。在这些应用中，通常要求字母表是一个有限集，但没有其他限制。 当使用自动机...

加上一個計數器的非确定有限状态自动机 加上一個計數器的确定有限状态自动机 沒有計數器或堆栈的确定型或非确定型有限状态机 針對第一個或是最後一個，有限状态机可以是确定型，也可以是非确定型。前二者及最後一個是依喬姆斯基譜系排列。 上述的第一種有限状态机，也就是有二個計數器的有限状态机，其計算能力和图灵机等效。 網頁計數器（英语：web...

线性有界自动机（英文：Linear bounded automaton，简写： LBA）是受限形式的非确定图灵机。它拥有由包含来自有限字母表的符号的单元构成的磁带，可以一次读取和写入磁带上一个单元的并可以移动的磁头，和有限数目个状态。它区别于更为普遍的图灵机在于尽管磁带最初被认为是无限的，只有其长度...

"tree"。但是，其他作者把它读作/ˈtraɪ/ "try"。 在图示中，键标注在节点中，值标注在节点之下。每一个完整的英文单词对应一个特定的整数。Trie可以看作是一个确定有限状态自动机，尽管边上的符号一般是隐含在分支的顺序中的。 键不需要被显式地保存在节点中。图示中标注出完整的单词，只是为了演示trie的原理。 可以在字典树算法的可视化演示...

汤普森构造法在计算机科学中是指一个能将正则表达式转化为一个与之等价的非确定有限状态自动机（NFA）的算法。算法得到的NFA可以在编程中用于匹配一个正则表达式，这也是正则表达式引擎实现的基本思路之一。 正则表达式和非确定有限状态自动机是形式语言的两种不同的抽象表达方式。在诸如文本编辑器的高级“查找和...

的极小自动机的转移幺半群。 等价的说，一个语言 L 是可识别的，当且仅当商的族 { L / m | m ∈ M } {\displaystyle \{L/m\,\vert \;m\in M\}} 是有限的。等价性的证明非常容易。假定字符串 x 是可被确定有限状态自动机识别的，带有最终机器状态是 f。如果...

在计算理论中，幂集构造是转换非确定有限状态自动机（NFA）到识别同样语言的确定有限状态自动机（DFA）的标准方法。它在理论上的重要性源于它确立了NFA尽管有额外的灵活性，它不能识别不能被任何DFA识别的任何语言。在实践中的重要性源于它把易于构造的NFA转换成了更有效执行的DFA。但是如果NFA有n个状态...

算法（英語：algorithm），在数学（算学）和计算机科学之中，指一个被定义好的、计算机可施行其指示的有限步骤或次序，常用于计算、数据处理和自动推理。算法可以使用条件语句通过各种途径转移代码执行（称为自动决策），并推导出有效的推论（称为自动推理），最终实现自动化。 相反，启发式是一种解决问题的方法，可能没...

因为L是正则语言，所以存在一个与之等价的确定有限状态自动机， 假设n是这个确定有限状态自动机中状态的数量， 假设 w ∈ L {\displaystyle w\in L} 和 | w | ≥ n {\displaystyle \left|w\right|\geq n} 在这个自动机读入w的前n个字符后一定有一个状态达到过两次，...

时间和空间效率在这种情况下都极其重要。例如说，当有程序在运行时解释正则表达式，并根据该正则表达式生成代码时，通常该程序会先生成非确定有限状态自动机而不是确定有限状态自动机，因为通常前者的创建速度以及占用的内存空间等属性往往会比后者更为优秀。 Steven Muchnick; Muchnick and...

Their Decision Problems）的论文，提出了非确定自动机的观点。他们也因此获得了1976年的图灵奖，并做“计算机复杂性”（Complexity of Computations）的演讲。图灵奖的引文是： 非确定自动机已经成为计算复杂度理论中的一个重要概念，特别是在描述P与NP问题的复杂度类时。...

确定有限状态自动机（NFA）之间有简单的映射；为此NFA经常被用作正则表达式的替表示式。 这种形式化中存在着冗余，典型的体现是存在不同的正则表达式可以表达同样的语言。有可能对两个给定正则表达式写一个算法来判定它们所描述的语言是否本质上相等，即简约每个表达式到极小确定有限自动机，确定...

述了许多日常现象，但在接近光速或是微觀層級時，这些定律就不适用，而需要用相对论或量子力学。 计算机科学中的一个常见模型是各种自动机，如用抽象数学概念定义的确定有限状态自动机（DFA），但是由于DFA的确定性性质，可以用硬件或软件来实现以解决各种具体问题。 许多日常活动都暗含着数学模型的运用。把地球的...

x_{n}} 。也有其他的全域約束，全域約束的出現擴展了約束架構可以可表達的範圍。在這些例子中，全域約束常會對應一種特殊組合問題的結構。例如确定有限状态自动机可以接受Regular（正則約束（英语：Regular constraint））的約束。 全域約束有用在簡化約束滿足問題的建模，擴展了約束語...

图灵机（英語：Turing machine），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种將人的計算行為抽象化的数理逻辑机，其更抽象的意义为一种计算模型，可以看作等价于任何有限逻辑，数学过程的强大可计算机器。 图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：...