计算理论¶
集合、关系和语言¶
二元关系¶
- 自反:\((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)|\)
- \(|\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)¶
允许几个可能的下一个状态,选择转移到这些状态中的一个。这一选择不被任何东西决定。
- 形式定义:\(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\) 是非上下文无关的。