计算理论¶
集合、关系和语言¶
二元关系¶
- 自反：\((a, a)\in R\)
- 对称：\((a, b)\in R \land a \neq b \Rightarrow (b, a)\in R\)
- 反对称：\((a, b)\in R \land a \neq b \Rightarrow (b, a)\notin R\)
-
传递性：\((a, b)\in R \land (b, c)\in R \Rightarrow (a, c)\in R\)
-
等价关系：自反、对称、传递
- 表现为无向图的连通分量
-
偏序关系：自反、反对称、传递
- 偏序集中的极小元、极大元
- 全序关系：偏序关系且任意两个元素有序关系
有限和无限集¶
- 基数（Cardinality）：集合中元素的个数 \(|A|\)、\(\mathrm{card}(A)\)、\(\#A\)
- 等势（Equinumerous）：\(|A|=|B|\)，存在双射 \(f:A\rightarrow B\)
- 有限集：与某个 \({1, 2, \ldots, n}\) 等势。
- 无限集：不是有限集的集合。
- 可数无穷集：与自然数集 \(\mathbb{N}\) 等势，基数为 \(\aleph_0\)。
- 不是所有的无限集都等势。
- 可数集：有限集或可数无穷集。
- 不可数集：不是可数集的集合。
证明：可数无穷个可数无穷集的并集是可数无穷集
- 设 \(A_1, A_2, \ldots\) 是可数无穷个可数无穷集。
- 构造一个二维表格，\(A_1\) 的元素为第一行，\(A_2\) 的元素为第二行，以此类推。
- 沿着对角线遍历，得到一个可数无穷集。
证明：\(|\mathbb{R}| = |(0, 1)|\)
\[
f(x) = \frac{1}{\pi}\arctan(x) + \frac{1}{2}
\]
- \(|\mathbb{R}| = \aleph_1\)
- 连续统假设：
- 不存在介于 \(\aleph_0\) 和 \(\aleph_1\) 之间的基数。
- \(\aleph_0 < \aleph_1\)。
- 康托尔定理：\(|A| < |\mathcal{P}(A)|\)
三个基本证明技术¶
- 数学归纳法
- 鸽巢原理
- 对角化原理：\(R\) 是集合 \(A\) 上的二元关系，对角线集合 \(D=\{x\in A|(x, x)\notin R\}\)。对于任意 \(a \in A\)，令 \(R_a = \{x\in A|(a, x)\in R\}\)，则 \(D\neq R_a\)。
- 为什么对角线集合与方阵的每一行都不同？因为它的构造：与第一行在第一个位置不同，与第二行在第二个位置不同，以此类推。
证明：\(|\mathbb{R}| > |\mathbb{N}|\)，即不可数
证明：\(2^\mathbb{N}\) 不可数
闭包与算法¶
- \(R^*\)：自反传递闭包。
- \(R^+\)：传递闭包。
字母表与语言¶
| 中文 | 英文 | 符号 | 说明 |
|---|---|---|---|
| 字母表 | alphabet | \(\Sigma\) | 有穷符号集合 |
| 字符串 | string | \(w\) | 字母表中符号的有穷序列 |
| 空串 | empty string | \(e\) | |
| 长度 | length | \(\|w\|\) | |
| \(\Sigma^*\) | 字母表上所有字符串集合 | ||
| 子串 | substring | \(v\) 是 \(w\) 的子串，当且仅当 \(\exists x, y\) 使 \(w=xvy\) | |
| exponentiation | \(w^i\) | \(w\) 的 \(i\) 次幂 | |
| 反转 | reversal | \(w^R\) | 对字符串 \(w\) 的长度进行递归定义 |
| 字符串连接 | concatenation | \(x \circ y\) \(xy\) |
|
| 语言 | language | \(L\) | 字符串的集合 |
| Kleene 星号 | Kleene star | \(L^*\) | 连接 \(L\) 中 0 或多个字符串得到的所有字符串的集合 \(L^*=\{w_1w_2\ldots w_n\|n\geq 0, w_i\in L\}\) |
| 语言连接 | concatenation | \(L_1 \circ L_2\) \(L_1L_2\) |
|
| \(L^+\) | \(LL^*\)，可以视为连接运算的闭包 |
证明：对任意两个字符串 \(w\) 和 \(x\)，\((wx)^R=x^Rw^R\)
对 \(x\) 的长度进行归纳。
- 字符串的数量
- 如果 \(\Sigma\) 是有穷的，则 \(\Sigma^*\) 是可数无穷集。
- 语言的数量
- 任何字母表上的任何语言都是可数的。
- 字母表上的语言的数量是 \(|\mathbb{R}|=\aleph_1\)。因为所有语言的集合是 \(\mathcal{P}(\Sigma^*)\)，而可数无穷集的幂集的基数是 \(\aleph_1\)。
课后习题
- 字符串连接
- 证明连接可结合 \((xy)z = x(yz)\)：证明长度相等、字符相同。
- 字符串连接的递归定义：对 \(y\) 的长度进行递归定义。
- 利用连接的递归定义证明连接的结合律：对 \(yz\) 的长度进行归纳。
- 字符串反转
- 利用递归定义证明 \((w^R)^R=w\)：对 \(w\) 的长度进行归纳。
- 证明子串的反转是反转的子串：直接应用子串和反转的定义即可。
- 证明反转和幂的交换律：对幂次进行归纳。
- 定义字典序（偏序关系）：分长度不同和长度相同两种情况定义。长度相同的情况，找第一个不同的字符比较。
- Kleene 星
- 证明 \(\{e\}^* = \{e\}\)：应用 Kleene 星的定义和空串连接的性质即可。
- 证明 \((L^*)^* = L^*\)：
- 我的方法：证明两者互相包含。根据定义已经有一侧了，再证明一侧即可。
- 书本：直接展开 \((L^*)^*\)，通过下标变换得到 \(L^*\)。
- 证明 \(\{a, b\}^* = \{a\}^*(\{b\}\{a\}^*)^*\)：无答案。
- 证明 \(L_1\Sigma^*L_2 = \Sigma^*\)，其中 \(L_1, L_2\) 含有空串：证明两侧相互包含。
- 证明 \(\emptyset L = L\emptyset = \emptyset\)：空集中取不出字符串，所以结果是空集。
5、6、7 todo。
语言的有穷表示¶
- 正则表达式的字母表：\(\Sigma\cup\{ (, ), \cup, *, \emptyset \}\)。
- 正则表达式是可数的（\(\Sigma^*\)），语言是不可数的（\(2^{\Sigma^*}\)），故存在不可用正则表达式表示的语言。
- 正则语言类：所有可以写成 \(L=L(a)\) 的语言，其中 \(a\) 是 \(\Sigma\) 上的正则表达式。
- 正则表达式表示的语言的运算：
- \(L(\alpha \beta) = L(\alpha)L(\beta)\)
- \(L(\alpha \cup \beta) = L(\alpha)\cup L(\beta)\)
- \(L(\alpha^*) = L(\alpha)^*\)
根据上下文，有时候指正则表达式本身，有时候指正则表达式表示的语言，不作严格区分。
课后习题
- 理解正则表达式 \((((a^*a)b)\cup b)\)。
- 化简正则表达式
- \(\emptyset^* \cup a^* \cup b^* \cup (a \cup b)^*\)：\(\Sigma^*\)
- \(((a^*b^*)^*(b^*a^*)^*)^*\)：\(\Sigma^*\)
- \((a^*b)^*\cup (b^*a)^*\)：\(\Sigma^*\)
- \((a\cup b)^*a(a\cup b)^*\)：\(\Sigma^*a\Sigma^*\)
- 写正则表达式：
有穷自动机¶
- 有穷自动机（Finite Automata, FA）：\(M\)
- 接受输入（一个字符串 \(w\)），给出是否接受这个输入的信号。
- 核心是有穷控制器（一个黑盒），在特定的时刻处于有穷个状态中的一个 \(q\)。
- 每隔一定时间读取一个符号，进入一个新的状态。
- 如果结束在一个终结状态，认为输入被接受。
- 机器接受的语言是它接受的所有字符串的集合 \(L(M)\)。
确定型有穷自动机（Deterministic Finite Automata, DFA）¶
- 新的状态只与当前状态和刚读到的符号有关。
- 形式定义：\(M=(K, \Sigma, \delta, s, F)\)
- \(K\)：有穷状态集合
- \(\Sigma\)：字母表
- \(s\in K\)：初始状态
- \(F\subseteq K\)：终结状态集合
- \(\delta: K\times\Sigma\rightarrow K\)：状态转移函数。如果 \(M\) 处于状态 \(q\)，读到符号 \(a\)，则 \(\delta(q, a)\) 是下一个状态。
- 格局：当前状态和被处理的字符串尚未读过的部分，如 \((q_2, ababa)\)。
- 用格局序列可以描述 FA 在一个字符串上的计算。
- 格局间的关系：
- 一步产生 \((q, w)\vdash_M(q', w')\)
- 当且仅当 \(\delta(q, w)=q'\) 且 \(\exists a\in\Sigma, w=aw'\)。
- 这是从 \(K\times\Sigma^+\) 到 \(K\times\Sigma^*\) 的一个关系，因为 \((q, e)\) 不再有下一步。
- 产生：一步产生的自反传递闭包 \((q, w)\vdash_M^*(q', w')\)。
- 一步产生 \((q, w)\vdash_M(q', w')\)
- 字符串被接受 \(w\in L(M)\)：当且仅当 \(\exists q \in F, (s, w)\vdash_M^*(q, e)\)。
- 状态图：
- 顶点表示状态，双圈表示终结状态，\(>\) 表示初始状态。
- 箭头表示 \(\delta(q, a)=q'\)。
课后习题
- 什么情况下 \(e\in L(M)\)：当且仅当 \(s\in F\)。
- 根据状态图写出 DFA 接受的语言。
- 根据语言构造状态机。
- 确定型有穷状态转换器：将输入串转换成输出串。
- 绘制它的一些状态图。
- 形式地定义它。
- 确定型双带有穷自动机。
非确定型有穷自动机（Nondeterministic Finite Automata, NFA）¶
上下文无关语言¶
- 上一章的有穷自动机是语言识别器，本章将讨论一种语言生成器。这个语言生成器从某种开始信号开始构造字符串，操作从一开始就不确定，但受到一组规则限制，最终停止输出一个字符串。
上下文无关文法¶
- 形式定义：\(G=(V, \Sigma, R, S)\)
- \(V\)：字母表。
- \(\Sigma\)：终结符集合。
- \(R\)：规则集合，\((V - \Sigma)\times V^*\) 的有穷子集。
- \(S\in V - \Sigma\)：开始符号。
- \(V - \Sigma\) 是非终结符。
- 关系：
- 可以是：\(A\rightarrow_G u\)。
- 一步产生：\(u\Rightarrow_G v\)。
- 产生：\(u\Rightarrow_G^* v\)。
- \(G\) 生成的语言：\(L(G)=\{w\in\Sigma^*|S\Rightarrow_G^* w\}\)。上下文无关语言。
- 推导：\(w_0\Rightarrow_G w_1\Rightarrow_G \ldots \Rightarrow_G w_n\)，有 \(n\) 步。