自动机理论教程

自动机理论是计算机科学的一个分支，它处理设计抽象的、自动驱动的计算设备，这些设备自动遵循预定的操作序列。

一个状态数有限的自动机称为有限自动机。这是一个简短而简洁的教程，在介绍图灵机和可判定性之前，介绍了有限自动机、正则语言和下推自动机的基本概念。

谁应该学习自动机理论？

本教程是为攻读任何信息技术或计算机科学相关领域学位的学生准备的。它旨在帮助学生掌握自动机理论中涉及的基本概念。

学习自动机理论的先决条件

本教程在理论和数学严谨性之间取得了良好的平衡。读者应该具备离散数学结构的基本理解。

什么是自动机理论？

在数学和计算机科学中，自动机理论处理抽象机器和计算问题。自动机是自动遵循预定操作的自驱动计算设备。

根据约翰·冯·诺依曼的说法，“自动机理论是一种逻辑理论，它处理自动机和信息的研究，强调需要一个详细的、数学的和分析的理论来理解复杂的自动机。”

什么是自动机？

自动机是一种有限尺寸的设备，具有指定的输入和输出，其行为由输入决定。换句话说，自动机指的是自动运行的机械物体，它们根据预定的指令或程序转换信息。

自动机也可以指代一类机电设备，既有理论上的，也有现实中的，它们在被启动后转换信息。

自动机的主要类型是什么？

自动机可以分类如下：

• 有限自动机 - 有限自动机是一种状态数有限的自动机，它根据输入符号串改变其状态。当搜索到期望的符号时，就会发生转换。
• 下推自动机 - 下推自动机 (PDA) 是一种基于栈的自动机，用于计算理论。它比有限状态机更强大，可以解决比 FA 更复杂的问题。
• 图灵机 - 图灵机是一种理论设备，它使用规则表来操作磁带上的一系列符号，该磁带由无限长的磁带组成，磁带被分成包含 1、0 或空位的单元格。
• 线性界限自动机 - 线性界限自动机 (LBA) 是一种图灵机，它只使用输入磁带空间，这与图灵机不同。它的长度是输入长度的线性函数，并且读写头只能访问磁带的有限连续部分。
• 元胞自动机 - 元胞自动机是确定性系统，它们在离散的时间和空间中演化，通常是网格。它们由局部更新的单元格组成，这些单元格遵循全局时间尺度和递归规则，在网格上同步更新。

什么是有限自动机？

有限状态机 (FSM)是一种计算的数学模型，在任何给定时间都可以处于有限数量的状态之一。它可以根据输入（称为转换）从一个状态更改为另一个状态。

FSM 由其状态、初始状态和输入定义。FSM 有两种类型：确定性和非确定性。对于任何非确定性 FSM，都可以构造出一个等价的确定性 FSM。

确定性和非确定性有限自动机之间的区别

下表突出了确定性和非确定性有限自动机之间的主要区别：

什么是下推自动机？

下推自动机是非确定性有限状态机，其额外内存采用栈的形式。它比 FSM 更强大，但比图灵机弱。它们接受上下文无关语言。

例如，为了确保代码有效，程序员可以将代码输入到一个下推自动机中，该自动机使用实现平衡括号语言的上下文无关文法的转移函数进行编程。如果代码有效且所有括号都匹配，则下推自动机将接受该代码。如果存在不平衡的括号，则自动机可以返回代码的无效性。

什么是图灵机？

图灵机是一种抽象的计算模型，它通过读写无限长的磁带来执行计算。它为解决计算机科学问题和测试计算的极限提供了强大的计算模型。图灵机是由艾伦·图灵在 1936 年发明的。

图灵机由无限长的磁带、磁头和状态转移表组成。它们在输入位串上执行，磁头处于某个状态，表控制其行为。

图灵机可以模拟程序的复杂性和其对内存中不同数据的反应。

什么是乔姆斯基层次结构？

乔姆斯基层次结构是计算机科学和语言学中的一个分类系统，它包含四个级别：

• 0 型（无限制）
• 1 型（上下文相关）
• 2 型（上下文无关）
• 3 型（正则）

以诺姆·乔姆斯基命名，它描述了不同类型形式语言和文法的表达能力。它是形式语言研究中的一个基本概念，用于开发语法分析算法和其他用于处理形式语言的工具。

