计算理论导论

可计算理论

有限自动机

DFA

DFA（Deterministic Finite Automaton）是一种有限状态自动机，其中每个状态对于每个输入符号都有且仅有一个转移。DFA可以用来识别正则语言。

定义： DFA由一个五元组$(Q, \Sigma, \delta, q_0, F)$组成，其中：

• $Q$是状态集合
• $\Sigma$是输入符号集合
• $\delta$是转移函数，定义为$\delta: Q \times \Sigma \rightarrow Q$
• $q_0$是初始状态
• $F$是接受状态集合

接受： 一个字符串被DFA接受，如果从初始状态出发，按照输入符号进行状态转移，最终停在一个接受状态。

语言： 语言是所有被自动机接受的字符串集合。我们称DFA“识别”语言$L$，如果$L$是DFA接受的字符串集合。

注：

• 空字符串$\epsilon$也可以被DFA接受，取决于初始状态是否为接受状态。
• 空语言$\emptyset$表示没有任何字符串被接受。注意，空字符串不属于空语言，因为空语言没有任何字符串。、

语言的交集： 两个语言的交集是同时被两个自动机接受的字符串集合。对于两个DFA $M_1$和$M_2$，我们可以构造一个新的DFA $M$，使得$L(M) = L(M_1) \cap L(M_2)$。我们给出一个显式的构造：

• 状态集合：$Q = Q_1 \times Q_2$，其中$Q_1$和$Q_2$分别是$M_1$和$M_2$的状态集合。
• 输入符号集合：$\Sigma$，与$M_1$和$M_2$相同。
• 转移函数：$\delta((q_1, q_2), a) = (\delta_1(q_1, a), \delta_2(q_2, a))$，其中$\delta_1$和$\delta_2$分别是$M_1$和$M_2$的转移函数。
• 初始状态：$q_0 = (q_{0,1}, q_{0,2})$，其中$q_{0,1}$和$q_{0,2}$分别是$M_1$和$M_2$的初始状态。
• 接受状态集合：$F = F_1 \times F_2$，其中$F_1$和$F_2$分别是$M_1$和$M_2$的接受状态集合。

状态示意图往往类似于一个网格，其中每个状态$(q_1, q_2)$表示$M_1$处于状态$q_1$，$M_2$处于状态$q_2$。

正则语言： 正则语言是可以被DFA识别的语言。正则语言也可以通过正则表达式来描述。

正则语言的定义非常简单，但是判定一个语言是否为正则语言却是一个复杂的问题。我们可以使用泵引理（Pumping Lemma）来证明某些语言不是正则语言。我们 将在后续章节中介绍泵引理。

NFA

NFA（Nondeterministic Finite Automaton）是一种非确定性有限自动机，其中每个状态对于每个输入符号可以有多个转移。NFA也可以用来识别正则语言。

NFA与DFA的区别在于，NFA允许多个转移，而DFA每个状态对于每个输入符号只能有一个转移。尽管NFA看起来更强大，但实际上它们与DFA等价，即它们识别相同的语言。我们可以想象，NFA在无限的线程上并行地处理输入字符串，而DFA则在单线程上处理输入字符串（不准确）。

定理： 任何NFA等价于一个DFA，即对于每个NFA $N$，存在一个DFA$M$使得$L(M) = L(N)$。

这一点的证明略去。

我们下面陈述三个定理：

• 正则语言关于并运算闭合。
• 正则语言关于连接运算闭合。
• 正则语言关于星闭包运算闭合。

我们分别构造对应的DFA或者NFA来证明这些定理：

正则表达式

正则表达式是一种描述正则语言的工具。它使用特定的符号和规则来构建字符串集合。正则表达式可以转换为DFA或NFA，从而识别相同的语言。我们使用归纳定义：

定义：

基础：$\emptyset$, $\epsilon$, $a \in \Sigma$是正则表达式。

递归：如果$R_1$和$R_2$是正则表达式，那么以下也是正则表达式：

