计算理论：自动机理论

本笔记以经典教材《Introduction to the Theory of Computation, 3rd/4th Edition》为主要线索，仅对最核心的内容进行简要整理。由于我的主要兴趣在人工智能和机器人上，因此这个笔记本整体只整理为一个单页，而非像强化学习、深度学习那样每一章都详细整理为一个单页。

本书以及本课程将带领我们了解这么一个根本性的问题：

计算机的基本能力和局限性是什么？

What are the fundamental capabilities and limitations of computers?

对于一个计算问题，我们很难进行数学分析。因此我们把一个字符串的集合叫做语言，然后把一个问题转化为语言，接着就可以用严格的数学工具来分析问题了。换句话说，任何一个“是/否”形式的计算问题，都可以被看作是一个语言识别问题。

从这个角度来说，计算理论有三个主题，他们其实都是在研究如何使用语言：

1、Automata 自动机（自动机理论）—— Ch.1 - Ch.3

自动机理论研究用什么样的机器可以识别什么样的语言：

最简单的有限自动机能识别什么语言？——正则语言
复杂一点的下推自动机能识别什么语言？——上下文无关语言
最强大的图灵机能识别什么语言？——所有可计算语言

2、Computability 可计算性（可计算性理论）

可计算性理论就是研究什么是计算机可以识别的语言（即计算机可以解决的问题），什么事计算机不能识别的语言（即计算机不能解决的问题）。如果我们能找到一个语言，对于这个语言，我们永远无法设计出一个算法（图灵机）来完美判断一个字符串是否属于它，那么这个语言就是不可判定的语言（即计算机不能解决的问题）。比如“停机问题”所对应的语言，就是不可判定的。

3、Complexity 复杂性（计算复杂性理论）

计算复杂性理论研究识别一个语言需要耗费多少资源，即探讨在可以解决的问题中，哪些问题容易解决，哪些问题不容易解决。著名的PvsNP问题中，P和NP都是语言的集合。P类语言是那些可以被快速（多项式时间）解决的问题。NP类语言是那些解一旦被猜出，可以被快速验证的问题。P vs NP问题本质上就是在问，这两个语言的集合是否相等。

计算复杂性理论最直接的应用就是密码学，通过找到难计算的问题，来实现安全的加密。

Ch.0 离散数学基础

一般在学习计算理论前要掌握离散数学的基本知识。这里简单过一下离散数学的主要内容，注意这里并不展开讲解离散数学，而是针对计算理论需要的离散数学基础进行简要概述，因此在本部分的案例中也会以计算理论相关的内容为主。

计算理论中最常用的数学工具几乎都来自于离散数学，包括：

Set 集合
Union, Intersection, Complement（并、交、补）
Sequence 序列
Tuple 元组
Cartesian Product 笛卡尔积（Cross Product 叉积）
Function 函数
Mapping 映射
Graph 图
Undirected Graph, Directed Graph （无向图、有向图）
String, Lexicographic Order（字符串，字典序）

Boolean Logic 布尔逻辑：

AND ∧
OR ∨
NOT ¬
Exclusive OR ⊕ （只有1⊕0为0）
Equality ↔
Implication → （只有1→0为0）

定义、定理和证明：

Defination 定义
Mathematical Statement 数学命题
Proof 证明
Theorem 定理
Lemma 引理
Corollary 推论
Counterexample 反例

命题记号：

⟺ iff, if and only if
for P⟺Q:
forward direction: P⟹Q
reverse direction: Q⟹P

证明的类型

Proof by Construction 构造性证明
Proof by Contradiction 反证法
Proof by Induction 归纳法
Basis 归纳基础
Induction Step 归纳步骤

0.1 逻辑与证明方法

归纳法

归纳法（Induction）的证明方法是从小到大逐步推进，先证明base case（比如空串、最短串），再假设长度为k的时候命题成立，然后推出k+1时也成立，整个逻辑链条依赖长度逐步增加的归纳假设。

归纳法非常严谨，适合场景：

语言或者性质与字符串长度紧密相关，比如“任意长度的字符串都满足某种结构”。
要证明递归定义的语言，比如正则表达式生成的语言、递归语法定义的语言。
涉及逐级增长的性质，例如“无论读多少个字符，DFA都保持某个不变性”。

举例：

1758719123259

证明：

This DFA recognizes the language by proof of induction on the length of the input string such that the DFA always ends in the correct state according to the last symbol and the requirement that the string starts with 0.

Base Case:

If w is a single 0, the DFA moves from q₀ to q₁. The DFA does not accept this string because it doesn’t begin with a 0 AND end with a 1.
If w is a single 1, the DFA moves from q₀ to q₃. The DFA does not accept this string and will never accept because it doesn’t begin with a 0.
If w is the empty string, the DFA will immediately reject because it doesn’t begin with a 0 or end with a 1.

Inductive Steps:

Suppose the DFA is in the correct state after reading a string of length k and let w be a string that begins with a 0 and ends with a 1 of length k + 1.

If w began with a 1, the DFA transitioned to q₁ and will never accept due to an infinite loop.
Otherwise, if w began with a 0, the DFA can either be in q₁ or q₂ after reading in k characters.

Now there are two cases:

The last character of w is a 0
The last character of w is a 1

In the first case, if the last character of w is a 0, regardless of whether the DFA is in q₁ or q₂, the DFA will end in q₁ and reject.

In the second case, if the last character of w is a 1, regardless of whether the DFA is in q₁ or q₂, the DFA will end in q₂ and accept.

We know that the DFA only accepts a string iff (if and only if) it ends in q₂ and by the invariant, q₂ means the string starts with 0 and ends with 1.

Conversely, if the string does not begin with 0, the DFA will go into an infinite loop in q₃ and reject.

And if the string does not end with 1, the DFA will end in q₁ and reject.

构造法

构造法（Construction）也叫做分类讨论（Case Analysis），相比于归纳法更为直观易懂，分析方法也比较简单。但是构造法显然无法对涉及任意长度、递归结构的语言进行分类（即无法处理无限分类的情况）。

构造法适合场景：