什么是上下文无关语言？

上下文无关语言 (CFL)是由上下文无关文法生成的，它与下推自动机接受的语言集相同。正则语言是上下文无关语言的子集，如果输入语言以接受的最终状态结束，则计算模型接受这些语言。

形式语言理论将语言定义为受特定规则约束的一组符号，例如书面英语。有效的句子必须遵循特定的语法规则。上下文无关语言是由上下文无关文法生成的语言，它可以由多个上下文无关文法生成，这使得它更通用和包容性。

$\mathrm{\lbrace a^{n}b^{n} \: | \: n > 0\rbrace}$ 是上下文无关文法的示例，它表示所有 a 和 b 个数相等的字符串。例如 $\mathrm{a^{4}b^{4}}$ 是 aaaabbbb。

什么是上下文相关语言？

上下文相关文法比上下文无关文法更强大，因为它们能够描述某些上下文无关文法无法描述的语言。在乔姆斯基层次结构中，它们位于上下文无关文法和无限制文法之间。

上下文相关文法 (CSG) 允许生成规则被终结符和非终结符包围。

$\mathrm{\lbrace a^{n}b^{n}c^{n} \: | \: n > 0\rbrace}$ 是一个CFG的例子，它表示所有 a、b 和 c 的数量相等的字符串。例如 $\mathrm{a^{4}b^{4}c^{4}}$ 是 aaaabbbbcccc。要通过 CSG 生成这种语言，需要在生成过程中跟踪左右上下文。

什么是递归可枚举语言？

递归可枚举 (RE) 语言，也称为 0 型语言，由 0 型文法生成，并且可以被图灵机接受或识别。

对于语言的字符串，RE 语言可以进入最终状态；对于非语言字符串，它可能进入或可能不进入拒绝状态。对于非语言字符串，图灵机可能会永远循环，这使得它们成为图灵可识别语言。

这些字符串可能执行以下操作之一：

• 停止并接受
• 停止并拒绝
• 永远循环

递归可枚举的另一个子集是递归语言，它可以被全图灵机接受，并且将在以下两种情况之一中停止：“停止并接受”或“停止并拒绝”。

抽运引理的意义是什么？

抽运引理 是一种引理（通常是较小的、经过证明的命题，可以用作通往更大结果的垫脚石），我们通过反证法来证明某些东西。在 TOC 中，抽运引理用于反证某种语言是正则的或上下文无关的（如果我们对 CFG 使用抽运引理）。

抽运引理可以作为一种工具来证明某些语言不是正则的或不是上下文无关的。通过应用抽运引理，我们可以证明某些语言不能被有限自动机或下推自动机识别。这在理论计算机科学和形式语言理论中特别有用，用于确定这些计算模型的局限性。

抽运引理有助于对语言进行分类，并了解不同类型的自动机的功能和约束。

在形式语言的上下文中，什么是文法？

形式文法是形式语言中字符串的一组生成规则，定义哪些字符串根据语言的语法是有效的，而不是它们的含义或上下文。它专注于形式语言中这些字符串的形式。

它表示为 G(V, N, P, S)。它生成字母表上所有句法上正确的字符串，主要用于语法分析阶段，特别是在编译期间，在编译阶段。

G = (V, N, P, S) 是一个文法，其中：

• N 是非终结符的有限集合
• V 是终结符的有限集合
• P 描述一组生成规则
• S 是起始符号

语言和文法之间的区别

文法是一组生成规则，用于生成语言的字符串。文法 不过是符号、生成规则和起始符号的集合，通过四元组 G = (V, N, P, S) 表示。

另一方面，语言是文法的产物。如果没有定义文法，我们就无法创建语言。在下面的示例中，展示了文法和该文法使用的语言的概念。

$$\mathrm{G \: = \: (V,N,P,S) \: = \: (\lbrace S,A,B,C \rbrace , \: \lbrace a,b,c \rbrace , \: \lbrace S \rightarrow ABC, \: A\rightarrow a, \: B\rightarrow b, \: C\rightarrow c \rbrace , \: \lbrace S \rbrace)}$$