• $R_1 \cup R_2$
• $R_1 \circ R_2$
• $R^*$

下面证明所有的正则表达式都等价于为DFA：

定理： 对于每个正则表达式$R$，存在一个DFA $M$ 使得$L(M) = L(R)$。

证明：

我们通过对正则表达式的结构进行归纳证明。对于每个正则表达式$R$，我们构造一个等价的NFA $N$，然后利用NFA与DFA的等价性得到DFA。

基础情况：

1. $R = \emptyset$：构造NFA $N = (\{q_0\}, \Sigma, \delta, q_0, \emptyset)$，不接受任何字符串。

2. $R = \epsilon$：构造NFA $N = (\{q_0\}, \Sigma, \delta, q_0, \{q_0\})$，其中$\delta$为空函数，只接受空字符串。

3. $R = a$（$a \in \Sigma$）：构造NFA $N = (\{q_0, q_1\}, \Sigma, \delta, q_0, \{q_1\})$，其中$\delta(q_0, a) = \{q_1\}$。

归纳步骤：

假设$R_1$和$R_2$分别对应NFA $N_1$和$N_2$。

1. 并运算 $R_1 \cup R_2$：

   • 新建初始状态$q_{new}$
   • 添加$\epsilon$转移到$N_1$和$N_2$的初始状态
   • 接受状态为$N_1$和$N_2$接受状态的并集

2. 连接运算 $R_1 \circ R_2$：

   • 将$N_1$的每个接受状态通过$\epsilon$转移连接到$N_2$的初始状态
   • $N_1$的接受状态变为非接受状态
   • 接受状态为$N_2$的接受状态

3. 星闭包 $R_1^*$：

   • 新建初始状态$q_{new}$作为接受状态
   • 添加$\epsilon$转移到原NFA的初始状态
   • 将原NFA的接受状态通过$\epsilon$转移连接到原初始状态（形成循环）
   • 保留原接受状态

通过上述构造，每个正则表达式都可以转换为等价的NFA，进而转换为DFA。证毕。

反向证明：对于每个DFA，我们首先构造其对应的GNFA。然后，对于任何一个状态$q_{delete}$，指向它的状态为$q_i$，它指向下一个状态$q_j$，其正则表达式分别为$R_1(i向d), R_2(d向i), R_3(d向j), R_4(j向d), R_5(i向j)$，$q_i$，指向自己的表达式为$R_i$，$q_{delete}$指向自己的正则表达式为$R_{delete}$。那么，$q_i$指向自己的箭头为$R_i \cup R_1R_{delete}R_2$，指向$q_j$的箭头就是$R_5 \cup R_1R_{delete}^*R_3$，以此类推，我们就可以归纳消除到只有两个状态，这个箭头上的正则表达式就是DFA等价的正则表达式。

泵引理（Pumping Lemma）

泵引理是证明某个语言不是正则语言的重要工具。

泵引理（正则语言）：设$L$是一个正则语言，则存在一个泵长度$p > 0$，使得对于任何长度不小于$p$的字符串$s \in L$，都可以被分解为$s = xyz$，满足：

1. $|xy| \leq p$
2. $|y| > 0$
3. 对于所有$i \geq 0$，有$xy^iz \in L$

直观理解：如果DFA有$p$个状态，那么任何长度超过$p$的字符串在DFA中运行时必然会重复经过某个状态。$y$就是两次经过该状态之间的子串，可以”泵”（重复）任意次数。

证明思路：设DFA有$p$个状态，考虑长度为$n \geq p$的字符串。根据鸽巢原理，前$p+1$个状态（包括初始状态）中必有重复，设$q_i = q_j$（$i < j \leq p$），则$x = s[0..i-1]$，$y = s[i..j-1]$，$z = s[j..n-1]$。

应用示例：证明$L = \{0^n1^n \mid n \geq 0\}$不是正则语言。

