形式语言与计算复杂性笔记

这学期（2025 春）在上《形式语言与计算复杂性》课程（COMP6106P01）。黄文超老师授课时细节讲述的非常严谨认真，我听课时也产生了一些有趣的（可能上课没有讲到的）直观想法（以及一些私货），所以写一些笔记作为记录。

绪论

课程概述

作为本文开头，还是对这门课程做一个概述。本门课程实际是计算理论的一个入门。计算理论关心的是，给定一个计算模型（比如我们的计算机），我们能够用这个模型解决什么问题，以及这些问题的解决方案的复杂性如何。

解决问题的复杂性可以用时间复杂度等手段描述，这就是 complexity 关心的事情。研究复杂度的好处我们已经在上学期的《算法设计与分析》课程学到。如果一个问题是 NPC：

那你应该知道它很难，可以不用花时间再去尝试设计一个多项式时间的算法了。
你可以借鉴已有的 NPC 问题的近似算法，设计一个实践中可接受的算法。

然而，并非所有的问题都可以用我们的电脑解决，一些问题在理论上就是不可计算的（无法设计一个算法能在有限时间内解决）。这就又带来两件事情：

我们的电脑对应的计算模型（图灵机），到底能解决什么问题？
其他的计算模型呢？有没有更弱或者更强的计算模型，使得解决的问题集合不同？分别能解决什么问题？

关心我们的电脑能解决什么问题很重要。本门课程先从一些更弱的计算模型（被形式化为自动机，如 DFA，PDA）开始，先研究这些自动机能解决什么问题，然后再研究图灵机。

Terminology 与类型

定义了一些基本概念：

Set

Sequences and Tuples

Functions and Relations

Graphs

Strings and Languages

Boolean Logic

这里有趣的是它们基本都是构造性的。比如：

G = (\{1, 2, 3, 4, 5\}, \{(1, 2),(2, 3),(3, 4),(4, 5),(5, 1)\})

这件事情可以写成：

type Node = number
type Edge = [Node, Node] // 表示 tuple
type Graph = [Set<Node>, Set<Edge>]

const nodes = new Set([1, 2, 3, 4, 5])
const edges = new Set([
  [1, 2],
  [2, 3],
  [3, 4],
  [4, 5],
  [5, 1]
])
const G: Graph = [nodes, edges]
console.log(G)

这里数学对象的定义和程序中的对象对应得很好。数学对象的类型在程序语言中也有对应的类型。

在后面的课程中，使用类型的观点来看待数学对象也会使得理解更加容易。这是因为我们后续会研究一些复杂的对象，比如“所有正则语言的集合”，然而某个正则语言本身又是一个字符串的集合。为了区分开这些不同层次的对象，可以采用类型的方式来区分。例如，某个正则语言就是一个 Set<string>，而“所有正则语言的集合”就是 Set<Set<string>>。

明确了这些对象的类型，我们就可以更好地理解这些对象具备的操作。还是以正则语言为例。既然正则语言是一个 Set，那它自然就具备集合的操作，比如并集、交集、补集等。在正则语言一节我们就要研究并集操作（其他操作也有其意义，比如 Brzozowski derivative）。并且我们根据集合论的直觉就知道，两个正则语言的并集定义应该是：

function union(L1: Set<string>, L2: Set<string>): Set<string> {
  return new Set([...L1, ...L2])
}
// union({'a', 'b'}, {'b', 'c'}) = {'a', 'b', 'c'}
console.log(union(new Set(['a', 'b']), new Set(['b', 'c'])))

本门课程之外，类型在编程中还有更多的作用，和更多数学上的对应。例如本文用来举例的 TypeScript 就支持 Algebraic Data Types，可以实现类型之间的并集、笛卡尔积等操作。此时可以把某个类型看成一类对象的集合。

正则语言

总结

研究自动机能解决什么问题，就是要研究自动机能接受什么语言。这一节我们研究了有限状态自动机。

我们把 DFA 能解决的问题（接受的语言）称为正则语言；
这样就把有限状态自动机能力的边界转换为了正则语言表达能力的边界；
我们定义了正则表达式，它从 $\{\}, \{\varepsilon\}, \{a\}\ (a \in \Sigma)$ 出发，通过正则表达式的运算（并、串接、闭包）递归定义：
- 一方面证明正则表达式表达的语言都是正则语言；
- 另一方面证明正则语言都可以用正则表达式表达；
- 这就说明正则表达式和正则语言的等价。
结论：DFA 的能力和正则表达式的能力是等价的。