通过此文法可以形成一个可能的语言 L(G)，L(G) = {abc}

从 S → ABC、A → a、B → b 和 C → c，它将生成“abc”，这是一个语言。

可判定问题和不可判定问题之间的区别

对于可判定问题，算法可以为任何给定实例提供明确的答案，例如“是”或“否”，而不可判定性指的是没有算法可以为所有可能的实例提供明确答案的问题。

什么是停机问题？

停机问题是可计算理论中的一个判定问题，用于确定计算机程序是否会终止或永远运行。

例如，如果我们从用户那里获取一个正数“x”（x > 0），并在 while 循环中检查“x”是否为 0，在循环中我们不更新“x”的值。这将永远不会停止。

停机问题是一个众所周知的问题，已被证明是不可判定的，这意味着没有程序可以解决足够通用的计算机程序的停机问题。

图灵机在计算理论中经常被用作与“普通计算机”一样强大的工具。1936 年，艾伦·图灵使用图灵机证明了图灵机上的停机问题是不可判定的，这意味着没有图灵机可以正确地决定所有可能的程序/输入对。

在计算复杂度中，P 类和 NP 类是什么？

P 是一种复杂度类，它包含可以使用确定性图灵机在多项式时间内解决的判定问题。它通常被认为是“有效可解”或“易处理的”计算问题。

难处理问题在理论上是可解的，但在实践中无法解决。P 包含诸如计算最大公约数、查找最大匹配等自然问题，确定一个数是否为素数也属于 P。

NP 或非确定性多项式时间是一组在非确定性图灵机上可以在多项式时间内解决的判定问题。这些问题可以通过确定性图灵机在多项式时间内进行验证。一些示例包括布尔可满足性问题 (SAT)、哈密顿路径问题（TSP 的特例）、顶点覆盖问题等。

NP 完全问题和 NP 难问题之间的区别

在计算理论中，如果存在一个现有的 NP 完全问题 Y 可以被在多项式时间内规约到问题 X，则问题 X 可以称为 NP 难。

NP 难问题的难度级别类似于 NP 完全问题。但是，NP 难问题不一定要属于 NP 类。一个问题只有在同时属于 NP 难和 NP 问题时才能成为 NP 完全问题。

在自动机的上下文中，什么是转移函数？

在自动机理论的上下文中，有一些表格包含状态、输入符号、起始状态、最终状态集和转移函数。

(Q, Σ, q0, F, T)，其中 Q 是状态集，Σ 是输入符号。

当状态 q 从集合 Σ 中获取输入时，它会从 q 发送到另一个集合 q' 或 q 本身。基于输入的转换在转移函数中定义。转移函数集在集合 T 中提及。

在这个状态图中，有几个转换，其中一些可能是：

$$\mathrm{\delta(q1, 0) \: \rightarrow \: q2}$$

$$\mathrm{\delta(q3, 1) \: \rightarrow \: qf}$$

什么是状态图？

自动机理论中的状态图是有限自动机行为的可视化表示。

它由表示状态的顶点 (集合 Q)、输入符号 (Σ) 和输出符号 (Z)（如果没有输出集，它可以具有 Q 的子集、F 最终状态或接受状态的集合以及一组转换 T）组成。

它用于通过显示可能的状态和这些状态之间的转换来描述和分析系统行为。状态图提供了一种清晰简洁的方法来理解有限自动机的可能状态和转换。

这是一个状态图示例：

这里我们有四个状态

• Q = {q1, q2, q3, qf}
• 最终状态 F = {qf}
• 输入 Σ = {0, 1}
• 初始状态 q1

并且，

$$\mathrm{T \: = \: \lbrace \delta(q1, 0) \: \rightarrow \: q2, \: \delta(q1, 0) \: \rightarrow \: q3, \: \delta(q2, 1) \: \rightarrow \: q1, \: \delta(q2, 1) \: \rightarrow \: q3, \: \delta(q3, 1) \: \rightarrow \: qf \rbrace}$$

状态在自动机中的意义是什么？

自动机理论用于概念化一个系统，有助于在现实生活中设计它。它必须具有与输入相关的输入、输出和转换。状态图中状态是表示系统有限数量的条件或情况的基本组件。