语言性质比较局部，可以通过有限情况分类来完全覆盖。
DFA的设计明显基于几类不同的模式，直接逐类分析就能得出结论。

举例：

1758719123259

证明：

This DFA recognizes the language by proof of construction by breaking up how the DFA handles strings in different cases.

For any string w, w will either be one of the following:

w begins with a 0 and ends with a 1
w begins with a 0 and doesn’t end with a 1
w doesn’t begin with a 0 and ends with a 1
w doesn’t begin with a 0 and doesn’t end with a 1

In case 1, the DFA must transition to q₁ since w begins with a 0 and it must end up in q₂ because regardless of whether the DFA is in q₁ or q₂ before the last character is read, it will always end in q₂. Therefore, strings in this case will always get accepted.

In case 2, the DFA must transition to q₁ since w begins with a 0 and it must end up in q₁ because regardless of whether the DFA is in q₁ or q₃ before the last character is read, it will always end in q₁. Therefore, strings in this case will always be rejected.

In case 3 and 4 (which can be combined), the DFA must transition to q₃ since w begins with a 1 and will remain in q₃ as the state loops on all inputs. Therefore, strings in this case will always be rejected.

From the above cases, the only strings that can be accepted by this DFA are those that begin with a 0 and end with a 1 (case 1). All other cases result in the string being rejected. Therefore, the DFA recognizes the above language.

反证法

（待补充）

0.2 数学概念和术语

集合、序列和多元组、笛卡尔积

函数、映射、关系

等价关系、偏序关系

单射、满射、双射

可逆性、函数组合

组合数学与计数原理

排列组合
鸽巢原理
基本概率

图论基础

图与子图、树
路径、连通性
欧拉路径、哈密顿路径

数论基础

整除、模运算
素数与同余
对密码学/可计算性有帮助

布尔逻辑（书上0.2.6）

Ch.1 正则语言

1.1 字符串和语言

字符串是计算机科学的重要基础之一。根据应用的要求，可以在各种各样的字母表上定义这样的字符串。按照要求，定义 字母表（alphabet）为任意一个非空有限集合。字母表的成员为该字母表的符号（symbol）。通常用大写希腊字母 $\Sigma$ （Sigma）和 $\Gamma$（Gamma）表示字母表和字母表中符号的打印字符。下面是几个字母表的例子：

\[ \Sigma_1 = \{0,1\} \]

\[ \Sigma_2 = \{a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z\} \]

\[ \Gamma = \{0,1,x,y,z\} \]

字符串（string over an alphabet）为该字母表符号的有限序列，通常写为一个符号接着一个符号，不用逗号隔开。设 $\Sigma_1=\{0,1\}$，则 $01001$ 为 $\Sigma_1$ 上的一个字符串。设 $\Sigma_2=\{a,b,c,\cdots,z\}$，则 abracadabra 为 $\Sigma_2$ 上的一个字符串。

设 $w$ 为 $\Sigma$ 上的一个字符串，$w$ 的长度（length）等于它所包含的符号个数，记作 $|w|$。长度为零的字符串叫空串（empty string），记为 $\epsilon$。空串起到的作用像在整数环中的零一样。如果 $w$ 的长度为 $n$，则可写为：

\[ w = w_1 w_2 \cdots w_n, \quad \text{这里每个 } w_i \in \Sigma. \]

它的反转（reverse）是按照相反的顺序写下 $w$ 所得到的字符串，记作 $w^R$，即：

\[ w^R = w_n w_{n-1} \cdots w_1. \]

如果字符串 $x$ 连续地出现在 $w$ 中，则称 $x$ 为 $w$ 的子串（substring）。例如，cad 为 abracadabra 的子串。

设 $x$ 是长度为 $m$ 的字符串，$y$ 是长度为 $n$ 的字符串，$x$ 和 $y$ 的连接（concatenation）是把 $y$ 附加在 $x$ 后面得到的字符串，记为 $xy$，即：

\[ xy = x_1 \cdots x_m y_1 \cdots y_n. \]

可采用上标表示法表示一个字符串自身连接多次，例如 $x^k$ 表示：

\[ \underbrace{xx\cdots x}_{k \text{次}}. \]

字典序（lexicographic order）和大家熟悉的字典顺序一样。通常，我们采用 字符串顺序（shortlex order 或 string order），它在字典序基础上将短的字符串排在长的字符串的前面。例如，字母表 $\{0,1\}$ 上的所有字符串的字符串顺序为：

\[ (\epsilon, 0, 1, 00, 01, 10, 11, 000, \cdots) \]

字符串 $x$ 是字符串 $y$ 的前缀（prefix），如果存在字符串 $z$ 使得 $y = xz$。若且若 $x \neq y$，则 $x$ 称为 $y$ 的 真前缀（proper prefix）。

字符串的集合称为语言（language）。如果语言中任何一个成员都不是其他成员的前缀，那么该语言是 无前缀的（prefix-free）。

1.2 有限状态机

现实中的计算机太复杂，我们从更加简单和抽象的模型开始学习。我们用计算模型（computational model）来抽象一个计算机，只保留我们关心的核心特征。

我们关注状态和状态之间的转换，而不考虑复杂的内存和硬件，因此这种模型叫做有限状态机（finite state machine, FSM），也叫做有穷自动机（finite automaton）。

这里注意，有限自动机只有有限多个状态，没有额外的存储器，因此并非我们今天正在使用的计算机。现在我们用的计算机，更近似于图灵机（严格意义上的图灵机有无限的存储空间，但如今的计算机在存储空间上已经有极大的扩展空间，因此可以认为近似于图灵机），而非有限状态机。

当然，我们的生活中其实有很多有限状态机，比如：红绿灯、自动售货机、遥控器等。

一般情况下，我们主要关注DFA（Deterministic Finite Automaton），即确定性的有限状态机。DFA和NFA的核心区别就是：对于每一个状态，DFA对任何字母表内的合格字符都有着唯一的对应的转移方式；而NFA则不唯一。

一个有限自动机FA可以定义为一个五元组（5-tuple）：