证明：假设$L$是正则语言，设泵长度为$p$。考虑字符串$s = 0^p1^p \in L$。根据泵引理，$s = xyz$，其中$|xy| \leq p$，因此$y$只包含0。设$y = 0^k$（$k > 0$），则$xy^2z = 0^{p+k}1^p \notin L$（0和1数量不等），矛盾！因此$L$不是正则语言。

上下文无关语言

上下文无关语言（Context-Free Language, CFL）是比正则语言更丰富的语言类，可以用上下文无关文法（CFG）描述，也可以用下推自动机（PDA）识别。

上下文无关语法（CFG）

定义：上下文无关文法是一个四元组$G = (V, \Sigma, R, S)$，其中：

• $V$：变量（非终结符）的有限集合
• $\Sigma$：终结符的有限集合（与$V$不相交）
• $R$：产生式规则集合，每条规则形如$A \rightarrow w$，其中$A \in V$，$w \in (V \cup \Sigma)^*$
• $S \in V$：起始变量

派生：如果存在产生式$A \rightarrow w$，则字符串$uAv$可以一步派生为$uwv$，记作$uAv \Rightarrow uwv$。

语言：$L(G) = \{w \in \Sigma^* \mid S \stackrel{*}{\Rightarrow} w\}$，即从起始变量可以派生出的所有终结符串的集合。

示例：

• 文法$S \rightarrow 0S1 \mid \epsilon$生成语言$L = \{0^n1^n \mid n \geq 0\}$
• 文法$S \rightarrow SS \mid (S) \mid \epsilon$生成平衡的括号串

歧义性：

• 如果存在字符串$w \in L(G)$有多个不同的最左派生（或语法树），则称$G$是歧义的
• 某些语言是固有歧义的（所有生成它的CFG都是歧义的）

Chomsky范式（CNF）： 每个CFG都可以转换为等价的Chomsky范式，其中所有产生式形如：

• $A \rightarrow BC$（两个变量）
• $A \rightarrow a$（单个终结符）
• $S \rightarrow \epsilon$（仅起始变量）

下推自动机（PDA）

PDA是在DFA基础上增加了一个栈（Stack）结构的自动机，可以识别上下文无关语言。

定义：PDA是一个六元组$P = (Q, \Sigma, \Gamma, \delta, q_0, F)$，其中：

• $Q$：状态集合
• $\Sigma$：输入字母表
• $\Gamma$：栈字母表
• $\delta$：转移函数，$\delta: Q \times \Sigma_\epsilon \times \Gamma_\epsilon \rightarrow \mathcal{P}(Q \times \Gamma_\epsilon)$
• $q_0$：初始状态
• $F$：接受状态集合

转移的含义：$\delta(q, a, x) = \{(p_1, y_1), (p_2, y_2), \ldots\}$表示在状态$q$，读入输入$a$（可以是$\epsilon$），栈顶为$x$（可以是$\epsilon$）时，可以转移到状态$p_i$，并将栈顶$x$替换为$y_i$（弹出$x$，压入$y_i$的字符）。

接受方式：

1. 终态接受：读完输入后停在接受状态
2. 空栈接受：读完输入后栈为空

这两种接受方式是等价的。

示例：识别$\{0^n1^n \mid n \geq 0\}$的PDA：

• 读0时压栈
• 读1时弹栈（检查栈顶是否为0）
• 接受当且仅当输入读完且栈为空

上下文无关语言与PDA等价性

定理：一个语言是上下文无关的，当且仅当存在某个PDA识别它。

CFG → PDA： 给定CFG $G = (V, \Sigma, R, S)$，构造PDA $P$：

1. 将$S$压入栈
2. 如果栈顶是变量$A$，非确定性地选择一条产生式$A \rightarrow w$，将$A$替换为$w$
3. 如果栈顶是终结符$a$，读入输入并匹配
4. 如果栈为空且输入读完，接受

PDA → CFG： 构造较复杂，核心思想是创建变量$A_{pq}$表示从状态$p$到状态$q$且栈底不变（即开始时栈为空，结束时栈也为空）的派生。

首先对PDA进行简化：

