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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3-型文法（正规文法）生成正规语言。这种文法要求产生式的左侧只能包含一个非终结符号，产生式的右侧只能是空串、一个终结符号或者一个终结符号后随一个非终结符号；如果所有产生式的右侧都不含初始符号 S ，规则 S -> ε 也允许出现。这种文法规定的语言可以被有限状态自动机接受，也可以通过正则表达式来获得。正规语言通常用来定...

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

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

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

当状态集合Q是有限集合（不是必须的!）的时候，半自动机可以被认为是确定有限自动机 ( Q , Σ , T , q 0 , A ) {\displaystyle (Q,\Sigma ,T,q_{0},A)} ，但是没有“初始状态” q 0 {\displaystyle q_{0}} 或“接受状态...

变换半群 : 任何有限半群 S 都可以被表示为最多 |S|+1 个状态的(状态)集合 Q 的变换。S 的每个元素 x 是 Q 到自身的映射 x: Q → Q，序列 xy 定义为 q(xy) = (qx)y 对于 Q 中的每个 q。序列明显的是结合性运算，等价于函数复合。这种表示是任何自动机或有限状态机(FSM)的基础。...

在计算机科学中，模式匹配是检查给定记号序列中，是否存在某种模式的组成部分的行为。与模式识别相反，匹配通常必须是精确的。模式通常具有序列或树状结构的形式。模式匹配的用途包括：输出一个模式在一个记号序列中的位置（如果有的话），输出匹配模式的一些组成部份，以及用一些其他的记号序列替换匹配模式（即搜索和替换）。...

\delta p} 的值是任意的，熵没有一个确定值，必须如同上述增加一个常数项。这种微观状态分类方法叫做“组元配分”，相对应于量子力学选择的组元状态。 这种模糊概念被量子力学理论解决了，一个系统的量子状态可以被表述为组元状态的位置，选择作为非破缺的哈密顿函数的典型特征状态。在量子统计力学中， Ω {\displaystyle...

在动力系统中有所谓「状态」的概念，是一组可确定的实数。这组实数也是一种流形的几何空间坐标。动力系统的演化规则是一组函数的固定规律，描述了当前状态会如何产生未来状态。这种规则是确定的，即对于给定的时间间隔內，从现在的状态只能演化出一个未来的状态。不过也有随机的系统，因为随机事件也会影响状态变量的演化。...

机的次序列出： 计数器机——最原始和精简的模型。缺乏间接寻址。指令在按照哈佛结构的有限状态机内。 指针机——计数器机和RAM模型的混合。比这两个模型更少共通更多抽象。指令在按照哈佛结构的有限状态机内。 随机存取机（RAM）——带有间接寻址和通常扩充的指令集。指令在按照哈佛结构的有限状态机内。...

机的计算方面、用途的计算机或计算机语言。 到目前为止构建的现实计算机可以在功能上进行分析，就像单带图灵机（对应于它们的内存的“带”）一样； 因此，相关的数学问题可以通过足够抽象的运算来应用。但是，现实计算机的物理资源有限，因此它们仅是线性有界自动机。与之对应的，通用计算机...

的规则。因此，文法通常被认为是语言生成器。然而，它有时也可以用作“识别器”（计算机学中的一种函数，用于确定给定字符串是否属于该语言，是否为语法错误）的基础。形式语言理论使用另一个理论来描述识别器，也就是自動機理論。自动机理论有一个有趣的结果，某些形式语言是无法设计出识别器的。...

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