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}\) 不可数

闭包与算法

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

PPT 上的题目

  • 给出 FA 写 CFG
  • 给出正则表达式,构造 FA 然后写 CFG
  • 证明写出的 CFG 是正确的:归纳法
  • 证明一些语言是 CFG 生成的:直接构造 CFG 或通过运算得到
  • 常见上下文无关语言及其思路:
    • \(ww^R\):3 条规则
    • \(w=w^R\):比上面多两个单字符的规则
  • 注意两个平凡的语言同样是上下文无关的:单字符串和空集。
    • 判断题:终结符集不总是非空的。

语法分析树

CFG 的推导可以有很多,语法分析树表示推导的等价类。

  • 先于\(G\) 的两个推导 \(D\)\(D'\),称 \(D \prec D'\)\(D\) 先于 \(D'\)
    • 都是从单个非终结符到终结符串的推导。
    • 从某一步 \(uAvBw\) 开始,\(D\) 的下一步展开 \(A\)\(D'\) 的下一步展开 \(B\)
  • 一个等价类中,有一个推导在 \(\prec\) 下极大,称为最左推导。同理有最右推导。
  • 下面四个东西是等价的:
    • 一棵语法分析树
    • 一个最左推导
    • 一个最右推导

如果一个文法具有多个分析树,也就意味着有多个最左推导,也就意味着有多个最右推导。这种文法称为二义性的。

下推自动机

  • 下推自动机(Pushdown Automata, PDA)\(M=(K, \Sigma, \Gamma, \delta, s, F)\)
    • \(K\):有穷状态集合
    • \(\Sigma\):输入字母表
    • \(\Gamma\):栈字母表
    • \(\delta: K\times(\Sigma\cup\{e\})\times\Gamma^*\rightarrow K\times\Gamma^*\):状态转移函数。\(((p, \alpha, \beta), (q, \gamma))\in\delta\),表示从状态 \(p\) 读取符号 \(\alpha\),栈顶是 \(\beta\),转移到状态 \(q\),栈顶替换为 \(\gamma\)
      • 注意:栈顶元素若为 \(e\),说明对栈没有要求,而不是要求栈为空。
    • \(s\in K\):初始状态
    • \(F\subseteq K\):终结状态集合
  • 格局:机器状态,剩余输入,栈内容,如 \((q, ababa, \alpha)\)
  • 接受字符串:最终的状态是输入串和栈均为空。

课堂例题

  • 设计如下语言的 PDA:
    • \(ww^R\)
    • \(a,b\) 数目相等

下推自动机与上下文无关语言

引理 1:每个 CFL 都被某 PDA 接受

  • 给定 CFG \(G=(V, \Sigma, R, S)\)
  • 构造 PDA \(M=(K, \Sigma, \Gamma, \delta, s, F)\)
    • \(\Gamma=V\)
    • 起始和终结状态分别为 \(p, q\)
    • 状态转移:
      • \(\delta(p, e, e)=(s, S)\) 开始符号入栈
      • \(\delta(s, e, A)=(s, \alpha)\) 应用规则 \(A\rightarrow \alpha\)
      • \(\delta(s, a, a)=(s, e)\) 匹配的终结符出栈
  • 证明 \(L(G)=L(M)\):对 \(w\) 的最左推导的长度进行归纳,证明 CFG 的推导与 PDA 的计算等价。

上面的状态转移过程,本质上是在栈中模拟生成 CFG,然后通过终结符出栈进行逐步匹配。显然在这里我们需要 PDA 是非确定性的,这将影响下一节 CFL 的封闭性质。

引理 2:被 PDA 接受的语言是 CFL

  • 给定 PDA,将其转换到一种最简形式。
  • 根据该 PDA 构造 CFG。

定理:PDA 接受的语言与 CFL 相同

3.5 非上下文无关的语言

  • 上下文无关语言在并、连接和 Kleene 星下封闭。
  • 一个上下文无关语言与一个正则语言的交是一个上下文无关语言。

例题

\(a,b\) 数目相等,但不含子串 \(abaa\)\(babb\) 的语言是上下文无关的。


  • \(L_1\) \(a,b\) 数目相等,它是上下文无关的。
  • \(L_2\) 不含子串 \(abaa\)\(babb\),用正则表达式的补 \(\{a, b\}^*\{abaa, babb\}\{a, b\}^*\) 表示,它是正则的。
  • \(L_1\cap L_2\) 是上下文无关的。
  • 泵定理:对于 CFG,其生成的任意长度大于 \(\phi(G)^{|V - \Sigma|}\) 的字符串 \(w\),都可以被分解为 \(w=uvxyz\),满足 \(|vy|\geq 1\)\(uv^nxy^nz\in L(G)\)
    • 引理:高度为 \(h\) 的语法分析树产生的字符串长度不超过 \(\phi(G)^h\)。(归纳法)
    • \(|vy|\geq 1\) 保证了 \(v\)\(y\) 中至少有一个非空

使用方法:

  • 假设 \(L\) 是上下文无关的,则存在 \(K\),任意长度大于 \(K\) 的字符串可分解(这里可以取其中的一个特殊的 \(w\))。
  • 考虑 \(w\) 所有可能的分解方式(可能需要分类讨论),构造 \(uv^nxy^nz\),使其不在 \(L\) 中。

例题

\(a^nb^nc^n\) 是非上下文无关的。


  • \(n > \phi(G)^{|V - \Sigma|}\),将 \(w\) 按泵定理分解为满足条件的 \(u,v,x,y,z\)
  • 有两种可能:
    • 如果 \(vy\) 中三个符号都出现,则 \(uv^2xy^2z\) 中符号顺序不对
    • 如果 \(vy\) 中只有一或两种符号,则 \(uv^2xy^2z\) 中符号数不对

例题

\(a^n\) 其中 \(n\) 是素数是非上下文无关的。

例题

\(a, b, c\) 个数相等是非上下文无关的。


如果它是上下文无关的,那么它与 \(a^*b^*c^*\) 的交是上下文无关的。但我们知道 \(a^n b^n c^n\) 是非上下文无关的。