Skip to content

计算理论

集合、关系和语言

二元关系

  • 自反：\((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}\) 不可数

康托尔、哥德尔、图灵——永恒的金色对角线 - MwingFly - 博客园

闭包与算法

  • \(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\)。

课后习题

  1. 字符串连接
    1. 证明连接可结合 \((xy)z = x(yz)\)：证明长度相等、字符相同。
    2. 字符串连接的递归定义：对 \(y\) 的长度进行递归定义。
    3. 利用连接的递归定义证明连接的结合律：对 \(yz\) 的长度进行归纳。
  2. 字符串反转
    1. 利用递归定义证明 \((w^R)^R=w\)：对 \(w\) 的长度进行归纳。
    2. 证明子串的反转是反转的子串：直接应用子串和反转的定义即可。
    3. 证明反转和幂的交换律：对幂次进行归纳。
  3. 定义字典序（偏序关系）：分长度不同和长度相同两种情况定义。长度相同的情况，找第一个不同的字符比较。
  4. Kleene 星
    1. 证明 \(\{e\}^* = \{e\}\)：应用 Kleene 星的定义和空串连接的性质即可。
    2. 证明 \((L^*)^* = L^*\)：
      • 我的方法：证明两者互相包含。根据定义已经有一侧了，再证明一侧即可。
      • 书本：直接展开 \((L^*)^*\)，通过下标变换得到 \(L^*\)。
    3. 证明 \(\{a, b\}^* = \{a\}^*(\{b\}\{a\}^*)^*\)：无答案。
    4. 证明 \(L_1\Sigma^*L_2 = \Sigma^*\)，其中 \(L_1, L_2\) 含有空串：证明两侧相互包含。
    5. 证明 \(\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)^*\)

根据上下文，有时候指正则表达式本身，有时候指正则表达式表示的语言，不作严格区分。

课后习题

  1. 理解正则表达式 \((((a^*a)b)\cup b)\)。
  2. 化简正则表达式
    1. \(\emptyset^* \cup a^* \cup b^* \cup (a \cup b)^*\)：\(\Sigma^*\)
    2. \(((a^*b^*)^*(b^*a^*)^*)^*\)：\(\Sigma^*\)
    3. \((a^*b)^*\cup (b^*a)^*\)：\(\Sigma^*\)
    4. \((a\cup b)^*a(a\cup b)^*\)：\(\Sigma^*a\Sigma^*\)
  3. 写正则表达式：

有穷自动机

  • 有穷自动机（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')\)。
  • 字符串被接受 \(w\in L(M)\)：当且仅当 \(\exists q \in F, (s, w)\vdash_M^*(q, e)\)。
  • 状态图：
    • 顶点表示状态，双圈表示终结状态，\(>\) 表示初始状态。
    • 箭头表示 \(\delta(q, a)=q'\)。

课后习题

  1. 什么情况下 \(e\in L(M)\)：当且仅当 \(s\in F\)。
  2. 根据状态图写出 DFA 接受的语言。
  3. 根据语言构造状态机。
  4. 确定型有穷状态转换器：将输入串转换成输出串。
    1. 绘制它的一些状态图。
    2. 形式地定义它。
  5. 确定型双带有穷自动机。

非确定型有穷自动机（Nondeterministic Finite Automata, NFA）

允许几个可能的下一个状态，选择转移到这些状态中的一个。这一选择不被任何东西决定。

  • 形式定义：\(M=(K, \Sigma, \Delta, s, F)\)，与 DFA 一致，只是状态转移函数变成了转移关系
    • \(\Delta\subseteq K\times(\Sigma\cup\{e\})\times K\)：转移关系，其中每一个三元组 \((q, u, p)\) 表示从状态 \(q\) 读取符号 \(u\) 转移到状态 \(p\)。
  • 格局：\((q, w)\) 也是 \(K\times\Sigma^*\) 的元素。
    • 一步产生 \((q, w)\vdash_M(q', w')\)，注意这里 \(\vdash_M\) 不一定是函数，因为可能有若干个或零个下一步。
  • 接受：对于 NFA，只要有某种办法按照给定的字符串从初始状态到达一个终结状态，则接受这个字符串。

NFA 可能猜错，但没关系

这一点一定要注意，NFA 可能猜错，但只要有一种方法是正确的，就可以接受这个字符串。

  • 空转移：NFA 允许空转移，即不消耗任何符号从一个状态转移到另一个状态。

用 NFS 设计一些奇怪的语言

  • \(L=\{\exists a_i, a_i \notin w\}\)，有一个符号不在字符串中的语言。设计方式是：先猜不在的是哪个字符，转移到对应的终结状态，然后接收其余所有字符。

定理 2.2.1：每一台 NFA \(M\) 等价于一台 DFA \(M'\)

想法：认为 NFA 在任意时刻不是处于一个状态，而是处于一个状态集合，即消耗掉输入后可能处于的所有状态。

形式化地说：

  • \(M'\) 的状态集合是 \(M\) 的状态集合的幂集。
  • \(M'\) 的终结状态集合由 \(K\) 中至少包含 \(M\) 的一个终结状态的所有子集组成。
  • \(M'\) 的状态转移函数：模仿 \(M\) 对输入符号 \(a\) 的动作，并且后面可能跟着任意次数的空转移。专门定义一个 \(E(q)\)，对任一状态 \(q\in K\)，\(E(q)\) 是 \(q\) 可以通过空转移到达的所有状态的集合。

上下文无关语言

  • 上一章的有穷自动机是语言识别器，本章将讨论一种语言生成器。这个语言生成器从某种开始信号开始构造字符串，操作从一开始就不确定，但受到一组规则限制，最终停止输出一个字符串。

上下文无关文法

这是一种语言生成器，“上下文无关”的意思是替换规则不依赖于字符串的上下文。

  • 形式定义：\(G=(V, \Sigma, R, S)\)
    • \(V\)：字母表。
    • \(\Sigma\)：终结符集合。
    • \(R\)：规则集合，\((V - \Sigma)\times V^*\) 的有穷子集。
    • \(S\in V - \Sigma\)：开始符号。
    • \(V - \Sigma\) 是非终结符。
  • 关系：
    • 可以是：\(A\rightarrow u\)。
    • 一步产生：\(u\Rightarrow v\)。
    • 产生：\(u\Rightarrow^* 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\) 步。

CFG 和正则表达式的关系：

  • 都是语言生成器
  • \(L\) 是正则语言当且仅当存在一个正则表达式 \(r\) 使得 \(L=L(r)\)
  • \(L\) 是上下文无关语言当且仅当存在一个上下文无关文法 \(G\) 使得 \(L=L(G)\)

证明：所有正则语言是上下文无关的（直接构造法）

考虑由 DFA \(M=(K, \Sigma, \delta, s, F)\) 生成的正则语言 \(L(M)\)。构造下面的 CFG \(G=(V, \Sigma, R, S)\)：

  • \(V=K\cup \Sigma\)
  • \(S=s\)
  • \(R=\{q\rightarrow ap: \delta(q, a)=p\}\cup\{q\rightarrow e: q\in F\}\)

语法分析树