Automata Theory 简明教程

本教程旨在为攻读任何信息技术或计算机科学相关专业的学生准备。它旨在帮助学生掌握自动机理论中的重要概念。

本教程很好地平衡了理论和数学严谨性。读者应具备离散数学结构的基本理解。

在数学和计算机科学中， * automata theory* 涉及抽象机器和计算问题。自动机是遵循预定操作自动执行的自推进计算设备。

约翰·冯·诺伊曼说：“自动机理论是一门逻辑理论，它涉及自动机和信息的学习，强调需要一个详细的、数学的和分析性的理论来理解复杂的自动机。”

自动机是一个有限尺寸的设备，具有指定的输入和输出，其行为由输入决定。换句话说，自动机是指根据预先确定的指令或过程转换信息的自操作机械对象。

自动机还可以指一类机电设备，既有理论上也有实际上的，它们在运动后转换信息。

自动机可分类如下：

A * finite-state machine (FSM)* 是一个数学计算模型，它在任何给定时间都能处于有限数量的状态之一。它可以根据输入（称为 transition ）从一个状态转换为另一个状态。

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

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

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

图灵机由无限胶带、磁带头和状态转换表组成。它们对位串执行，磁带头处于特定状态，表控制其行为。

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

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

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

$\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 语言可以进入语言字符串的最终状态，也可能不会进入非语言字符串的拒绝状态。TM 可以永远循环非语言字符串，使其成为图灵可识别的语言。

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

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

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

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

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

它被表示为 G(V, N, P, S) 。它生成整个字母上的语法正确的字符串，主要用于语法分析阶段，尤其是在编译过程中，在编译阶段。

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

语法是一组用于生成语言字符串的产生规则。 * Grammars* 不过是符号、产生规则和起始符号的集合，通过四元组 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 ”，这是一种语言。

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

终止问题是可计算性理论中的一个决策问题，用于确定计算机程序将终止还是永久运行。

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

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

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

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

难以处理的问题在理论上是可以解决的，但实际上无法解决。 P 包含自然问题，比如计算最大公约数，以及寻找最大匹配，确定一个数是否是质数也是 P 的一部分。

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

在计算理论中，问题 X 可以称为 NP-Hard，如果存在一个现有的 NP-Complete 问题 Y 可以在多项式时间内简化为 X 。

NP-Hard 问题的难度等级与 NP-Complete 问题相同。然而，NP-Hard 问题不一定属于 NP 类。一个问题只有在属于 NP-Hard 和 NP 问题的情况下才能成为 NP-Complete。

在自动机理论的语境中，有一些表格包括状态、输入符号、初始状态、终态集合和转移函数。

(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 。

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

这是一个状态图示例：

这里我们有四个状态：

并且，

\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 ∈ Γ

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

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

状态、输入元素和栈中的顶部符号确定每一步的下一步（过渡）。过渡步骤包括进行状态更改、从输入带读取符号、移至右侧的下一个符号以及修改栈。

图灵机是一种与数字计算机等效的数学工具（图灵，1930 年代）。它由机器计算的输入输出关系组成，输入以二进制形式给定在机器的磁带上。输出由机器停止时的磁带内容组成。磁带的内容由图灵机内部的有限状态机 (FSM) 确定

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

看看以下通用图灵机的概念图 −

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

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

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

对于不同类别形式语言，这些规则已发生变化，如常规、上下文无关、上下文相关和递归可枚举。

解析器可以自顶向下或自底向上，从顶端开始使用起始符号，使用解析树来推导字符串。

一个确定性线性有界自动机是上下文相关的，并且一个线性有界自动机具有一个空 * language is undecidable* 。

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

LBA 的确定性版本是否拥有与非确定性版本同样的能力这一点未知。

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

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

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

乔姆斯基分类中的 3 型语法也称作正则语法。有限自动机可以通过简单表达式接受正则语言，这种表达式称为 * Regular Expressions*

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

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

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

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

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

该图展示了使用 epsilon 移动轻松转换正则表达式到 * Non-deterministic Finite Automata (NFA)* 的过程，然后转换为确定性有限自动机 (DFA)，后者可以轻松转换为正则表达式。

自动机理论和形式语言中的 * closure property* 指成员进行某些操作后仍保留在该类别中的语言类别。

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

正则语言在并集、交集、连接、补集和 Kleene 闭包等操作下是闭合的。相比之下，确定性上下文无关语言在补集、与正则语言的交集和逆同态下是闭合的。

非确定性图灵机 ™ 为每个状态和符号设置了一组动作，使转换变得非确定性。TM 的计算是从开始配置开始的配置树。

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

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