用正则表达式描述 DFA 的能力，好处是更加直观，也更加方便我们研究。例如，有了这个描述，我们要判断 DFA 能不能解决某个 decision problem，就只要判断这个问题的语言是不是正则语言，或者能不能用正则表达式描述。

这里的 decision problem 要求是判断某个 string 在不在一个特定的 Set<string> 中。虽然看起来约束很强，但往往我们都能将其他的 decision problem 归约到这种形式。而更一般地，其他 search problem 和 optimization problem 又常常可以归约到 decision problem。所以这里研究 decision problem 是很有意义的。

主线已经清晰，补充一些细节。

正则操作 - 并

正则操作就是正则表达式的构造过程（或者叫构造子）。现在要干的事情是：

说明正则表达式能够表达的语言都是正则语言；

递归证明，只要说明正则操作应用在正则语言上是封闭的。这就是证明封闭的动机。

并集操作对于语言如下定义：

L_1 \cup L_2 = \{x \mid x \in L_1 \text{ or } x \in L_2\}

证明的核心思路我们已经有了识别 $L_1$ 和 $L_2$ 的 DFA，那么我们可以让它们同时运行，只要有一个接受，那么 $x$ 就在 $L_1 \cup L_2$ 中。

因为要同时运行，所以新的 DFA 的状态要同时保存两个 DFA 的状态。这样的状态可以通过直积构造： $Q = Q_1 \times Q_2$ ，转移函数 $\delta((q_1, q_2), a) = (\delta_1(q_1, a), \delta_2(q_2, a))$ 等显然。

正则操作 - 连接和闭包

现在要证明连接和闭包操作在正则语言上也封闭：

\begin{align*} L_1 \cdot L_2 &= \{xy \mid x \in L_1, y \in L_2\}\\ L_1^* &= \{x_1x_2\cdots x_k \mid k \ge 0, x_i \in L_1\} \end{align*}

这里要开的支线就比较大了。我们不好直接构造出 DFA 来证明，因此采用的策略是引入一个比 DFA 更强的 NFA，证明已知 $L_1$ 和 $L_2$ 对应的 DFA（那它们自然也是 NFA），我们可以构造出 $L_1 \cdot L_2$ 和 $L_1^*$ 对应的 NFA，再把 NFA 转换到 DFA，就完成了构造。

这里定义好后需要注意一个记号的问题，那就是 $\{\}$ 和 $\{\varepsilon\}$ 的区别。 $\{\}$ 表示空集，而 $\{\varepsilon\}$ 表示只有空串的集合。按照集合演算，自然可以理解下面的结果：

\begin{align*} \{1\}^*\{\varepsilon\} &= \{1\}^*\\ \{1\}^*\{\} &= \{\}\\ \{\}^* &= \{\varepsilon\} \end{align*}

NFA to DFA

课程的算法把 NFA 分成两类，分别讨论了存在 $\varepsilon$ -transition 和不存在 $\varepsilon$ -transition 的情况。这里的观察是我们可以看图简单理解这个算法：

NFA to DFA

NFA 可以看成数个（进程？）同时在活跃。假设 NFA 有 $N$ 个状态。

注意到，某个时刻，如果两个 NFA 进程处在相同的状态，那么它们的后续演变是完全一致的，我们就可以把它们合并。那么图中的每一层只要用 Set<State_of_NFA> 就可以表示，这个 Set 是 NFA 的状态集的幂集的一个元素，取值个数显然是有限的，所以可以对应到 DFA 的状态。

可以想象，NFA 在运行过程中，其不确定性体现在每次可能会发生分裂。然而如何分裂却是确定的，所以我们可以用当前 NFA 所有能到达的状态来作为 DFA 的状态，并进行转移。

DFA to Regexp

这里我们说明：

另一方面，说明所有正则语言都可以用正则表达式描述；

那只要给出 DFA 到正则表达式的转换算法就可以了。上课的算法是引入 GNFA，然后消除状态的算法。这里的观察是，我们可以不采用 GNFA。

完整的想法可以参考 Brzozowski algebraic method，下面给出一个直观的理解。

将 DFA 的所有状态标号为 $1, 2, \cdots, n$ ，那么我们可以令 R[k][i][j] 表示一个能判定所有从 $i$ 状态到 $j$ 状态，并且中间经过结点（不包括 $i$ 和 $j$ ）的下标最大为 $k$ 的正则表达式。