\[ (Q, \Sigma, \delta, q_{0}, F) \]

where

$Q$ is a finite set called the states 状态集合
$\Sigma$ is a finite set called the alphabet 字母表
$\delta : Q \times \Sigma \to Q$ is the transition function 转移函数
$q_{0} \in Q$ is the start state 起始状态
$F \subseteq Q$ is the set of accept states 接受状态集

其中，FA必须有start state，但是特殊情况中accept states可以为空。

上述五元组也叫做有限自动机（Finite Automaton, FA）的形式化定义。 这个五元组之所以是“形式化”的，是因为它使用了精确的数学语言（集合、函数等）来描述一个自动机，没有任何模糊不清的地方。它精确定义了：

有哪些状态 (Q)
能接收哪些输入符号 (Σ)
如何从一个状态转移到另一个状态 (δ)
从哪个状态开始 (q0)
哪些状态是最终的成功状态 (F)

任何一个有限自动机，无论它多么复杂，都可以用这样一个五元组来毫无歧义地描述。这就是“形式化定义”的核心。

我们在绘制DFA的时候，用一个没有来源的箭头指向start state，然后用两个圈来代表accept state；accept state不一定存在，也不一定只有一个。下图是一个状态转移图的例子：

1758724039765

如果A是机器M可以接受的一串string，那么我们就说：A is the language of machine M, 并写作：

\[ L(M) = A \]

We say that M recognizes A, or M accepts A. 一台FA机器可以接受若干字符串，但它永远只能识别一个语言。

我们可以用简明的描述（Concise Description）来描述一个DFA：

集合形式
正则表达式
语言表达

1758724348162

以上图为例，可以用语言表述：

M2 accepts exactly the set of binary strings that end with a 1.

也可以用集合形式表述：

\[ L(M_2) = \{ w \mid w \text{ ends in a } 1 \} \]

或者用正则表达式：

\[ L(M_2) = (0 + 1) * 1 \]

上面三种都是concise description。

例1： 识别状态转移图，描述该DFA的语言：

1758724847567

我们可以绘制一个状态表，或者代入查看转移关系。可以发现，当接收0时，状态转移到q1；否则转移到q2。q1是accept state。也就是说，该DFA或者说Machine接收的是以0为结尾的字符串。即：

\[ L(M) = \{\, w \mid w \text{ is the empty string } \varepsilon \text{ or ends in a } 0 \,\}. \]

例2： 识别下列DFA所示语言

1758725025103

这个图中你会发现一旦接收到状态，要么去q1，要么去r1，没有返回s的情况。所以这个Machine记住了第一个符号。即如果最后接收的是a，那么第一个字符就是a；如果最后接收的是b，那么第一个字符就是b。更进一步地，该Machine接收开始与结束符号相同的字符串。即：

\[ L(M) = \{\, w \mid w \text{ starts and ends with the same symbol} \,\} \]

例3： 识别下列DFA所示语言

1758725231656

这个Machinbe多了一个 <RESET>，这个是特殊符号。上述DFA从q0开始，如果是0就接受，1的话到q1，2的话到q2；在q1这里如果是2就返回q0然后被接受；在q2的话如果是1就回到q0……仔细观察，会发现这就是一个模运算FA。RESET的作用是暂停当前的模运算，进行新的模运算。

我们可以把这个DFA进行泛化，对任意数字进行取模运算，可得如下Machine：

For each $i \geq 1$ let $A_i$ be the language of all strings where the sum of the numbers is a multiple of $i$, except that the sum is reset to $0$ whenever the symbol $\langle \text{RESET} \rangle$ appears.

For each $A_i$ we give a finite automaton $B_i$, recognizing $A_i$. We describe the machine $B_i$ formally as follows:

\[ B_i = (Q_i, \Sigma, \delta_i, q_0, \{ q_0 \}), \]

where $Q_i$ is the set of $i$ states $\{ q_0, q_1, q_2, \dots, q_{i-1} \}$, and we design the transition function $\delta_i$ so that for each $j$, if $B_i$ is in $q_j$, the running sum is $j \pmod{i}$.

For each $q_j$ let:

\[ \begin{aligned} \delta_i(q_j, 0) &= q_j, \\ \delta_i(q_j, 1) &= q_k, \quad \text{where } k = j+1 \pmod{i}, \\ \delta_i(q_j, 2) &= q_k, \quad \text{where } k = j+2 \pmod{i}, \\ \delta_i(q_j, \langle \text{RESET} \rangle) &= q_0. \end{aligned} \]

例4： 设计一个DFA，识别“至少包含一次字串001的二进制string”

解题思路:

忽略所有的1
一旦看到0，就记住可能是001的第一个0
接着如果还是0，就记住可能是001的00
接下来如果又是一个0，则仍然保持00状态
在00状态下看到1，则找到了解，accept

1758725603425

1.3 形式化定义

在上一节我们了解了五元组形式化定义（formal definition）和简明描述方法（concise description）。上面我们提到，在计算理论中，一个字符串的集合叫做“语言”（Language），这个集合可以包括有限或无限个字符串。

注意区分字母表和语言：

字母表（Alphabet）是有限的字符集合
语言（Language）是字符串的集合，是字母表中字符的有限序列

比如：

\[ L_{1} = \{\, \text{"cat"}, \text{"dog"}, \text{"fish"} \,\} \quad (\text{有限集合}) \]

\[ L_{2} = \{\, \text{所有以 "ab" 结尾的字符串} \,\} \quad (\text{无限集合，如 "ab", "aab", "bab", }\dots) \]

当一个自动机M能够对每一个传递给它的字符串w，给出一个“接受”（Accept）或者“拒绝”（Reject）的结论的时候，那么我们说：

\[ A = \{\, w \mid M \ \text{accepts } w \,\}. \]

上述描述有两层含义：

M接受的字符串，都在语言A里
M拒绝的字符串，都不在语言A里

因而，自动机M是语言A的一个完美的、精确的“定义”，或者说“规则”。如果一个语言能够找到一个对应的按照上述方式进行描述的FA，这个FA能够用上述的方式识别这个语言，那么我们就说这个语言是一个正则语言（regular language）。同理，如果一个语言不能找到这样的对应的FA，那么这个语言就不是正则语言。

