Lecture Notes: Theory of Computation
COMP4003 Theory of Computation
Dr. Goliath Zhiyuan Li
Lec 2: Math Preliminaries
引言 (Preface)
本讲旨在复习计算理论所需的基础数学知识，其中大部分概念源于离散结构 (Discrete Structures)。理解这些概念并掌握其规范的表述方式至关重要。
常用数学短语 (Common Phrases)
- s.t.: “such that” 的缩写，意为“使得…满足…”。
- w.l.o.g: “without loss of generality” 的缩写，意为“不失一般性”。
- Q.E.D: “quod erat demonstrandum” 的缩写，意为“证毕”，通常在证明结尾用方框
□表示。 - LHS / RHS: 分别指 “left-hand side” 和 “right-hand side”，即等式的左边和右边。
1. 集合 (Sets)
- 定义: 集合是对象的集合，具有无序性和互异性。
- 表示法:
- 枚举法: $\lbrace 0, 1, 2, … \rbrace$
- 描述法: $\lbrace x \mid P(x) \rbrace$ (满足性质 $P(x)$ 的所有 $x$ 的集合)
- 空集 (Empty Set): 不包含任何元素的集合，记为 $\emptyset$ 或 ${}$。
- 全集 (Universal Set): 在特定上下文中包含所有元素的集合，例如：
- $\mathbb{N}$: 自然数集
- $\mathbb{Z}$: 整数集
- $\mathbb{Q}$: 有理数集
- 子集 (Subset): 如果集合 $A$ 中所有元素都在集合 $B$ 中，则 $A$ 是 $B$ 的子集，记为 $A \subseteq B$。
- 幂集 (Power Set): 集合 $A$ 的所有子集构成的集合，记为 $P(A)$。
- 示例: 若 $A = \lbrace 1, 2 \rbrace$，则 $P(A) = \lbrace \emptyset, \lbrace 1 \rbrace, \lbrace 2 \rbrace, \lbrace 1, 2 \rbrace \rbrace$。
- 集合运算 (Set Operators):
- 补集 (Complement): $\bar{A} = \lbrace x \mid x \notin A \rbrace $
- 交集 (Intersection): $A \cap B = \lbrace x \mid x \in A \text{ and } x \in B \rbrace $
- 并集 (Union): $A \cup B = \lbrace x \mid x \in A \text{ or } x \in B \rbrace $
- 差集 (Set Minus): $A \setminus B = \lbrace x \mid x \in A \text{ and } x \notin B \rbrace $
2. 关系 (Relation)
- 笛卡尔积 (Cartesian Product): $A \times B = \lbrace (x, y) \mid x \in A \text{ and } y \in B \rbrace$。
- 关系 (Relation): 笛卡尔积 $A \times B$ 的一个子集 $R$。若 $(x, y) \in R$，则称 $x$ 与 $y$ 有关系 $R$，记为 $xRy$。
- 关系性质 (Properties on a set A):
- 自反性 (Reflexive): $\forall x \in A, xRx$。
- 对称性 (Symmetric): $\forall x, y \in A, xRy \to yRx$。
- 反对称性 (Anti-symmetric): $\forall x, y \in A, (xRy \land yRx) \to x = y$。
- 传递性 (Transitive): $\forall x, y, z \in A, (xRy \land yRz) \to xRz$。
3. 函数 (Function)
- 定义: 函数是一种特殊的关系，对于定义域 (Domain) $A$ 中的每一个元素 $x$，在陪域 (Co-domain) $B$ 中都有且仅有 (uniquely exist) 一个元素 $y$ 与之对应。记为 $f: A \to B$。
- 术语:
- 像 (Image): $y = f(x)$。
- 原像 (Pre-image): $x$ 是 $y$ 的原像。
- 函数类型:
- 单射 (Injection): $\forall x, y \in A, x \neq y \to f(x) \neq f(y)$ (不同的输入对应不同的输出)。
- 满射 (Surjection): $\forall y \in B, \exists x \in A, f(x) = y$ (陪域中所有元素都有原像)。
- 双射 (Bijection): 既是单射又是满射。
4. 形式语言 (Formal Language)
- 字母表 (Alphabet, $\Sigma$): 一个非空有限的符号集合。
- 字符串 (String): 由字母表中符号组成的有限序列。
- 长度 (Length): $|w|$，字符串 $w$ 中符号的个数。
- 空串 (Empty String, $\epsilon$): 长度为 0 的字符串。
- 字符串操作:
- 逆序 (Reverse): $w^R$。例：$(abc)^R = cba$。
- 子串 (Substring): 在 $w$ 中连续出现的字符串。
- 连接 (Concatenation): $wz$。例：
abc和xyz连接后是abcxyz。
- 语言 (Language): 在特定字母表上，所有字符串的一个集合。
5. 证明技巧 (Proof Techniques)
- 构造性证明 (Constructive Proof):
- 用途: 证明存在性命题，如 $\exists x, P(x)$。
- 方法: 直接构造一个满足条件的 $x$，并证明其满足性质 $P(x)$。
- 反证法 (Proof by Contradiction):
- 用途: 证明命题 $p$。
- 方法: 假设 $p$ 为假 (即 $\neg p$ 为真)，然后从此假设出发，推导出一个矛盾。因此，原假设 $\neg p$ 错误，故 $p$ 必为真。
- 数学归纳法 (Induction):
- 用途: 证明关于自然数的全称量词命题，如 $\forall n \in \mathbb{N}, P(n)$。
- 简单归纳法 (Simple Induction):
- 基础步骤 (Base Case): 证明 $P(0)$ 成立。
- 归纳步骤 (Inductive Step): 假设 $P(k)$ 成立 (归纳假设)，证明 $P(k+1)$ 也成立。
- 强归纳法 (Strong Induction):
- 基础步骤 (Base Case): 证明 $P(0)$ 成立。
- 归纳步骤 (Inductive Step): 假设 $P(0), P(1), …, P(k)$ 全部成立，证明 $P(k+1)$ 也成立。
- 对角线法 (Diagonal Argument):
- 由康托尔 (Georg Cantor) 提出，是一种强大的反证法。
- 用途: 常用于证明某个无限集合是不可数 (uncountable) 的。
- 核心思想: 假设该集合是可数的，从而可以将其所有元素一一列出。然后，通过构造一个新元素，该元素与列表中的第 $n$ 个元素在第 $n$ 个位置上均不相同。这个新元素必然存在于集合中，但又不在我们列出的“完整”列表中，从而产生矛盾。
- 对角论证法 - 维基百科
6. 集合的基数 (Cardinality of Sets)
- 基数 (Cardinality): 集合中元素的数量，记为 $|A|$。
- 等势: 如果两个集合 $A$ 和 $B$ 之间存在一个双射 (bijection) 函数，则称它们基数相同，或等势。
- 可数集 (Countable Set): 有限集，或基数与自然数集 $\mathbb{N}$ 相同的集合。$|\mathbb{N}|$ 的基数记为 $\aleph_0$ (aleph-zero)。
- 不可数集 (Uncountable Set): 基数比 $\aleph_0$ 更大的无限集。例如，$(0, 1)$ 区间内的实数集是不可数的，其基数为 $\aleph_1$。
- 连续统假设 (Continuum Hypothesis, CH): 不存在基数严格介于 $\aleph_0$ 和 $\aleph_1$ ($|\mathbb{R}|$) 之间的集合。该假设在 ZFC 公理体系下是不可证明的。
Lec 3: Finite Automata
1. 有限自动机简介 (A Simple Model)
本课程从最简单的计算模型——有限自动机 (Finite Automata) 开始。
- 特点:
- 计算能力相对较弱。
- 核心限制是它只能使用有限的 (finite) 内存。
- 应用: 尽管简单，但在某些领域非常有用。
示例：Goliath 批改试卷
- 状态 (States): Goliath 的心情有三种：开心 🙂, 平静 😐, 不开心 😠。
- 输入 (Inputs): 试卷的等级有三种：A, B, C。
- 转移规则 (Transitions): 无论当前心情如何：
- 看到 ‘A’，心情变为 🙂。
- 看到 ‘B’，心情变为 😐。
- 看到 ‘C’，心情变为 😠。
这个过程可以用一个状态转移图来表示。
示例：游戏角色动画
- 状态 (States): 待机 (idle), 准备 (standing by), 攻击 (attacks), 胜利 (winning)。
- 输入 (Inputs): 玩家的键盘操作（如无输入, 按住 “E”, 按 “A” 等）。
- 转移规则: 角色根据玩家的输入在不同动画状态之间切换。
2. 形式化定义 (Formalization)
一个确定性有限自动机 (Deterministic Finite Automaton, DFA) 由以下五个部分组成。
定义: 一个 DFA 是一个五元组 $(Q, \Sigma, \delta, q_0, F)$，其中：
- $Q$: 一个有限的状态集合 (a finite set of states)。
- $\Sigma$: 一个有限的字母表，包含所有可能的输入符号 (a finite set, called the alphabet)。
- $\delta$: **转移函数 (transition function)**，其定义为 $\delta: Q \times \Sigma \to Q$。它接收当前状态和当前输入符号，并输出下一个状态。
- $q_0 \in Q$: **起始状态 (start state)**，机器从这个状态开始运行。
- $F \subseteq Q$: 接受状态 (accept states) 或 终结状态 (final states) 的集合。
转移函数的表示:
- 转移表 (Transition Table): 一个 $|Q| \times |\Sigma|$ 的表格，每个单元格内容是下一个状态。
- 状态图 (State Graph):
- 每个状态是一个圆圈。
- 每个转移是一条从当前状态指向下一个状态的有向边，边的标签是触发该转移的输入符号。
- 起始状态有一个指向它的箭头。
- 接受状态是双层圆圈。
示例：一个抽象的 DFA
- $M_1 = (\lbrace q_0, q_1 \rbrace, \lbrace 0, 1 \rbrace, \delta, q_0, \lbrace q_1 \rbrace)$
- 转移函数 $\delta$ 如下：
0 1 $q_0$ $q_0$ $q_1$ $q_1$ $q_0$ $q_1$ - 状态图：
3. DFA 的计算过程 (Computation)
- 输入: DFA 的输入是一个定义在字母表 $\Sigma$ 上的字符串 $w = w_1w_2\dots w_n$。
- 输出: 接受 (accept) 或 **拒绝 (reject)**。
- 过程:
- 从起始状态 $q_0$ 开始。
- 依次读取字符串 $w$ 中的每一个符号 $w_i$。
- 每读取一个符号，就根据转移函数 $\delta$ 从当前状态转移到下一个状态。
- 接受条件: 如果读取完整个字符串后，机器停在了一个接受状态 (即最终状态 $\in F$)，那么该字符串被 接受。否则，被 拒绝。
- 形式化地，一个字符串 $w=w_1w_2\dots w_n$ 被接受，当且仅当 $\delta(\dots\delta(\delta(q_0, w_1), w_2)\dots, w_n) \in F$。
核心定义
- 机器的语言 (Language of a Machine):
- 一个机器 $M$ 所能接受的所有字符串的集合，称为机器 $M$ 的语言，记为 $L(M)$。
- $L(M) = \lbrace w \mid M \text{ accepts } w \rbrace$
- 识别 (Recognize):
- 我们称机器 $M$ 识别语言 $A$，如果 $A = L(M)$。
- 正则语言 (Regular Language):
- 如果一个语言可以被某个 DFA 识别，那么这个语言就是正则语言。
4. DFA 设计 (DFA Design)
设计 DFA 类似于设计算法，关键在于想清楚在处理输入字符串时，需要“记住”哪些信息。这些需要记忆的信息就构成了自动机的状态。
设计示例
- 语言: $A = \lbrace w \mid w \text{ 包含偶数个 1} \rbrace$，其中 $\Sigma = \brace 0, 1 \rbrace$。
- 设计思路:
- 在从左到右读取字符串时，我们唯一需要记住的信息是：到目前为止，我们已经看到的 ‘1’ 的数量是奇数还是偶数。
- 这提示我们需要两个状态：
- $q_{even}$: 已看到偶数个 ‘1’。
- $q_{odd}$: 已看到奇数个 ‘1’。
- 具体设计:
- 状态集 $Q$: ${q_{even}, q_{odd}}$
- 字母表 $\Sigma$: ${0, 1}$
- 起始状态 $q_0$: $q_{even}$ (因为在开始时，’1’ 的数量为 0，是偶数)。
- 接受状态 $F$: ${q_{even}}$ (因为语言要求 ‘1’ 的总数是偶数)。
- 转移函数 $\delta$:
- $\delta(q_{even}, 0) = q_{even}$ (读 ‘0’ 不改变 ‘1’ 的奇偶性)
- $\delta(q_{even}, 1) = q_{odd}$ (读 ‘1’ 后，偶数变为奇数)
- $\delta(q_{odd}, 0) = q_{odd}$ (读 ‘0’ 不改变 ‘1’ 的奇偶性)
- $\delta(q_{odd}, 1) = q_{even}$ (读 ‘1’ 后，奇数变为偶数)
Lec 4: NFA
1. 动机 (Motivation)
在设计自动机时，我们有时会遇到用 DFA 难以直观表达，但用一种更灵活的模型却很简单的情况。
- 示例语言: $A = \lbrace w \mid w \text{ 的1的个数是奇数，或者 w 以1结尾} \rbrace$
- 这个语言可以被下面这个机器识别，其设计思路非常清晰：
- 一条路径（$q_0 \to q_1$）负责检查“1的个数是奇数”。
- 另一条路径（$q_0 \to q_2$）负责检查“以1结尾”。
- 问题: 上图所示的机器不是一个 DFA。因为它在状态 $q_0$ 接收到输入
1时，下一个状态可以是 $q_1$，也可以是 $q_2$。这种不确定性就是 NFA 的核心特征。
2. NFA 的形式化定义 (NFA Definition)
为了描述这种具有不确定性的计算模型，我们引入**非确定性有限自动机 (Nondeterministic Finite Automaton, NFA)**。
定义: 一个 NFA 是一个五元组 $(Q, \Sigma, \delta, q_0, F)$，其中：
- $Q$: 有限的状态集合。
- $\Sigma$: 有限的字母表。
- $\delta$: **转移函数 (transition function)**，其定义为 $\delta: Q \times \Sigma \to P(Q)$。
- $q_0 \in Q$: 起始状态。
- $F \subseteq Q$: 接受状态集合。
NFA 与 DFA 的核心区别:
- DFA 的转移函数 $\delta: Q \times \Sigma \to Q$，对于一个给定的当前状态和输入，其下一个状态是唯一确定的。
- NFA 的转移函数 $\delta: Q \times \Sigma \to P(Q)$，其返回的是一个状态的集合（$P(Q)$ 是 $Q$ 的幂集）。这意味着，对于一个给定的当前状态和输入，下一个状态可能是零个、一个或多个。
3. NFA 的计算与 $\epsilon$-转移
- NFA 的接受条件:
- 一个字符串 $w$ 被 NFA 接受，当且仅当在读取完整个字符串后，存在至少一条计算路径，能够使得机器最终停在一个接受状态。
- 即使某些路径会失败（停在非接受状态），只要有一条路径成功，该字符串就被接受。
- $\epsilon$-转移 ($\epsilon$-Move):
- 我们可以进一步扩展 NFA，允许它在不消耗任何输入符号的情况下进行状态转移，这种特殊的转移称为 $\epsilon$-转移。
- 对于带有 $\epsilon$-转移的 NFA，其转移函数定义变为：
$\delta: Q \times (\Sigma \cup {\epsilon}) \to P(Q)$ - $\epsilon$-转移使得 NFA 的构造（尤其是在进行语言的运算时）变得更加优雅和方便。
示例
- 考虑以下带有 $\epsilon$-转移的 NFA，它识别的语言是什么？
- 分析:
- 机器可以从 $q_0$ 不消耗任何输入（通过 $\epsilon$ 边）直接跳转到 $q_2$。
- 要被接受，机器必须停在 $q_1$。
- 为了到达 $q_1$，必须从 $q_0$ 接收一个输入
1。 - 因此，任何被接受的字符串都必须包含至少一个
1。在接收到第一个1并到达 $q_1$ 后，可以再接收任意数量的0。在此之前，机器可以在 $q_0$ 和 $q_2$ 之间任意转移。
4. 等价性 (Equivalence)
我们现在有三种计算模型：DFA, NFA, NFA with $\epsilon$-moves (NFA-$\epsilon$) 。一个自然的问题是：它们中哪一个的计算能力更强？
- 计算能力 (Power):
- 如果两个计算模型能够识别的语言集合完全相同，则称它们计算能力等价。
- 如果模型 M1 能识别一个语言，而模型 M2 不能，则 M1 比 M2 更强大。
- 核心定理: DFA, NFA, 和 NFA-$\epsilon$ 的计算能力是等价的。
- 这意味着，任何一个 NFA（或 NFA-$\epsilon$）能够识别的语言，都存在一个 DFA 也能识别它。它们都识别同一类语言，即正则语言。
- 证明思路:
- 显然，DFA 是 NFA 的一个特例，NFA 是 NFA-$\epsilon$ 的一个特例。所以 DFA $\le_{pow}$ NFA $\le_{pow}$ NFA-$\epsilon$。
- 证明的关键在于证明 NFA-$\epsilon$ $\le_{pow}$ DFA，即证明对于任意给定的 NFA-$\epsilon$，我们都可以构造出一个与之等价的 DFA。
- 从 NFA 到 DFA 的转换算法 (子集构造法 Subset Construction):
- 核心思想: DFA 的每一个状态对应 NFA 的一个状态集合。
- $\epsilon$-闭包 (ε-closure): 对于一个状态 $q$，其 $\epsilon$-闭包 $E(q)$ 是指从 $q$ 开始，仅通过 $\epsilon$-转移所能到达的所有状态的集合（包括 $q$ 自身）。
- 构造步骤:
- DFA 的起始状态: NFA 起始状态的 $\epsilon$-闭包，即 $q’_0 = E(q_0)$。
- DFA 的状态转移: 对于 DFA 的一个状态 $R$ (它是一个 NFA 的状态集) 和一个输入符号 $a \in \Sigma$，其下一个状态 $\delta’(R, a)$ 是这样计算的：
a. 找到从 $R$ 中的任意状态出发，经过一条 $a$ 边能到达的所有 NFA 状态的集合。
b. 计算这个新集合的 $\epsilon$-闭包。 - 重复步骤2，直到没有新的 DFA 状态产生。
- DFA 的接受状态: DFA 的任何一个状态 $R$，如果它包含了至少一个 NFA 的接受状态 ($R \cap F \neq \emptyset$)，那么 $R$ 就是一个 DFA 的接受状态。
- 这个算法保证了我们可以为任何 NFA 找到一个等价的 DFA，从而证明了它们计算能力的等价性。
Lecture Notes: Theory of Computation
https://tosakaucw.github.io/lecture-notes-theory-of-computation/