按照定义：

R[0][i][j] = \bigcup_{a \in \Sigma, \delta(i, a) = j} a

递推关系：

R[k][i][j] = R[k-1][i][j] \cup (R[k-1][i][k] \cdot R[k-1][k][k]^{*} \cdot R[k-1][k][j])

换言之，我们每次在 R[k-1][i][j] 的基础上，松弛新加入的状态机结点 $k$ 。

这样，最终的正则表达式：

R = \bigcup_{j \in F} R[n][q_0][j]

显然每一步都是正则表达式的并、串接、闭包操作，所以最终的结果也是正则表达式。

非正则语言

这一部分是想举例说明什么样的语言不是正则语言，并且证明。比如 $B = \{a^n b^n \mid n \ge 0\}$ 。

稍微思考一下这个问题会发现，这个语言的特点是 $a$ 和 $b$ 的数量是相等的。然而 DFA 状态是有限的，所以这里有个非常简单的证明：

假设存在一个能接受 $B$ 的 DFA，状态数为 $n$ 。我们投喂给它一个 $aaa...$ 的前缀。假设投喂完 $k$ 个 $a$ 后，DFA 的状态是 $q_k$ 。当 $k = n$ 时，连同初始状态 $q_0$ ，DFA 一共经过了 $n+1$ 个状态，那么必然存在两个状态相同，也就是存在 $i < j \leq n$ ，使得 $q_i = q_j$ 。

这就出现了矛盾：

因为 $q_i$ 由投喂 $i$ 个 $a$ 得到，所以再投喂 $i$ 个 $b$ 就应该转移到接受状态；
但是因为 $q_i = q_j$ ，所以再投喂 $i$ 个 $b$ 不足以转移到接受状态。

这就说明不存在接受 $B$ 的 DFA，所以 $B$ 不是正则语言。

pumping lemma

上课的思路是先给出 pumping lemma 的结论，然后再证明。但这么做不太直观，所以这里展示怎么在不知道 pumping lemma 的情况下推导出它。

把上面所说的证明过程一般化：

假设 $A$ 是一个正则语言，它的 DFA 状态数为 $n$ 。则任意 $s \in A$ ，如果 $|s| \ge n$ ，则自动机在被投喂前 $n$ 个字符后经过了 $n+1$ 个状态。根据抽屉原理可设 $q_i = q_j (i < j \leq n)$ 。

$i$ 和 $j$ 作为字符串下标，我们把 $s$ 分成三部分： $s = xyz$ ：

$x = s[0: i]$ ；
$y = s[i: j]$ ；
$z = s[j: n]$ 。

由 $s \in A$ 得 $\forall k \ge 0, xy^kz \in A$ 。

结论（pumping lemma）：如果 $A$ 是正则语言，它的 DFA 状态数为 $n$ ，则任意 $s \in A, |s| \ge n$ ，都有 $s$ 可以被分成三部分 $xyz$ ，满足 $|xy| \leq n$ ， $|y| \ge 1$ ，且 $\forall k \ge 0, xy^kz \in A$ 。

$|xy| \leq n$ 和 $|y| \ge 1$ 等价于 $i < j \leq n$ 。

可以试着用 pumping lemma 来说明上一节的 $B$ 不是正则语言。只需要取出一个 $s = a^nb^n = xyz$ ，因为 $|xy| \leq n$ ，所以 $y$ 中只包含 $a$ ，那么 $xy^2z$ 中 $a$ 的数量会超过 $b$ 的数量，所以不在 $B$ 中，矛盾。

上下文无关语言

总结

在正则语言中，我们考虑了机器 DFA 和它接受的语言正则语言，并且把正则表达式和正则语言等价。

然而这一节，我们先介绍一种能生成语言的文法：上下文无关文法（CFG）。我们定义它能生成的语言就是上下文无关语言（CFL）。然后再给出机器 PDA，最后说明 PDA 能接受的语言和 CFL 的等价。

Ambiguity

前面 CFG 的一些定义没什么问题，略过。

这里讨论了 CFG 的二义性问题，例如对于：

S \to S + S \mid S \times S \mid a

则 $a + a \times a$ 有两种解析方式。这里的解析方式指的是语法树的差别（根结点是作为一个乘法结点还是加法结点，这会带来语义上的不同），而无关推导时先展开哪个产生式，所以定义了最左推导的概念，明确二义性指的是语法树不唯一。

Chomsky Normal Form

未完待续。