1. 引入新的唯一接受状态$q_{accept}$；
2. 确保接受时栈为空（通过添加状态逐个弹出栈中符号）；
3. 确保每次转移要么压入一个符号，要么弹出一个符号（不压不弹的转移可拆成两步）。

设简化后的PDA为$P = (Q, \Sigma, \Gamma, \delta, q_0, \{q_{accept}\})$，构造CFG $G = (V, \Sigma, R, S)$：

• 变量集合：$V = \{A_{pq} \mid p, q \in Q\}$
• 起始变量：$S = A_{q_0 q_{accept}}$
• 产生式规则$R$如下表所示：

直观解释：

• 情况a) 表示：从$p$到$q$且栈底不变的最短派生，可能先读入$a$并在空栈上压入符号$t$进入状态$r$，然后从$r$到$s$保持栈底$t$不变，最后从$s$读入$b$并弹出$t$进入$q$。
• 情况b) 表示：从$p$到$q$的派生可以拆分为两段，先经过某个中间状态$r$。
• 情况c) 表示：不移动即可保持栈底不变，对应空串$\epsilon$。

CFG的泵引理

泵引理（上下文无关语言）：设$L$是上下文无关语言，则存在一个泵长度$p > 0$，使得对于任何长度不小于$p$的字符串$s \in L$，都可以被分解为$s = uvxyz$，满足：

1. $|vxy| \leq p$
2. $|vy| > 0$
3. 对于所有$i \geq 0$，有$uv^ixy^iz \in L$

直观理解：在足够长的派生中，某个变量会重复出现（在语法树的同一条路径上），形成可泵的部分。

应用示例：证明$L = \{a^nb^nc^n \mid n \geq 0\}$不是上下文无关的。

证明：假设$L$是CFL，设泵长度为$p$。考虑$s = a^pb^pc^p$。根据泵引理，$s = uvxyz$，其中$|vxy| \leq p$，因此$vxy$不能同时包含$a$、$b$、$c$三种字符（因为最多跨越两种字符的边界）。 pumping后，三种字符的数量将不再相等，矛盾！

Ogden引理：泵引理的强化版本，可以选择某些位置作为”标记”，确保泵的部分包含标记。

上下文无关语言的封闭性

可判定性问题

图灵机

图灵机（Turing Machine, TM）是计算理论中最强大的计算模型，由Alan Turing于1936年提出。它定义了”可计算”的直观概念。

定义

定义：图灵机是一个七元组$M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$，其中：

• $Q$：状态的有限集合
• $\Sigma$：输入字母表（不包括空白符$\sqcup$）
• $\Gamma$：带字母表，$\Sigma \subset \Gamma$且$\sqcup \in \Gamma$
• $\delta$：转移函数，$\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$（确定性TM）
• $q_0 \in Q$：初始状态
• $q_{accept} \in Q$：接受状态
• $q_{reject} \in Q$：拒绝状态（$q_{reject} \neq q_{accept}$）

工作方式：

1. 输入写在无限长的纸带上（两端无限或单向无限）
2. 读写头初始位于输入最左端
3. 根据当前状态和读到的符号，按照$\delta$进行转移：改变状态、写入新符号、左移或右移
4. 如果进入$q_{accept}$则接受，进入$q_{reject}$则拒绝
5. 可能永不停机（loop）

格局（Configuration）：描述TM某一时刻的完整状态，形如$uqv$表示：

• 纸带内容为$uv$（其余为空白）
• 当前状态为$q$
• 读写头指向$v$的第一个符号

识别与判定：

• 识别（半判定）：TM在输入$w$上停机并接受 $\Leftrightarrow$ $w \in L(M)$
• 判定：TM在所有输入上都停机，且正确接受或拒绝

图灵机的变体

多带图灵机的单带模拟： 用单带存储多带内容，用特殊符号分隔，用额外的标记记录读写头位置。时间复杂度至多增加多项式倍。

丘奇-图灵论题（Church-Turing Thesis）：

任何直观上可计算的函数都可以被图灵机计算。