例如：

所有以1结尾的binary string: FA只需要判断最后一个字符是不是1，因此是正则语言。
所有包含007的string：可以设计几个状态来追踪是否有连续的007，因此是正则语言。
所有由n个0后面跟着n个1组成的字符串：因为FA没有记忆能力，因此你无法设计出一个FA来设别这个语言，因此这个并非正则语言。

1.4 正则运算

闭包性质

闭包（Closure） 是一个数学概念，描述的是集合和运算之间的关系。其主要内容是：如果一个集合里的成员，在经过某种运算后产生的结果依然在这个集合内，那么这个集合就是封闭的（Closed）。

比如说：

对于所有整数，加法运算是封闭的。
对于所有证书，除法运算不是封闭的，因为整数除以整数可能是小数。
对于所有奇数，加法运算是不封闭的。（奇数+奇数=偶数）
字符串在拼接（concatenation）运算下是封闭的。
布尔值集合在AND运算下是封闭的。

闭包性质是一个检验工具，用来描述一个集合在某种运算下是否自给自足。在计算理论中，“正则语言在正则运算下具有闭包性” 是一个核心定理。这个定理是构建正则表达式、编译器等高级工具的理论基石。

并运算 Union

以及并运算的闭包性质

假设A和B是两个语言，则并运算：

\[ A \cup B = \{ x \mid x \in A \;\text{or}\; x \in B \} \]

连接运算 Concatenation

以及连接运算的证明闭包性质

假设A和B是两个语言，则连接运算：

\[ A \circ B = \{ xy \mid x \in A \;\text{and}\; y \in B \} \]

星号运算 Star

以及星号运算的证明闭包性质

假设A和B是两个语言，则星号运算：

\[ A^* = \{ x_1 x_2 \cdots x_k \mid k \geq 0 \;\text{and each } x_i \in A \} \]

1.5 正则表达式

一个使用代表‘并、连接、星号’的符号，把代表最基础语言（如 {a}、{ε}）的符号，组合起来的式子，就是正则表达式。我们之前提到，能用FA识别的语言就是正则语言。在学习正则运算符号后，我们现在又获得了一个新的判定方法：能用正则表达式表达的语言，就是正则语言。

就描述能力而言，正则表达式和DFA是等价的。换句话说，所有的DFA都可以用正则表达式来描述。任何一个DFA（确定性有限自动机）所能识别的语言，都一定可以用一个正则表达式来描述。反之，任何一个正则表达式所描述的语言，也一定可以用一个DFA来识别。

