Automata Theory
在介绍自动机前，我们需要知道一下计算理论中三个非常核心的概念：Machine (机器)、Language (语言) 和 Syntax (语法)。 在计算理论中，这三个概念是紧密相连的，它们共同构成了我们理解计算能力、复杂性和极限的基础。
Machine (机器)
在计算理论中，“机器”（Machine）通常不指我们日常生活中看到的实体计算机，而是一个抽象的、数学化的计算模型。它是一个精确定义了的系统，能够遵循一系列预设的规则来执行计算。
这些模型帮助我们以一种严谨的方式来分析和推理“计算”这个过程本身。它们去除了所有物理实现的细节（如电子元件、速度等），只关注其核心的计算能力。
核心思想： 一个机器模型定义了什么是“可以被计算的”。
主要例子：
- 有限自动机 (Finite Automaton, FA)： 这是最简单的计算模型。它只有有限的内存（通过其“状态”来体现）。它非常适合用于识别简单的模式，例如文本搜索中的正则表达式。它能“记住”的信息非常有限。
- 下推自动机 (Pushdown Automaton, PDA)： 这是比有限自动机更强大的模型。它除了有有限的状态外，还有一个额外的、无限容量的“栈”（Stack）作为内存。这个栈的特性是“后进先出”(Last-In, First-Out)。这种机器能够识别比有限自动机更复杂的语言，例如编程语言中嵌套的括号结构。
- 图灵机 (Turing Machine, TM)： 这是计算理论中最为强大和重要的模型，由艾伦·图灵提出。它可以被看作是现代计算机的理论原型。它包含一个无限长的纸带（作为无限内存），一个读写头可以在纸带上移动和修改符号，以及一组有限的规则。图灵机被认为是所有“可计算”问题的上限，任何能被今天的计算机解决的问题，都能被图灵机解决。这就是著名的丘奇-图灵论题 (Church-Turing Thesis)。
总结： “机器”是一个形式化的计算模型，用来定义和研究不同层次的计算能力。
Language (语言)
在计算理论中，“语言”（Language）同样不是指我们日常交流的自然语言（如中文、英文），而是一个形式语言 (Formal Language)。
一个形式语言被精确地定义为一个字符串 (strings) 的集合。这些字符串都是由某个预先指定的字母表 (alphabet) 中的符号构成的。
- 字母表 (\(\Sigma\))： 一个有限的、非空的符号集合。例如，二进制字母表 \(\Sigma = \{0, 1\}\)；英文字母表 \(\Sigma = \{a, b, c, ..., z\}\)。
- 字符串 (String)： 由字母表中的符号组成的有限序列。例如，如果字母表是 \(\Sigma = \{0, 1\}\)，那么 “0110”, “1”, “000” 都是这个字母表上的字符串。空字符串（用 \(\epsilon\) 或 \(\lambda\) 表示）也是一个字符串。
- 语言 (Language)： 在某个字母表 \(\Sigma\) 上所有可能字符串的集合（记作 \(\Sigma^*\)) 中，取出的一个子集。
核心思想： 一个“语言”定义了一个“问题”。判断一个给定的字符串是否属于某个语言，就等价于回答一个“是/否”问题。
例子：
- 设字母表为 \(\Sigma = \{a, b\}\)。
- 语言 L1： 所有以 ‘a’ 开头的字符串的集合。例如，“a”, “ab”, “abaa” 都属于 L1，但 “b”, “ba” 不属于。
- 语言 L2： 所有包含偶数个 ‘a’ 的字符串的集合。例如，“bb”, “aab”, “bab” 属于 L2，但 “a”, “abb”, “aaab” 不属于。
- 语言 L3 (一个更复杂的例子)： 所有形式为 \(a^n b^n\) 的字符串的集合，其中 \(n \ge 0\)。这意味着 ‘a’ 的数量必须和 ‘b’ 的数量相等，且所有的 ‘a’ 都在 ‘b’ 的前面。例如，“” (空字符串, n=0), “ab”, “aabb”, “aaabbb” 属于 L3，但 “aab”, “abba” 不属于。
Syntax (语法)
语法 (Syntax) 是一套规则，它精确地定义了一个语言中哪些字符串是“合法的”或“格式正确的”。换句话说，语法是用来生成或识别一个语言中所有字符串的规则集合。
核心思想： 语法是语言的“蓝图”或“基因”，它描述了语言的结构。
表示方式：
- 正则表达式 (Regular Expressions)： 这是描述最简单一类语言（正则语言）的语法。例如，正则表达式
a*b定义了一个语言，该语言包含任意数量的 ‘a’（包括零个）后面跟着一个 ‘b’。字符串 “b”, “ab”, “aab” 都符合这个语法。 - 上下文无关文法 (Context-Free Grammar, CFG)： 这是更强大的语法表示方法，通常用来定义编程语言的结构。它使用一组产生式规则 (production rules) 来生成语言中的字符串。例如，前面提到的语言 L3 (\(a^n b^n\)) 可以用以下CFG来定义： \(S \to aSb \mid \epsilon\) 这个规则的意思是：一个合法的字符串S，要么是 ‘a’ 加上一个合法的S 再加上 ‘b’，要么是空字符串。通过这个规则，我们可以生成 “ab”, “aabb” 等所有L3中的字符串。
三者之间的关系：乔姆斯基谱系
计算理论中最核心的连接就是：一个特定类型的“机器”恰好能识别由特定类型“语法”所定义的“语言”。
这个优美的对应关系被称为乔姆斯基谱系 (Chomsky Hierarchy)：
| 语言类型 (Language) | 语法规则 (Syntax) | 识别机器 (Machine) |
|---|---|---|
| 正则语言 (Regular) | 正则表达式 / 正则文法 | 有限自动机 (FA) |
| 上下文无关语言 (Context-Free) | 上下文无关文法 (CFG) | 下推自动机 (PDA) |
| 上下文相关语言 (Context-Sensitive) | 上下文相关文法 (CSG) | 线性有界自动机 (LBA) |
| 递归可枚举语言 (Recursively Enumerable) | 无限制文法 (Unrestricted) | 图灵机 (Turing Machine) |
简单来说，它们的关系是：
我们使用 语法 (Syntax) 来精确地 描述 一个 语言 (Language)，而这个语言可以被一个相应计算能力的 机器 (Machine) 来 识别 或 接受。
例如，一个正则表达式（语法）定义了一个正则语言，而这个语言中的所有字符串，也只有这些字符串，能够被一个有限自动机（机器）所接受。如果你想识别一个需要记忆配对括号的语言（如 \(a^n b^n\)），那么有限自动机就不够用了，你需要一台更强大的机器——下推自动机，而这个语言也需要一个更复杂的语法——上下文无关文法来描述。