状态对于分析和表示系统的行为、跟踪对象的不同条件至关重要。一组有限的状态描述了自动机响应输入符号的行为。这种基于状态的方法对于可以抽象成有限数量的不同条件的系统特别有用。

什么是确定性下推自动机？

确定性下推自动机 (DPDA 或 DPA) 是自动机理论中下推自动机的变体，它接受确定性上下文无关语言。

此处，机器转换基于当前状态、输入符号和栈顶符号，较低层级的符号不会产生直接影响。机器操作包括入栈、出栈或替换栈顶元素。

正式地讲，对于一个 PDA 机器，**M = (Q, Σ, Γ, δ, q0, z, F)** 是确定的，如果对于每个 **q ∈ Q, a ∈ Σ ∪ {λ}, b ∈ Γ**

• **δ(q, a, b)** 至多只有一个元素。
• 如果 **δ(q, λ, b)** 非空，则对于每个 **c ∈ Σ**，**δ(q, c, b)** 必须为空。

什么是非确定性下推自动机？

非确定性下推自动机 (NPDA) 是一种机器，它拥有 NFA 和栈的所有特性。它的程序利用当前状态、读写头下的当前符号以及栈顶符号来做出决策。NPDA 比确定性 PDA 更强大。

NPDA 中的栈与输入带的“语言”字母表是不同的。栈在控制自动机的起始状态使用，栈中只有初始符号。

在每一步中，状态、输入元素和栈顶符号决定下一步（转换）。转换步骤包括改变状态、从输入带读取符号、向右移动到下一个符号以及修改栈。

什么是通用图灵机？

图灵机是一种数学工具，等价于数字计算机（图灵，20世纪30年代）。它包含一个机器计算的输入输出关系，输入以二进制形式给出在机器的带上。输出包括机器停止时带的内容。带的内容由图灵机内部的有限状态机 (FSM) 决定。

然而，图灵机需要为每个新的计算和输入输出关系构建一个不同的图灵机。这导致了通用图灵机 (UTM) 的发明，它接收机器 M 的描述，并可以在输入带剩余内容上模拟它。

请查看以下通用图灵机的概念图 -

在这里，我们使用无限长的带，UTM 在上面工作，但此外它还从一个单独的模块中获取机器描述或状态转换到 UTM 模块，在实现中，带本身在单独的区域保存机器描述。

为什么在计算机科学中使用形式语言？

在计算机科学中，形式语言是在一个有限的符号集（称为字母表）上的一组字符串，并且使用此字母表根据定义的语法规则创建的结构化字符串构成了形式语言。

形式语言围绕三个关键概念构建：字母表、字符串和语法。

• **字母表**是有限的一组不同的符号，
• **字符串**是从字母表中选择的一系列有限符号。符号的顺序在字符串中很重要，空字符串包含零个符号。
• **语法**是一组正式规则，用于控制符号的组合以构成形式语言中的字符串。

这些规则对于不同类别的形式语言（如正则语言、上下文无关语言、上下文相关语言和递归可枚举语言）是不同的。

自动机在解析中的作用是什么？

解析是一个基于语法的过程，它使用产生式规则推导出一个字符串并检查其可接受性。它是一个用于检查字符串是否在语法上正确的工具。

解析器可以是自顶向下或自底向上，从顶部开始使用开始符号并使用语法树来推导出字符串。

自顶向下解析

• PDA 使用自顶向下解析将语法的开始符号与其栈中的输入进行匹配。
• 如果它是一个终结符，则将其与当前输入符号进行比较，
• 如果它是非终结符，则用产生式规则替换。
• 栈跟踪解析上下文和预期符号，如果栈为空并且所有输入都被消耗，则接受输入。

自底向上解析

• PDA 从一个空栈开始并读取输入符号。
• 它通过移进-归约动作将序列简化为非终结符。
• 栈包含部分构建的语法树，如果在所有输入都被消耗时存在开始符号，则接受输入。

什么是线性有界自动机？

一个线性有界自动机是一个多轨道的非确定性图灵机，其带的长度有限。线性有界自动机中的计算被限制在一个恒定的有界区域内，其中两个特殊的符号充当左右端标记。

确定性线性有界自动机是上下文相关的，而具有空语言的线性有界自动机是不可判定的。

