自动机理论

Combinational logic Finite-state machine Pushdown automaton Turing machine Automata theory
自动机的类
状态图所描述的自动机始于状态s 1 ,并根据输入符号到达时按标记为0或1的箭头更改状态。双圆标记为S 1是一种接受状态。由于从s 1到本身的所有路径都包含标记为0的均匀数量的箭头,因此该自动机接受包含偶数为0的字符串。

自动机理论是对抽像机器自动机的研究,以及可以使用它们解决的计算问题。这是理论计算机科学中的理论,与数学逻辑有紧密的联系。 Automata一词来自希腊语αὐτόματος,意思是“自我表演,自我燃烧,自我移动”。一个自动机(复数中的自动机)是一种抽象的自行式计算设备,它会自动遵循预定的操作序列。具有有限状态的自动机称为有限自动机(FA)或有限状态机器(FSM)。右侧的图显示了有限状态的机器,这是一种众所周知的自动机。该自动机由状态(在图中表示)和过渡(由箭头表示)组成。当自动机看到输入的象征时,它会根据其过渡函数将过渡(或跳跃)到另一个状态,该函数将先前的状态和当前输入符号作为其参数。

自动机理论与形式语言理论密切相关。在这种情况下,自动机被用作可能是无限的形式语言的有限表示。就像在乔姆斯基层次结构中那样,自动机通常由他们可以识别的形式语言类别进行分类,该层次结构描述了主要的自动机阶层之间的嵌套关系。自动机在计算理论编译器构造人工智能解析正式验证中起着重要作用。

历史

抽象自动机理论是在20世纪中叶与有限自动机有关的。自动机理论最初被认为是数学系统理论的一个分支,研究了离散参数系统的行为。自动机理论中的早期工作与以前在系统上的工作不同,通过使用抽象代数来描述信息系统而不是差分计算来描述材料系统。有限状态传感器的理论是由不同的研究社区以不同名称开发的。 Turing Machine的早期概念以及新形式的无限状态自动机(例如下降自动机)也包括在该学科中。

1956年看到了自动机研究的出版,该研究收集了包括克劳德·香农( Claude Shannon)W。RossAshbyJohn von NeumannMarvin MinskyEdward F. MooreStephen Cole Kleene等科学家的作品。随着该卷的出版,“自动机理论成为一门相对自主的学科”。这本书包括克莱恩(Kleene)对常规事件或普通语言集的描述,以及香农(Shannon)的图灵机器程序中相对稳定的复杂性。同年, Noam Chomsky描述了Chomsky层次结构,Automata和正式语法之间的对应关系,Ross Ashby发表了关于控制论的介绍,这是一本可访问的教科书,使用基本集合理论解释了自动机和信息。