这不仅仅是一个巧合，而是由一条著名的定理——克林定理 (Kleene's Theorem) 所保证的。这个定理揭示了一个深刻的等价关系：

正则表达式 (Regular Expressions) ⇔ 有限自动机 (Finite Automata)

具体来说，下面这三种描述语言的方式，它们在表达能力上是完全等价的：

正则表达式 (Regular Expression)
非确定性有限自动机 (NFA)
确定性有限自动机 (DFA)

它们都能且仅能描述同一类语言，这类语言被称为 “正则语言” (Regular Languages) 。

这种等价关系意味着我们有明确的算法可以在这几种形式之间进行转换：

正则表达式 → NFA ：我们可以用一种叫做“汤普森构造法” (Thompson's construction) 的算法，将任意一个正则表达式转换成一个等价的NFA。
NFA → DFA ：我们可以用“子集构造法” (Subset construction) 将任意一个NFA转换成一个等价的DFA。
DFA → 正则表达式 ：同样，我们也有算法（例如“状态消除法” State Elimination Method 或 Brzozowski's Algebraic Method）可以将任意一个DFA转换成一个等价的正则表达式。

总结一下上面的几节内容，其实就是：

首先我们了解什么是正则语言：能被FA识别的就是正则语言。
然后我们学习三个正则运算符号：并、连接、星号。
接着我们了解到，正则运算符合闭包性质。
最后我们升华到：能用正则运算表达的就是正则语言。

在Ch1.正则语言中，我们了解到以下内容相互等价：

有穷自动机 Finite Automata: DFA/NFA
正则表达式 Regular Expressions
正则文法 Regular Grammar
五元组 5-Tuple

正则语言封闭于以下主要运算：

并集 (Union): $L_{1} \cup L_{2}$
连接 (Concatenation): $L_{1} \cdot L_{2}$
克莱尼星号 (Kleene\ Star): $L_{1}^{*}$
交集 (Intersection): $L_{1} \cap L_{2}$
补集 (Complement): \overline{$L_{1}$}
差集 (Difference): $L_{1} - L_{2}$

正则语言位于乔姆斯基谱系 (Chomsky Hierarchy)这个形式语言谱系的 最底层 (Type-3) ，是能力最弱但也是最容易分析的一类：

Type-0：递归可枚举语言 (Turing Machines)
Type-1：上下文相关语言 (Linear-Bounded Automata)
Type-2：上下文无关语言 (Pushdown Automata)
Type-3：正则语言 (Finite Automata)

因此，学完正则语言后，我们就要继续学习上下文无关语言和图灵机。从隶属关系（完整的语言集合包含关系）和对应的机器能力关系上来说：

正则语言 ⊂ 上下文无关语言 ⊂ 上下文相关语言 ⊂ 图灵机可判定的语言
有限自动机 < 下推自动机 < 线性有界自动机 < 图灵机

1.6 泵引理

如果我们现在遇到了一个语言L，我们想知道这个语言是什么，我们可以通过如下思路来分析：

首先，我们尝试为该语言构造一个DFA/NFA/正则表达式，如果构造成功，那么语言L就是正则语言
如果构造失败，那么我们怀疑L可能不是正则语言，那么我们就用正则语言的泵引理来证明该语言不满足泵送条件。如果证明成功，那么这个语言就不是正则语言。
如果这个语言不是正则语言，那么我们就尝试为改语言构造一个下推自动机PDA或者上下文无关文法CFG。如果构造成功，那么就证明L是上下文无关语言CFL。
如果构造失败，那么我们怀疑该语言不是CFL，那么我们就要用上下文无关语言的泵引理。如果证明成功，那么这个语言就不是上下文无关语言。
如果这个语言不是上下文无关语言，那么我们可以继续判断他是否是上下文相关语言或者递归可枚举语言；如果能成功构造线性有界自动机LBA或者图灵机Turing Machine，那么他就是上下文相关语言或者递归可枚举语言。

在正则语言和上下文无关语言的阶段，泵引理是最好用的工具；但是到了上下文相关语言和图灵机的阶段，泵引理便不再好用了。所以我们在这里主要讨论正则语言的泵引理和上下文无关语言的泵引理。

正则语言的泵引理（Pumping Lemma）可以用来证明一个语言不是正则语言。 换句话说，正则语言的泵引理（本章中简称泵引理）是一个证伪工具，我们可以通过假设语言L是正则，然后发现L不满足泵引理性质，来推论一个语言不是正则；但是如果一个语言L满足泵引理的性质，我们不能断定他就是正则语言。

考虑语言：

\[ B = \{0^n1^n \mid n \geq 0\} \]

\[ C = \{\,w \mid w \text{ 中 }0\text{ 和 }1\text{ 的数量相等}\,\} \]

\[ D = \{\,w \mid w \text{ 中出现子串 }01\text{ 和 }10\text{ 的次数相等}\,\} \]

上面的语言中，0和1出现的次数都可能是无限个，但是我们很难直观地判断哪一个不是正则语言、哪一个是正则语言。因为上面的三个语言中：B和C不是正则语言，但D是正则语言。

因此，我们需要一个好用的、严格的方法，来判断一个语言是否是正则的。

我们一般用泵引理来证明语言的非正则性。为什么叫“pumping lemma”呢？ “pump”的意思就是打气，你可以想象给一个自行车打气：你不停地把打气筒按下去又拉上来、按下去又来上来，这个动作非常地重复且有规律。

比如说，我们现在有一个字符串“xyyyyyyz”，那么显然中间的y可以通过pump的方式打进去，于是这个字符串就可以改写成“x{pump:y}z”。

现在来看Pumping Lemma: If A is a regular language, then there is a number $p > 0$ (the pumping length) where if $s$ is any string in A of length at least $p$, then $s$ may be divided into three pieces, $s = xyz$, satisfying the following conditions:

for each $i \geq 0, xy^{i}z \in A$，这里的$y^i$代表连续i个y连接在一起
$\lvert y \rvert > 0$，这里的双竖线包围代表字符串y的长度
$\lvert xy \rvert \leq p$

$y$的长度不为0也记作$y \ne \varepsilon$，这个记法在形式语言、分析学、自动机理论中特别指代空字符串（katex格式为\varepsilon）。当字符串s被划分为xyz的时候，x或z可以使空字符串，但y不能是空字符串。这个条件是pumping lemma的灵魂。condition 3的规定的含义是：可以被pumping的部分必须出现在字符串的开头，也就是前p个字符内。

总之，记住下面这几个关键信息：

pumping length p > 0
exist string s, |s| >= p
$xy^{i}z \in A$
|xy|<=p
|y|>0

解题步骤就是：

从pumping lemma获得p
选择一个s，满足|s|>=p且s属于L
列举pumping lemma的三个性质
把s拆分开看，发现xy的内容
pumping y，得到s'
发现s'不属于L，反证结束

现在我们回头看刚才的B、C、D这三个语言。

EXAMPLE 1

$B = \{0^n1^n \mid n \geq 0\}$

首先我们假设B是正则语言，那么B一定符合泵引理。设p>0为泵长度，那么必然有一个字符串s，有|s|>=p，属于B。根据泵引理，我们有：s=xyz, s'=xy^iz也属于B，且|xy|<=p, |y|>0.

现在，我们选择n=p, 那么s=xyz。由于|xy|<=p, 所以xy只包含0，那么y也只包含0。现在，根据泵引理，我们假设i=2，那么s'=xyyz也属于B。由于y中只包含0，所以s'相比于s只增加了y的数量，且增加了至少一个0。而由于z的数量没有变，因为1只存在于z中，所以s'中1的数量没有变。

我们发现，xyyz由于0和1的数量不相等，所以xyyz不属于B。这与我们的假设相悖，因此B不是正则语言。

EXAMPLE 2

$C = \{\, w \mid w \text{ has an equal number of }0\text{s and }1\text{s} \,\}$.

这个可以直接用B的反例来证明，因为C是B的一个特例，所以B中那个反例在C这里也适用。

EXAMPLE 3

\[ F = \{\, ww \mid w \in \{0,1\}^* \,\} \]

这个和上面的还是很像，可以把B中的情况double一下，组成一个特例，然后反证。

令$s=0^p1^p0^p1^p$，则|s|=4p>=p。拆分s为xyz, 由于|xy|0，所以y只有0。接着pumping，让i=2，然后s'=xyyz，则新字符串中的0增加了，这导致$0^{p+增加}1^p$和后半部分的$0^p1^p$的长度不再相等，从而导致s'不属于F，与假设相悖，因而证明了F不是正则语言。

EXAMPLE 4

$D = \{\, 1^{n^{2}} \mid n \geq 0 \,\}$

这个语言的意思是该语言仅由1组成，其长度由指数$n^2$决定。

证明方法：令n=p, 把s拆分为s=xyz, 令i=2，那么$s'=xyyz, |s'|=|s|+|y|=p^2+k$，那么我们的任务其实就变成了证明$p^2+k$不是平方数。由于p是整数，所以$p^2$的下一个数是$(p+1)^2$，即$p^2+2p+1$，由于$1 \leq \lvert y \rvert \leq p$，所以$p^2 < p^2 + k \leq p^2+p < p^2 + 2p + 1$，因此pumping后长度达不到下一个平方数，也就是说pumping后的s'的长度不是一个平方数，从而证明D不是正则语言。

EXAMPLE 5

证明一个语言不是回文。

这种类型可以通过闭包性质：如果L不是回文同时是正则语言，那么他的补集也是正则语言。接着我们只需要证明L的补集（回文语言）不是正则语言就行了。

Ch.2 上下文无关文法

2.1 CFG与CFL

在第一章节的末尾，我们学习了如何使用泵引理来证明一个语言不是正则语言，比如经典的例子：

\[ \{0^n1^n \mid n \ge 0\} \]

由于0和1的数量都是无限且不确定数量的，我们没有办法构造出一个DFA来描述这个语言。本章我们来学习一个可以描述上述语言的上下文无关文法（Context-Free Grammar, CFG），在乔姆斯基谱系 (Chomsky Hierarchy) 这个形式语言谱系的 第二层 (Type-2) ，是能力最弱但也是最容易分析的一类：

Type-0：递归可枚举语言 (Turing Machines)
Type-1：上下文相关语言 (Linear-Bounded Automata)
Type-2：上下文无关语言 (Pushdown Automata)
Type-3：正则语言 (Finite Automata)

上下文无关文法CFG在程序设计语言中有着重要的应用。当设计人员编写程序设计语言的编译器和解释器时，常需先获取该语言的文法。因此，大多数编译器（Compiler）和解释器都包含一个语法分析器（parser），它在生成编译代码或解释程序执行前，提取出程序的语义。

与上下文无关文法相关的语言集合称为上下文无关语言（Context-Free Language, CFL）。请注意，上下文无关语言是包含正则语言的。

上下文无关文法由一组替换规则（substitution rule）组成，替换规则又称为产生式（production）。每条规则占一行，由一个符号和一个字符串构成。

例如文法$G_1$：

\[ \begin{aligned} A &\rightarrow 0A1 \\ A &\rightarrow B \\ B &\rightarrow \# \end{aligned} \]

上面的三行指令就是替换规则（Substitution Rule）或者说产生式（Productions）。它的含义是：

一个A可以变成一个0、一个A和一个1的组合
一个A也可以变成一个B
一个B可以变成一个#

其中可以被替换的符号，叫做Variables（变量）或Non-terminals（非终结符），在上面A和B可以被替换，因此A和B就是变量。

其中不能再被替换的符号，叫做终结符（Terminals）。这些不能被替换的符号，就是我们造句过程中的基础积木，是最终成品的组成部分。在上面的文法中，终结符有0、1、#。

起始变量（Start Variable） 是造句的起点，一般按照惯例，它就是第一条规则左边的那个变量，在上面的文法中就是A。

那我们如何用这个文法造句呢？我们从起始变量A出发，不断应用规则替换，最终得到一个只包含终结符的字符串，就完成了造句。比如：

从A起始，目标是造一个句子00#11
A
0A1
0(0A1)1
00B11
00#11，推导完毕

上面这个过程叫做派生（derivation）。凡是能通过上述推导过程造出来的句子，都符合这个文法，叫做文法的语言（language of the grammar）。能够用上下文无关文法生成的语言称为上下文无关语言（CFL）。

上面的文法例子的特点是，#号两边的0和1的数量必须相等。如果我们把它写为语言，那么这个语言就是：

\[ \{0^n\#1^n \mid n \ge 0\} \]

任何不满足上面规律的字符串，都是这个文法造不出来的，比如：

00#1
01#
0011
a#b

为了方便，我们把可以派生出多种结果的变量写作：

\[ \begin{aligned} A &\rightarrow 0A1 | B\\ B &\rightarrow \# \end{aligned} \]

2.2 形式化定义

上下文无关文法的形式化定义是一个4-tuples：

Set of Variables: $V$
Set of Terminals: $\Sigma$
Set of Rules: $R$
Start Variable: $S$

例如：

\[ \begin{aligned} &\text{Set of Variables (V): } V = \{P\} \\ &\text{Set of Terminals } (\Sigma): \Sigma = \{a, b, (, ), \cup, *, \emptyset\} \\ &\text{Set of Rules (R):} \\ &P \rightarrow a \\ &P \rightarrow b \\ &P \rightarrow \emptyset \\ &P \rightarrow (P) \\ &P \rightarrow P \cup P \\ &P \rightarrow PP \\ &P \rightarrow P* \\ &\text{Start Variable (S): } S = P \end{aligned} \]

2.3 下推自动机

待复习：下推自动机PDA等

2.4 泵引理

待复习：上下文无关语言的泵引理

2.4 DCFL

待复习：确定型上下文无关语言

2.5 封闭性

参考作业3的第一题。

Ch.3 图灵机

3.1 图灵机

3.2 形式化定义

一个图灵机由一个7-tuples组成，以二进制数加一的图灵机为例：

Set of States (Q):

$$ Q = {Start, Carry, Back, End} $$ 2. Input Alphabet (Σ):

$$ \Sigma = {0, 1} $$ 3. Tape Alphabet (Γ):

$$ \Gamma = {0, 1, -} $$ 4. Transition Function (δ):

$$ \begin{aligned} \delta(Start, 0) &= (Start, 0, R) \ \delta(Start, 1) &= (Start, 1, R) \ \delta(Start, -) &= (Carry, -, L) \[6pt] \delta(Carry, 1) &= (Carry, 0, L) \ \delta(Carry, 0) &= (Back, 1, L) \ \delta(Carry, -) &= (Back, 1, L) \[6pt] \delta(Back, 0) &= (Back, 0, L) \ \delta(Back, 1) &= (Back, 1, L) \ \delta(Back, -) &= (End, -, R) \end{aligned} $$ 5. Start State:

$$ q_0 = Start $$ 6. Accept State:

$$ q_{\text{accept}} = End $$ 7. Reject State:

$$ q_{\text{reject}} = \emptyset $$

3.3 丘奇-图灵论题

1900年，数学家希尔伯特在巴黎举行的世界数学家大会上提出了23个数学问题，其中第十个是关于不定方程的可解答性的，也就是给定一个不定方程：

\[ a_1 x_1^{b_1} + a_2 x_2^{b_2} + \cdots + a_n x_n^{b_n} = c \]

希尔伯特的问题是：能否给定一个这样的任意多个未知数的不定方程（丢番图方程），通过一种可行的方法（希尔伯特所说的verfahren，就是我们今天所说的algorithm），经过有限次运算，可以判定该方程是否有整数解。

虽然早在古希腊以及春秋时代，人们就知道可以使用类似辗转相除法这样的方式进行运算。但是，到了希尔伯特的时代，人们依然对于什么是可行的计算，仍然没有精确的概念。一个问题可解与不可解，究竟是什么含义，当时的人们还不得而知。

1936年，丘奇（Alnozo Church）和图灵（Alan Turing）给出了该问题的定义。丘奇使用称为$\lambda$演算的记号系统来定义算法，而图灵则使用机器来做同样的事情。这两个定义后来被证明是等价的，因而算法的非形式化概念和精确定义之间的这个联系从此被称为丘其-图灵论题（Church-Turing Thesis）：

Intuitive notion of algorithms

EQUALS

Turing machine algorithms

即：算法的直观概念等于图灵机算法。简单来说，丘奇-图灵论题断言：任何我们直观上认为可计算的问题，或者说任何存在算法能解决的问题，都等价于可以用一台图灵机来解决。

丘奇-图灵论题提出的算法定义是解决希尔伯特第10问所必需的。1970年，马提亚塞维奇证明了该问题。

Ch.4 可判定性

1761016039627

可识别的语言

详见下一节。

可判定的语言

我们说图灵机 $M$接受$w$，是指机器从一个起始配置 $C_1$ (即机器在初始状态 $q_0$，磁带上写着 $w$，读写头在 $w$ 的开头) 开始运行。经过一系列的单步状态转移 ( $C_i$ 产生 $C_{i+1}$ )，机器最终达到了一个“接受配置” $C_k$ (即机器的状态变成了 $q_{\text{accept}}$)。只要存在这样一条能达到 $q_{\text{accept}}$ 的路径，我们就说 $M$ 接受 $w$。

基于“接受”的定义，我们就可以定义一个图灵机的“语言”：

定义：一个图灵机 $M$ 的语言，记作 $L(M)$，是所有 $M$ 能够接受的字符串 $w$ 的集合。
数学表示 ：$L(M) = \{w \mid M \text{ accepts } w\}$

现在，基于 $L(M)$ 的概念，我们来定义两种不同“难度”的语言：

(A) 图灵可识别语言 (Turing-recognizable)

定义：一个语言 $L$ 是 图灵可识别的 ，如果存在一个图灵机 $M$，使得 $L(M) = L$。
通俗讲解 ：
如果一个字符串 $w$ 在这个语言 $L$ 中 (即 $w \in L$)，那么这个图灵机 $M$ 运行后一定会停机并接受 (accept) $w$。
如果一个字符串 $w$ 不在这个语言 $L$ 中 (即 $w \notin L$)，那么 $M$ 运行后有两种可能：
1. 停机并拒绝 (reject)。
2. 永不停机 (陷入无限循环)。
核心点 ：这种机器只需要对“是”的答案（$w \in L$）给出肯定的答复（停机并接受）。它不需要保证对“否”的答案一定能停机。

(B) 图灵可判定语言 (Turing-decidable)

定义：一个语言 $L$ 是 图灵可判定的 ，如果存在一个“判定器” (Decider) $M$ 来决定它。
什么是“判定器” (Decider)？
“判定器”是一种特殊的图灵机，它保证对任何输入都永远不会进入无限循环。它总会在有限的时间内停机，并给出“接受”或“拒绝”的答案。
通俗讲解 ：
如果一个字符串 $w$ 在这个语言 $L$ 中 (即 $w \in L$)，判定器 $M$ 会在有限时间内停机并接受 (accept)。
如果一个字符串 $w$ 不在这个语言 $L$ 中 (即 $w \notin L$)，判定器 $M$ 也会在有限时间内停机并拒绝 (reject)。
核心点 ：这种机器（判定器）必须对所有输入（无论是“是”还是“否”）都能在有限时间内停机并给出明确的答案。

特性	图灵可识别 (Turing-recognizable)	图灵可判定 (Turing-decidable)
对于$w \in L$(在语言中)	必须停机并接受	必须停机并接受
对于$w \notin L$(不在语言中)	可以停机并拒绝，也可以永不停机	必须停机并拒绝
是否总停机？	不一定	是，总会停机

总结来说，Decider 判定器必须保证停下来，即无论你给他什么问题（输入），他都必须在有限的时间内完成计算，然后亮起一盏灯：

Accept，接受，代表是
Reject，拒绝，代表否

Decider总会停机（Halts on all inputs），绝对不会陷入死循环或者无限思考中。如果一个问题能被Decider回答，那么这个问题就是Decidable（可判定的）。

如果一个语言 L 和它的补集都是可识别的，那么 L 就是 可判定（decidable） 的。（因为可以并行运行两个识别器，一个认L，一个认L的补集，必有一个会停）。

定理：一个语言是可判定的，当且仅当它既是图灵可识别的，也是补图灵可识别的。换句话说，一个语言是可判定的，当且仅当他和他的补都是图灵可识别的。

例1： “这个数字 $N$ 是不是偶数？”

判定器工作：

接收数字 $N$。
计算 $N$ 除以 2 的余数。
如果余数是 0，停机并回答 “是” 。
如果余数是 1，停机并回答 “否” 。

分析： 这个过程非常快，而且对于任何数字 $N$，它都保证会停下来给出一个明确的“是”或“否”的答案。所以，这是一个 Decider。

例2：令 $M$ 为一个图灵机，$w$ 为 $M$ 的输入字母表中的一个字符串。考虑以下问题：

$A = \{\langle M, w \rangle \mid M \text{ 在 } w \text{ 上的计算中在某个点向左移动}\}$

证明 $A$ 是可判定的（decidable）。

解答：

要证明一个语言是可判定的，我们必须构造一个“判定器” (Decider)。这个判定器是一个图灵机，它在任何输入上都必须停机 (always halts)，并给出正确的“接受”或“拒绝”的答案。

这个问题的核心难点在于：我们如何处理 $M$ 在 $w$ 上无限循环的情况？

我们要构造一个判定器 $D$ (Decider)，它来判定语言 $A$： $A = \{\langle M, w \rangle \mid M \text{ 在 } w \text{ 上的计算中至少移动过一次左 (Left)}\}$

我们将构造一个判定器 $D$。$D$ 会模拟$M$ 在 $w$ 上的运行，但它会 设置一个最大步数限制 ，以防止 $M$ 无限循环导致 $D$ 自己也无限循环。

关键在于证明：如果 $M$ 永远不向左移动，它要么在有限步数内停机，要么会进入一个可被检测到的无限循环。

判定器 $D$ 在收到输入 $\langle M, w \rangle$ 后，执行以下操作：

1、获取 $M$ 和 $w$ 的参数 ：

令 $k$ 为 $M$ 的状态数量 ($|Q|$)。
令 $g$ 为 $M$ 的带字母表大小 ($|\Gamma|$)。
令 $n$ 为 $w$ 的长度 ($|w|$)。（如果 $w$ 是空串， $n=1$）。

2、计算一个“最大步数”界限 (Bound) ：

界限 1 (在输入 $w$ 上循环)： 如果 $M$ 的读写头始终保持在 $w$ 的 $n$ 个格子内（即位置 1 到 $n$）并且从不向左移动（即只移动 'R' 或 'S'），那么它的“配置”(configuration) 可以由 (当前状态, 读写头位置, $n$ 个格子的内容) 来定义。

可能的状态数：$k$
可能的读写头位置：$n$
可能的带内容：$g^n$
总的配置数 $B_1 = k \times n \times g^n$。
如果 $M$ 在 $w$ 上运行超过 $B_1$ 步并且读写头从未超过第 $n$ 个格子，它一定重复了某个配置，因此它陷入了一个永不向左的无限循环。

界限 2 (在空白带上循环)： 一旦 $M$ 的读写头移动到 $w$ 之后的空白带上（即位置 $> n$）并且从不向左移动，它就永远不会再回头读取 $w$。

此时，它的行为只取决于它的（当前状态）和它（当前读取的带符号）。
可能的（状态, 符号）组合数：$B_2 = k \times g$。
如果 $M$ 在空白带上运行超过 $B_2$ 步（并且从未向左移动或停机），它一定重复了某个（状态, 符号）组合。因为它右边的带总是相同的（全是 $\sqcup$ 或它自己写下的符号序列），它将陷入一个永不向左的无限循环。

总界限 ：我们设置一个总的模拟步数 $B = B_1 + B_2$。

3、开始有限模拟 ：

模拟 $M$ 在 $w$ 上的运行，但最多只模拟 $B$ 步。
在模拟的每一步中 ：
情况 (a) ：如果 $M$ 的转移函数指示它 向左移动 (L) ，则 $D$ 停机并接受 (ACCEPT) 。（因为 $\langle M, w \rangle \in A$）
情况 (b) ：如果 $M$ 停机（进入 $q_{\text{accept}}$ 或 $q_{\text{reject}}$），则 $D$ 停机并拒绝 (REJECT) 。（因为它停机了却从未向左移动）
情况 (c) ：如果模拟 达到了 $B$ 步，而 $M$ 既没有向左移动，也没有停机。

4、得出结论 ：

如果在模拟中发生了情况 (a) 或 (b)， $D$ 已经给出了答案。
如果模拟达到了 $B$ 步（情况 c），根据我们对 $B_1$ 和 $B_2$ 的分析，这一定意味着 $M$ 已经陷入了一个永不向左的无限循环。因此，$D$ 停机并拒绝 (REJECT) 。

为什么 $D$ 是一个“判定器”？

$D$ 总会停机 ：$D$ 的模拟要么在 $B$ 步之内因情况 (a) 或 (b) 而停机，要么在 $B$ 步时因情况 (c) 而强制停机。$B$ 是一个根据输入 $\langle M, w \rangle$ 计算出来的具体、有限的数字。因此，$D$ 永远不会无限循环。
$D$ 总是正确的 ：
如果 $\langle M, w \rangle \in A$ ($M$ 确实向左移动了)，这个移动一定发生在 $M$ 停机或循环之前。如果它发生在 $B$ 步内，$D$ 会通过情况 (a) 接受。如果 $M$ 在 $B$ 步后才向左移动，那它一定是在 $B$ 步内进入了循环，但这是不可能的（因为我们的界限 $B$ 就是用来检测非左移循环的），所以向左移动一定发生在 $B$ 步内。
如果 $\langle M, w \rangle \notin A$ ($M$ 永不向左移动)，$M$ 只有两种可能：
$M$ 停机：$D$ 会在 $B$ 步内通过情况 (b) 拒绝。
$M$ 无限循环：$D$ 会在 $B$ 步时通过情况 (c) 检测到这个循环并拒绝。

因此，$D$ 是一个判定器，所以 $A$ 是 可判定的 (decidable) 。

例3：

$A_{TM}$是可识别的、不可判定的；

$\overline{A_{TM}}$时不可识别的、不可判定的。

quiz3：You will be asked to prove languages decidable or recognizable.

你将被要求证明某些语言是可判定的或可识别的

涉及内容：

可判定语言，对应Decider 判定机
可识别语言，对应Recognizer 识别机，Semi-decider 半判定机

这里注意，所有可判定语言都是可识别语言：

可判定的对L接受并停机，对非L拒绝并停机，所以总是停机
可识别的对L接受并停机，对非L拒绝或永不停止，不保证停机

对角化方法

According to COROLLARY 4.18 on textbook, some languages are not Turing-recognizable.

According to the diagonalization method, $L_{diag}$ and its complement is not recognizable.

特性	图灵可识别 (Turing-recognizable)	图灵可判定 (Turing-decidable)
对于\(w \in L\)(在语言中)	必须停机并接受	必须停机并接受
对于\(w \notin L\)(不在语言中)	可以停机并拒绝，也可以永不停机	必须停机并拒绝
是否总停机？	不一定	是，总会停机