非确定性线性边界算法 (LBA) 与上下文相关语言的关系与下推自动机与上下文无关语言的关系相同。

目前尚不清楚 LBA 的确定性版本是否与非确定性版本具有相同的功效。

它是一个 9 元组自动机：G = (Q, Σ, Γ, δ, q0, B, F, GL, GR)

• Q - 状态集
• Σ - 输入字母集
• Γ - 带字母 Σ ⊂ Γ
• δ - 转换函数集
• q0 - 初始状态
• B - 空白符号集，B ∈ Γ – Σ
• F - 终结状态集 F ⊂ Q
• GL - 左端标记 GL ∈ Σ
• GR - 右端标记 GR ∈ Σ

Myhill-Nerode 定理的意义是什么？

Myhill-Nerode 定理指出，如果语言L的L~（L~是字符串x和y上的关系，其中x和y没有可区分的扩展）具有有限数量的等价类，并且如果此数量为N，则存在一个识别 L 的最小确定性有限自动机 (DFA)，其中包含N个状态。

除了定义之外，Myhill-Nerode 定理还用于解释哪些语言可以被简单的机器或“有限状态自动机”识别。它有助于理解这些简单的机器可以处理哪些语言，或者可以在机器上进行多少简化以接受这些语言。

自动机和语法的等价性是什么？

等价性表示不同类型的自动机与其可以识别的语法类别之间的关系。根据乔姆斯基的分类，有四种类型的语法。

什么是正则表达式？

乔姆斯基分类中的 3 型语法也被称为正则语法。有限自动机可以通过简单的表达式（称为正则表达式）来接受正则语言。

正则表达式是表示任何语言的最有效方法。这些表达式定义一个字符串并匹配字符组合。字符串搜索算法使用此模式查找字符串上的操作，从而易于检查语言。

正则表达式，用x*表示，表示x的零次或多次出现，而x+表示x的一次或多次出现，生成一系列字符。

(a | b)^*表示任何大小的a和b的所有可能组合。[此处符号“|”表示或]

正则表达式如何与有限自动机相关？

正则表达式是一种被有限自动机接受的语言描述语言，它提供了任何语言的最有效表示，其中Σ表示输入集作为字母表。它可以定义如下 -

• Φ表示空集，
• ε表示空字符串，
• 对于Σ中的每个'a'，都是一个正则表达式，并表示集合'a'。

如果“r”和“s”是分别表示语言 L1 和 L2 的正则表达式，则

• “r + s”与 (L1 ∪ L2) 相同
• rs与L1L2串联相同
• r^*分别等价于L1^*闭包

该图演示了将 RE 轻松转换为具有 epsilon 移动的非确定性有限自动机 (NFA)，然后转换为确定性有限自动机 (DFA)，然后可以轻松地将其转换为 RE。

闭包性质在自动机理论中的重要性是什么？

自动机理论和形式语言中的闭包性质是指在对其成员执行某些操作后，语言类别仍然保持在该类别内。

在正则语言的上下文中，当通过并集或串联等操作执行时，它们具有相同的特征和限制，因此我们可以说正则语言在并集下是封闭的。

正则语言在并集、交集、串联、补集和 Kleene 闭包等运算下是封闭的。相反，确定性 CFL 在补集、与正则语言的交集和逆同态下是封闭的。

什么是非确定性图灵机？

非确定性图灵机 (TM) 对于每个状态和符号都有一组动作，使得转换是非确定性的。TM 的计算是一棵从起始配置开始的配置树。

像 NTM 这样的机器可以在每一步中进行多次转换，例如从输入符号转换到状态 Qi、Qj、Qk 等。NTM“猜测”最终导致接受状态 Qf 的最佳转换，因为每一步中都没有建立良好的转换。这个概念就像一个迷宫，机器总能猜出正确的选择，如果存在一条路，就能找到最快的方法出去。

NTM 是计算机科学家理解计算极限、复杂性理论和有效算法求解类别的宝贵工具。它们在研究 NP（非确定性多项式时间）和 NP 完全问题等复杂性类别中特别有用，使研究人员能够推理那些解决方案可以有效验证但可能难以找到的问题。但是，设计 NTM 在实践中不像 DTM 那样可行。