这不是一个数学定理，而是一个关于”计算”本质的论题，被广泛接受。

停机问题

停机问题是计算机科学中最著名的不可判定问题。

停机问题：给定图灵机$M$和输入$w$，判定$M$是否在输入$w$上停机。

定理：停机问题是不可判定的。

证明（对角化法）： 假设存在判定停机问题的TM $H$，构造TM $D$：

• 输入为图灵机$M$的描述$\langle M \rangle$
• 模拟$H$在输入$(\langle M \rangle, \langle M \rangle)$上的运行
• 如果$H$接受（$M$在自身描述上停机），则$D$进入无限循环
• 如果$H$拒绝（$M$在自身描述上不停机），则$D$接受

考虑$D$在输入$\langle D \rangle$上的行为：

• 如果$D$停机，则$H$接受，则$D$不停机，矛盾！
• 如果$D$不停机，则$H$拒绝，则$D$停机，矛盾！

因此$H$不存在，停机问题不可判定。

可归约性与更多不可判定问题

可归约性：语言$A$可归约到语言$B$（$A \leq_m B$），如果存在可计算函数$f$，使得$w \in A \Leftrightarrow f(w) \in B$。

性质：如果$A \leq_m B$且$B$可判定，则$A$可判定。逆否命题：如果$A \leq_m B$且$A$不可判定，则$B$不可判定。

其他不可判定问题：

Rice定理：任何关于图灵机识别语言的非平凡性质都是不可判定的。

形式化：设$P$是关于语言的性质，$P$是非平凡的（存在TM满足，存在TM不满足），则$L_P = \{\langle M \rangle \mid P(L(M))\}$是不可判定的。

可计算性层次

关系：可判定 = r.e. ∩ co-r.e.

复杂性理论

复杂性理论研究计算问题的资源需求（主要是时间和空间），将问题按照难度分类。

时间复杂度

时间复杂性类：

$\text{TIME}(t(n))$：由$O(t(n))$时间的确定性图灵机判定的语言类。

主要复杂性类：

$\mathbf{P}$的意义：

• 被认为是”易处理”（tractable）的问题类
• 对模型变化鲁棒（多带、随机访问机等多项式相关）

类$\mathbf{P}$

$\mathbf{P}$类包含所有可以被确定性图灵机在多项式时间内判定的语言。

$\mathbf{P}$中的问题：

• 路径问题（PATH）：图中有无$s$到$t$的路径（BFS/DFS）
• 素数判定（PRIMES）：2002年被证明属于$\mathbf{P}$（AKS算法）
• 线性规划
• 上下文无关语言的成员判定

编码的影响： 问题的编码方式可能影响复杂性。通常假设合理编码（如数字用二进制而非一元表示）。

非确定性时间

$\text{NTIME}(t(n))$：由$O(t(n))$时间的非确定性图灵机判定的语言类。

$\mathbf{NP}$ = $\bigcup_k \text{NTIME}(n^k)$：非确定性多项式时间可判定的语言类。

$\mathbf{NP}$的等价定义：

• 可以被多项式时间验证的解的语言
• 存在多项式时间验证器$V$，使得$w \in L$当且仅当存在证书$c$，$|c| = |w|^{O(1)}$，使得$V$接受$(w, c)$

$\mathbf{NP}$中的问题：

NP完全问题与Cook-Levin定理

多项式时间归约：$A \leq_p B$，如果存在多项式时间可计算函数$f$，使得$w \in A \Leftrightarrow f(w) \in B$。

NP难（NP-hard）：语言$B$是NP难的，如果对于所有$A \in \mathbf{NP}$，有$A \leq_p B$。

NP完全（NP-complete）：语言$B$是NP完全的，如果：

1. $B \in \mathbf{NP}$
2. $B$是NP难的

Cook-Levin定理（1971）：SAT是NP完全的。

证明思路：

