确定有限状态自动机最小化
在自动机理论（计算机科学的一个分支）中，确定有限状态自动机最小化是将给定的确定有限状态自动机（DFA, Deterministic Finite Automaton）改造为等价且拥有最少状态的DFA的过程。这里，两个DFA等价意味着他们识别相同的正则语言。各自动机理论的教材中，已经给出了若干已知的最小化算法。 最小DFA 对于每个正则语言，都存在一个最小自动机接受它，即一个有着最小状态数目的DFA，且这个DFA是唯一的（除去状态命名不同…
标签：#自动机
共 24 篇文章
莱斯定理
莱斯定理（Rice's theorem）是可计算性理论中的一条定理，由亨利·戈登·莱斯于1953年提出。定理指出，递归可枚举语言的所有非平凡（nontrival）性质都是不可判定的。 “非平凡”是指，仅被部分递归可枚举语言具有的特性。 定理 P是所有图灵可计算函数构成的集合，S是P的一个非空真子集，即：\emptyset\neq S \subsetneq P。将图灵机以某种方式编码，使得每一个n\in \mathbb{N}都唯一对应一个…
Uppaal模型检查器
UPPAAL是一个用于对实时系统进行建模、确认和验证的集成工具环境，该系统以时序自动机网络为模型基础，并扩展到几种额外的数据类型（有界整数、数组等）。 自 1995 年发布以来，它已在至少 17 个研究案例中使用，包括Lego Mindstorms 、飞利浦音频协议和Mecel的变速箱控制器。 该工具是由瑞典乌普萨拉大学实时系统设计与分析小组和丹麦奥尔堡大学计算机科学基础研究中心合作开发的。 有以下可用的扩展： Cora用于成本最优可达…
图灵机
图灵机（），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种將人的計算行為抽象化的数理逻辑机，其更抽象的意义为一种计算模型，可以看作等价于任何有限逻辑，数学过程的强大可计算机器。 图灵的基本思想 图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作： 在纸上写上或擦除某个符号； 把注意力从纸的一处移动到另一处； 而在每个阶段，人要决定下一步的动作，依赖于（a）此人当前所关注的纸上某…
正则表达式
正则表达式（，常简写为、或），又称規律表達式、正規-{zh-cn:表示式; zh-tw:表達式; zh-hk:表示式;}-、正規表示法、規則運算式、常規表示法，是计算机科学概念，用簡單字串来描述、匹配文中全部符合指定格式的字串，現在很多文本编辑器都支援用正則表达式搜尋、取代符合指定格式的字串。 许多程序设计语言都支援用正則表达式操作字串，如Perl就内建功能强大的正則表达式引擎。正則表达式这概念最初由Unix的工具软件（例如sed和gr…
形式文法
在形式语言理论中，文法（formal grammar)是形式语言中字符串的一套产生式规则（production rule）。这些规则描述了如何用语言的字母表生成符合句法(syntax)的有效的字符串。文法不描述字符串的含义，也不描述在任何上下文中可以用它们做什么——只描述它们的形式。 形式语言理论是应用数学的一个分支，是研究形式文法和语言的学科。它在理論計算機科學、理论语言学、形式语义学、数理逻辑等领域有着广泛的应用。 形式文法是从一个…
嵌套堆栈自动机
在自动机理论中，嵌套堆栈自动机是可以利用持有作为附加栈的数据的栈的有限自动机。 嵌套堆栈自动机除了压入和弹出外还可以读它的栈。嵌套堆栈自动机有能力识别附标语言。 参见 * 自动机 引用
有限状态机
有限状态机（，缩写：FSM）又称有限状态自动机（，缩写：FSA），简称状态机，是表示有限个以及在这些状态之间的转移和动作等行为的数学计算模型。它是一台（真实或假设的）机器，其对于输入（input）的响应（或输出）形成于一组状态（state）和一组用于从某状态传递到另一状态的规则（rules）。 概念和术语 状态存储关于过去的信息，就是说：它反映从系统开始到现在时刻的输入变化。转移指示状态变更，并且用必须满足确使转移发生的条件来描述它。动…
抽象機器
抽象機器（），又稱抽象電腦（），利用自動機理論，建立出電腦硬體或軟體的理論模型。把運算過程抽象化，一般來說是採用離散時間模型，可應用於電腦科學或電腦工程。在計算理論中，抽象機器經常被當成是一種思想實驗，用來推論可計算性（），或是分析演算法的時間複雜度及空间复杂度。 参见 抽象機器 垃圾进，垃圾出 算法导论 计算理论 可计算性理论 計算複雜性理論 * 高级综合
确定有限状态自动机
在计算理论中，确定有限状态自动机或确定有限自动机（）是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表\Sigma的字符，它都能根据事先给定的转移函数转移到下一个状态（这个状态可以是先前那个状态）。 基础概念 定义 确定有限状态自动机\mathcal{A}是由 一个非空有限的状态集合Q 一个输入字母表\Sigma（非空有限的字符集合） 一个转移函数\delta: Q \times \Sigma \ra…
自動機理論
在理论计算机科学中，自动机理论是对抽象机和它们能解决的问题的研究。自动机理论密切关联于形式语言理论，因为自动机经常按它们所能识别的形式语言类来分类。 基本描述 自动机是有限状态机（FSM）的数学模型。FSM是给定符号输入，依据（可表达为一个表格的）转移函数“跳转”过一系列状态的一种机器。在常见的FSM的“米利型有限状态机”（Mealy）变体中，这个转移函数告诉自动机给定当前状态和当前字符的时候下一个状态是什么。 逐个读取输入中的符号，直…
下推自动机
在自动机理论中，下推自动机（）是使用了包含数据的栈的有限自动机。 综述 下推自动机比有限自动机复杂：除了有限状态组成部分外，还包括一个长度不受限制的栈；下推自动机的状态迁移不但要参考有限状态部分，也要参照栈当前的状态；状态迁移不但包括有限状态的变迁，还包括一个栈的出栈或入栈过程。下推自动机可以形象的理解为，藉由加上读取一个容量无限栈的能力，扩充一个能做\epsilon-转移的非确定有限自动机。 下推自动机存在“确定”与“非确定”两种形式…
米利型有限状态机
]] 在计算理论中，米利型有限状态机（）是基于它的当前状态和输入生成输出的有限状态自动机（更精确的叫有限状态变换器）。这意味着它的状态图将为每个转移边包括输入和输出二者。与输出只依赖于机器当前状态的摩尔有限状态机不同，它的输出与当前状态和输入都有关。但是对于每个米利机都有一个等价的摩尔机，该等价的摩尔机的状态数量上限是所对应米利机状态数量和输出数量的乘积加1（|S'|=|S||Λ|+1）。 名源 米利机的名字来自这个概念的提出者，在19…
确定下推自动机
在自动机理论中，确定下推自动机（，縮寫：DPDA）是可以使用了持有数据的栈的确定有限状态自动机。术语“下推”来自原型机械自动机物理上接触穿孔卡片来阅读其内容的下推动作。术语“确定下推自动机”当前指称识别确定上下文无关语言的抽象计算设备。 确定下推自动机是减弱版本的下推自动机。 定义 一个下推自动机(PDA) M 可以定义为一个 7-元组: M=(Q,\Sigma,\Gamma,q_0,Z_0,A,\delta) 这里的 Q 是状态的有限…
摩尔型有限状态机
]] 在计算理论中，摩尔型有限状态机（）是指输出只由当前的状态所确定的有限状态自动机。摩尔型有限状态机的状态图对每个状态包含一个输出信号，相对于米利型有限状态机，它映射机器中的“转移”到输出。 摩尔型有限状态机的名字来自它的提出者，写了《Gedanken-experiments on Sequential Machines》的状态机先驱愛德華·F·摩爾。 運作機制 多数数字电子系统被设计为时序系统。时序系统是受限制形式的摩尔型有限状态机…
非确定有限状态自动机
在计算理论中，非确定有限状态自动机或非确定有限自动机（NFA）是对每个状态和输入符号对可以有多个可能的下一个状态的有限状态自动机。这区别于确定有限状态自动机（DFA），它的下一个可能状态是唯一确定的。尽管DFA和NFA有不同的定义，在形式理论中可以证明它们是等价的；就是说，对于任何给定NFA，都可以构造一个等价的DFA，反之亦然：通过使用幂集构造。两种类型的自动机只识别正则语言。非确定有限自动机有时被称为有限类型的子移位（subshif…
半自动机
在数学和计算机科学中，半自动机或M-act是幺半群在集合上的乘法性运算。从代数结构的观点来看，它非常接近于群作用的概念。从计算机科学的观点来看，它是只有输入没有输出的自动机。从范畴论的观点来看，作用是如范畴上的函子般重要。 这个概念也叫做*S-集合、M-集合、M-操作数、S-系统、S-自动机、转移系统、算子幺半群、变换半群或转移幺半群。本文力图表现出它们表示的是同一个概念，尽管在使用中有各种概念和术语的变体。 变换半群 變換半群或變換幺…
线性有界自动机
线性有界自动机（英文：Linear bounded automaton，简写： LBA）是受限形式的非确定图灵机。它拥有由包含来自有限字母表的符号的单元构成的磁带，可以一次读取和写入磁带上一个单元的并可以移动的磁头，和有限数目个状态。它区别于更为普遍的图灵机在于尽管磁带最初被认为是无限的，只有其长度是初始输入的线性函数的有限临近部分可以被读写磁头访问。这个限制使 LBA 成为在某些方面比图灵机更接近实际存在的计算机的精确模型。 结构 线…
幂集构造
在计算理论中，幂集构造是转换非确定有限状态自动机（NFA）到识别同样语言的确定有限状态自动机（DFA）的标准方法。它在理论上的重要性源于它确立了NFA尽管有额外的灵活性，它不能识别不能被任何DFA识别的任何语言。在实践中的重要性源于它把易于构造的NFA转换成了更有效执行的DFA。但是如果NFA有n个状态，结果的DFA可能有最多2n个状态，这种指数增长有时使这种构造对于大NFA而言是不实际的。 动机 回想一下，NFA除了特定节点可能有“分…
状态图
状态器是有限状态自动机的图形表示。另一种可能的表示是状态转移表。状态图有很多形式，它们有稍微的差异并有不同的语义。 定义 有限状态自动机的状态图是由下列元素構成的有向图： 状态Q :表示为其中标记着唯一性指示符号或字的圆圈的顶点的有限集合（Booth（1967）p. 69, Hopcroft与Ullman（1979）p. 16, Sipser（2006）p. 34）。 输入符号Σ :输入“符号”或指示符的有限搜集Σ（Booth, Hop…