线性界限自动机的研究导致了Myhill -hearse定理,这为正式语言提供了必要和充分的条件,并确切地计算了该语言中最小的机器中的状态数量。在此期间,迈克尔·罗宾( Michael O.

在1960年代,出现了一个被称为“结构理论”或“代数分解理论”的代数结果体系,它涉及通过互连从较小机器中实现顺序机器的实现。虽然可以使用通用门集对任何有限的自动机进行模拟,但这要求模拟电路包含任意复杂性的循环。结构理论涉及机器的“无环”可实现性。计算复杂性的理论在1960年代也形成了。到本十年末,自动机理论被视为“计算机科学的纯数学”。

自动机

接下来的是对自动机的一般定义,该定义将系统的更广泛定义限制在一个被视为在离散时步中起作用的系统,其状态行为和输出在每个步骤中定义,仅通过不变的状态和输入的函数来定义。

非正式描述

自动机在离散(单个)时间步长(或仅步骤)中给出某个输入序列时运行。一个自动机处理一个从一组符号字母中挑选的输入,该输入称为输入字母。自动机作为任何步骤输入的符号是一系列称为单词的符号。一个自动机具有一组状态。在自动机的运行过程中,自动机其一种状态之一中。当自动机接收新输入时,它会根据将先前状态和当前输入符号作为参数的过渡函数移至另一个状态(或过渡)。同时,另一个称为输出函数的功能也会根据先前的状态和当前输入符号产生输出字母的符号。自动机读取输入单词的符号和状态之间的过渡,直到单词在长度上是有限的,此时自动机停止。自动机停止的状态称为最终状态

为了使用形式语言理论研究自动机中可能的状态/输入/输出序列,可以为机器分配一个起始状态和一组接受状态。然后,根据从起始状态开始以接收状态开始的运行,可以说自动机接受拒绝输入序列。自动机接受的所有单词的集合称为自动机识别的语言。识别语言的机器的一个熟悉的示例是电子锁,它接受或拒绝尝试输入正确的代码。

正式定义

自动机
自动机可以用五重奏正式表示,其中:
  • 是一组有限的符号,称为自动机的输入字母,
  • 是另一组有限的符号,称为自动机的输出字母,
  • 是一组状态,
  • 是下一个状态函数或过渡函数映射状态输入对,
  • 是下一个输出函数映射状态输入对输出对。
如果是有限的,则是有限的自动机。
输入单词
自动机读取有限的符号字符串,其中称为输入单词。所有单词的集合都表示。
跑步
一系列状态,其中是从状态开始的输入上的自动机的运行。换句话说,起初自动机处于开始状态,并接收输入。对于输入字符串中的每个以后,自动机根据过渡函数选择下一个状态,直到读取最后一个符号为止,将机器处于运行的最终状态。同样,在每个步骤中,自动机根据输出函数发出输出符号。
当馈送整个输入单词时,将过渡函数归纳为描述机器的行为。对于所有状态的空字符串,对于字符串,最后一个符号是(可能是空的)弦的其余部分。输出函数可以相似地扩展到,从而使机器的完整输出在状态下运行。
受体
为了研究使用正式语言理论的自动机,可以将自动机视为受体,替代输出字母和功能,并用
  • ,指定的起始状态,以及
  • ,一组(IE)的状态称为接受状态。
这允许定义以下内容:
接受单词
单词是对自动机的接受单词,即如果在消耗整个字符串后,机器处于接受状态。
公认的语言
自动机识别的语言是自动机接受的所有单词的集合。
可识别的语言
可识别的语言是某些自动机识别的一组语言。对于有限自动机,可识别的语言是普通语言。对于不同类型的自动机,可识别的语言是不同的。

自动机的变体定义

自动机被定义为在数学形式主义下研究有用的机器。因此,自动机的定义是根据我们要使用自动机建模的“现实世界机器”开放的。人们研究了自动机的许多变体。以下是自动机不同组件的定义中的一些流行变体。

输入
  • 有限输入:仅接受有限符号序列的自动机。以上介绍性定义仅包含有限词。
  • 无限输入:接受无限单词( ω字)的自动机。这样的自动机称为ω-automata
  • 树输入:输入可以是符号的树,而不是符号序列。在这种情况下,在阅读每个符号后,自动机读取输入树中的所有后继符号。据说,自动机为每个后继者制作了一个自身的副本,并且每个这样的副本都根据自动机的过渡关系开始在州的一个后继符号上运行。这样的自动机称为树自动机
  • 无限树输入:可以将上面的两个扩展名组合在一起,因此自动机读取具有(IN)有限分支的树结构。这样的自动机称为无限树自动机
状态
  • 单状态:一个具有一个状态的自动机,也称为组合电路,执行可能实现组合逻辑的转换。
  • 有限状态:仅包含有限数量状态的自动机。
  • 无限状态:一种可能没有有限数量状态的自动机,甚至是可数次数的状态。可以使用不同种类的抽象存储器来提供此类机器有限描述。
  • 堆栈内存:自动机还可能包含一些堆栈形式的额外内存,其中可以推动符号并弹出符号。这种自动机称为下降自动机
  • 队列内存:自动机可能具有队列形式的内存。这样的机器称为队列计算机,正在图灵完成。
  • 磁带存储器:自动机的输入和输出通常被描述为输入和输出磁带。一些机器还有其他工作磁带,包括图灵机线性界限自动机日志空间传感器
过渡功能
  • 确定性:对于给定的当前状态和输入符号,如果自动机只能跳至一个状态,则它是确定性的自动机
  • 非确定性:一种自动机,在阅读输入符号后,可以通过其过渡关系许可进入许多状态中的任何一个。术语过渡函数被过渡关系替换:自动机在非确定性上决定跳入允许的选择之一。这样的自动机称为非确定性自动机
  • 交替:这个想法与树自动机非常相似,但是正交。自动机可以在下一个读取符号上运行其多个副本。这种自动机称为交替自动机。必须在所有此类副本上满足接受条件才能接受输入。
  • 双向:自动机可以从左到右读取其输入,或者可以以类似于图灵机的方式在输入上移动输入。可以在输入上向后移动的自动机称为双向有限自动机
接受条件
  • 接受有限词:与上述非正式定义相同。
  • 无限单词的接受ω-Automaton不能具有最终状态,因为无限单词永远不会终止。相反,通过在运行过程中查看无限状态的无限顺序来决定该词的接受。
  • 概率接受:自动机不必严格接受或拒绝输入。它可以接受零和一个之间的概率一定概率的输入。例如,量子有限自动机,几何自动机和公制自动机具有概率接受。

上述变化的不同组合会产生许多类别的自动机。

自动机理论是研究各种自动机构的特性的主题。例如,研究了有关给定类型的自动机的以下问题。

  • 某种类型的自动机可以识别哪种类型的形式语言? (可识别的语言)
  • 是否在联合,交叉路口或形式语言的补充下关闭了某些自动机? (封闭特性)
  • 在识别一类形式语言方面,一种自动机的表现方式如何?而且,他们的相对表现力吗? (语言层次结构)

自动机理论还研究了任何有效算法的存在或不存在,以解决类似于以下列表的问题:

  • 自动机至少接受一个输入单词吗? (空虚检查)
  • 是否可以在不更改识别语言的情况下将给定的非确定性自动机转换为确定性自动机? (确定)
  • 对于给定的正式语言,识别它的最小自动机是什么? (最小化

自动机的类型

以下是自动机类型的不完整列表。

自动机可识别的语言
非确定性/确定性有限状态机(FSM)普通语言
确定性下降自动机(DPDA)确定性的无上下文语言
倒计时自动机(PDA)无上下文的语言
线性有限自动机(LBA)上下文敏感语言
图灵机递归枚举语言
确定性的Büchi自动机ω-LIMIT语言
非确定性Büchi自动机ω-regular语言
Rabin AutomatonStreett AutomatonParity AutomatonMuller Automaton
加权自动机

离散,连续和混合自动机

通常,自动机理论描述了抽像机器的状态,但是分别使用数字数据,模拟数据或连续时间或数字模拟数据,有离散的自动机,模拟自动机或连续自动机或混合离散的连续自动机。

层次结构

关于不同类型的虚拟机的功率,以下是一个不完整的层次结构。层次结构反映了机器能够接受的语言的嵌套类别。

自动机
确定性有限自动机(DFA) - 最低功率

(相同的力量)(相同的力量)
非确定有限自动机(NFA)
(上面较弱)(下面更强大)
确定性按下自动机(DPDA-I)
有1个推销商店

非确定性按下自动机(NPDA-I)
有1个推销商店

线性有限自动机(LBA)

确定性推动自动机(DPDA-II)
有2个推销商店

非确定性按下自动机(NPDA-II)
有2个推销商店

确定性的图灵机(DTM)

非确定的图灵机(NTM)

概率图灵机(PTM)

多层图灵机(MTM)

多维图灵机

申请

自动机理论中的每个模型在多个应用领域都起着重要作用。有限自动机用于文本处理,编译器和硬件设计无上下文语法(CFG)用于编程语言和人工智能。最初,CFG用于人类语言的研究。蜂窝自动机被用于人造生活领域,最著名的例子是约翰·康威(John Conway)生活游戏。可以在生物学中使用自动机理论来解释的其他一些示例包括软体动物和松果的生长和色素沉着模式。进一步,一些理论表明,某些科学家提倡整个宇宙由某种离散的自动机计算得出。这个想法起源于Konrad Zuse的作品,并由爱德华·弗雷德金(Edward Fredkin)在美国普及。自动机还出现在有限领域的理论中:可以写入两个多项式组成的不可约多项式的集合实际上是一种规则的语言。可以使用自动机的另一个问题是诱导普通语言

自动机模拟器

自动机模拟器是用于教授,学习和研究自动机理论的教学工具。自动机模拟器作为输入自动机的描述,然后模拟其为任意输入字符串的工作。自动机的描述可以通过多种方式输入。可以用符号语言定义自动机,也可以以预先设计的形式输入其规范,或者可以通过单击和拖动鼠标来绘制其过渡图。众所周知的自动机模拟器包括图灵的世界,JFLAP,VAS,标签和Simstudio。

与类别理论的联系

一个人可以在自动机分类之后将几种不同类别的自动机定义为上一节中描述的不同类型。确定性自动机,顺序机器或顺序自动机的数学类别以及具有自动机同态定义自动机之间的箭头的Turing机器是笛卡尔封闭类别,它既具有分类限制又具有分类限制colimits 。一个自动构象的同构将一个自动机A i的五重奏映射到另一个自动机A j的五重奏。当自动机s的状态空间被定义为semigroup s g时,自动机同态也可以被视为自动变换或半群同构。单粒细胞也被认为是单型类别中自动机的合适设置。

可变自动机的类别

从诺伯特·维纳(Norbert Wiener)的意义上讲,在他的书中通过内态使用人类使用人类,也可以定义一个可变的自动机。然后,人们可以表明这种可变的自动机同构形成了数学组。在非确定性或其他复杂类型的自动机的情况下,后者的内态性可能会变成可变的自动机器人类型。因此,在最普遍的情况下,任何类型的可变自动机的类别都是类别类别的类别类别。此外,可逆自动机的类别是2类别,也是2类群体或Groupoid类别的子类别。

也可以看看