1. 显然$\text{SAT} \in \mathbf{NP}$（给定赋值可多项式时间验证）
2. 证明SAT是NP难的：对于任意$\mathbf{NP}$语言$L$和输入$w$，构造布尔公式$\phi$，使得$\phi$可满足当且仅当存在证书使$w \in L$
3. 构造模拟NTM计算的布尔电路，编码为CNF公式

经典NP完全问题归约链：

NP完全问题的处理策略

面对NP完全问题，常用策略：

1. 近似算法：在多项式时间内找到接近最优的解

   • 顶点覆盖：2-近似算法
   • TSP（满足三角不等式）：2-近似（MST-based），1.5-近似（Christofides）

2. 启发式算法：没有理论保证但实际效果好

   • 模拟退火
   • 遗传算法
   • 禁忌搜索

3. 参数化算法：将复杂度与问题参数关联

   • 顶点覆盖：$O(1.2738^k + kn)$算法

4. 固定参数可追踪（FPT）：时间复杂度为$f(k) \cdot n^{O(1)}$

5. 随机算法：使用随机化获得好的期望性能

6. 处理特殊情况：某些限制条件下问题可能变得易解

   • 2SAT（每个子句最多2个文字）属于$\mathbf{P}$
   • 平面图上的3COLORING属于$\mathbf{P}$

复杂性类的关系

基本包含关系：

开放问题：

• $\mathbf{P} \stackrel{?}{=} \mathbf{NP}$：计算机科学最重要的未解决问题
• 大多数人相信$\mathbf{P} \neq \mathbf{NP}$
• 证明难度：已知某些证明技术（相对化、自然证明）无法解决此问题

其他重要复杂性类：

NP问题举例

以下是一些著名的NP完全问题：

1. 布尔可满足性问题（SAT）

• 输入：布尔公式$\phi$
• 问题：是否存在赋值使$\phi$为真？
• 3SAT限制：每个子句恰好3个文字，仍是NP完全

2. 团问题（CLIQUE）

• 输入：图$G = (V, E)$，整数$k$
• 问题：$G$是否包含大小为$k$的完全子图？
• 补问题：独立集问题（INDEPENDENT SET）

3. 顶点覆盖（VERTEX-COVER）

• 输入：图$G = (V, E)$，整数$k$
• 问题：是否存在大小为$k$的顶点覆盖（每条边至少一个端点在覆盖中）？
• 关系：顶点覆盖的补是独立集

4. 哈密顿路径/回路

• HAMILTONIAN-PATH：图中是否存在经过每个顶点恰好一次的路径？
• HAMILTONIAN-CYCLE：是否存在哈密顿回路？
• 即使限制在平面图中仍是NP完全

5. 旅行商问题（TSP）

• 判定版本：给定距离矩阵和界限$B$，是否存在长度$\leq B$的回路访问所有城市？
• 优化版本：找最短回路（NP难）
• 欧几里得TSP也是NP完全

6. 子集和（SUBSET-SUM）

• 输入：整数集合$S$，目标值$t$
• 问题：是否存在子集和等于$t$？
• 与背包问题密切相关

7. 划分问题（PARTITION）

• 输入：正整数集合$S$
• 问题：是否可将$S$划分为两个和相等的子集？

8. 图着色（GRAPH-COLORING）

• 输入：图$G$，整数$k$
• 问题：$G$是否$k$-可着色（相邻顶点不同色）？
• 3COLORING是NP完全，2COLORING属于$\mathbf{P}$

9. 装箱问题（BIN-PACKING）

• 输入：物品大小，箱子容量，箱子数量$k$
• 问题：是否可用$k$个箱子装下所有物品？

10. 集合覆盖（SET-COVER）

• 输入：集合族$\mathcal{F}$，全集$U$，整数$k$
• 问题：是否存在$\leq k$个集合覆盖$U$？
• 对数近似比（贪心算法）

这些问题的NP完全性意味着：

• 不太可能有多项式时间算法
• 一个问题的突破意味着所有NP问题的突破（如果找到多项式算法）
• 实际应用中需要借助近似算法、启发式或专门求解器