重要知识点(复习)
Language, Automaton, Regex¶
正则表达式¶
使用 \(A|B\) (或、并集),\(AB\) (concatenation) 以及 \(A\ast\) (Kleene-star)。
NFA 转 Regex¶
Pump Lemma¶
If \(L\) is a regular language, then there exists a length \(p\), where \(\forall w \in L, \exists x,y,z: |w| \geq p, |xy| \leq p, |y| \geq 1, w=xyz \implies xy^\ast z \subseteq L\).
说人话,就是:存在一个长度 \(p\),比这个长度长的所有字符串,一定存在一种 \(w=xyz\) 的形式(其中 \(xy\) 比这个长度短,\(y\) 非空),使得所有 \(xy^\ast z\) 都属于这个 \(L\)。
- 其中,由于状态的数量是有限的,又由于 \(xy\) 一定不超过这个数量,因此 \(xy\) 长度有限
Context-Free Language¶
Pushdown Automaton¶
相比 NFA 来说,这个 pushdown automaton
- 所有箭头处增加了 \(? \to ?\) 这一个标志,也就相当于,如果你希望走这一步,那么就必须在栈顶进行这样的变换
- 最后必须状态在 final states 中且栈为空才接受。
Pump Lemma for CFL¶
说人话,就是:存在一个长度 \(p\),比这个长度长的所有字符串,一定存在一种 \(w=uvwxy\) 的形式(其中 \(vwx\) 比这个长度短,\(vx\) 非空),使得所有 \(uv^nwx^ny\) 都属于这个 \(L\)。
两个 pump lemma 的共同点
对于 RL 的,\(xy\) 就是 center,\(y\) 就是 loop。 对于 CFL 的,不妨称 \(vwx\) 为 center,\(vx\) 为 loop。
Center 一定不长于某常数,loop 一定非空。
Chomsky 范式以及转换方法¶
Chomsky 范式只包含下面三个:
- \(A \to BC\)
- \(A \to \alpha\)
- \(S \to \varepsilon\)
这里的
- \(A\), \(B\) 和 \(C\) 是非终结符
- \(B\) 和 \(C\) 都不可以是开始符号
- \(\alpha\) 是终结符(表示常量值的符号)
- \(S\) 是(非终结符的)开始符号
- \(\varepsilon\) 是空串
如何将任意 CFG 转换成 Chomsky 范式呢?
转换方法¶
1. 添加开始变元及规则
- 添加一个新的开始变元 \(S_0\)。
- 添加规则 \(S_0 \to S\),其中 \(S\) 是原始的开始变元。
2. 消除所有的 \(\varepsilon\) 规则
除所有从变元到空字符的规则,例如 \(A \to \varepsilon\)。 - 特殊情况:如果空字符是语言中合法的(即可以由 \(S_0\) 推导 \(\varepsilon\)),保留该可能性,但其他变元的 \(\varepsilon\) 规则需消除。
3. 消除所有的 \(A \to B\) 规则
- 消除所有形式为 \(A \to B\) 的规则,其中 \(A\) 和 \(B\) 都是单个变元。
- 保留从单个变元到多个变元或终结符的规则,例如 \(A \to BC\) 或 \(A \to aB\)。
4. 添加新的变元
- 对规则形如 \(A \to BCD\) 的情况:
- 转换为 \(A \to ED\),并添加新的规则 \(E \to BC\)。
- 如果 \(BC\) 的组合不符合 Chomsky 范式,再继续拆分,例如 \(E \to FG\)。
不可判定性¶
Rice's Theorem¶
定义(\(L(P)\)):\(P\) 是一个性质(比如“L(M) 为空”“L(M) 有限”等等),\(L(P)\) 是所有满足条件 \(P\) 的递归可枚举语言。
定理: \(L(P) \neq \emptyset \land L(P) \neq \textbf{All enumerable recursive languages} \implies \{M: M \text{ is Turing machine} \land L(M) \in L(P)\}\) 是不可判定的。
- 注意:\(M\) 是图灵机,\(L(P)\) 是满足条件 \(P\) 的语言,不要搞混(多个图灵机可以对应同一个语言)
Lemma: \(ALL_{TM}, E_{TM}, A_{TM}, EQ_{TM}\) 等等都不可被判定。
规约¶
不妨假设我们现在的规约都是在图灵机计算模型之下(对于 PDA、DFA 等等其它计算模型,也可类比):
存在 A 到 B 的规约,就相当于:\(\exists f \text{ computable}, \forall x: x \in A \iff f(x) \in B\)。
因此,为了判断 \(x\) 在不在 \(A\) 中,我们只需要将 \(f(x)\) 在 \(M_B\) 中跑一遍就行。显然,\(B\) 的难度至少和 \(A\) 相当,记为 \(A \preceq B\)。
因此,如果 \(M_B\) 具有怎样的能力,那么一定存在 \(M_A\) 存在这样的能力——只需要让 \(M_A\) 先运行 \(f\),然后再运行 \(M_B\) 即可。
例题:证明所有递归可枚举语言 \(A\),都可以规约到 \(H_{TM}\)
对于任意 \(A\),都有一个图灵机 \(M_A\) 半判定它。
我们不妨构造这样的机器 \(M_A^\omega\)(下面是它的伪代码):
然后,\(M_A\) 停机且为真(i.e. \(M_A \in H_{TM}\),当且仅当 \(w \in A\)。从而,我们令 \(f(w) = M_A^w\),就有 \(\forall w: w \in M_A \iff f(w) \in H_{TM}\)。也就是将 \(A\) 规约到了 \(H_TM\)。
几种 R 和 RE 的语言¶
\(A_{CFG} = \{\langle G, w \rangle: w \in L(G)\}\) is recursive¶
证明
很简单,我们将 CFG \(G\) 转换成等价的 Chomsky Normal Form (CNF),也即:
如果 \(w = \varepsilon\),那么 \(\langle G, w \rangle \in A_{CFG}\) 当且仅当 \(S \to \varepsilon \in G\)。
如果 \(w \neq \varepsilon\),那么我们的策略就是:
- 首先,将 \(S\) 不断使用某一个第三类规则进行延长,直到延长到 \(|w|\)。我们将分别尝试每一种延长的方式。
- 然后,将所有 symbol,试图通过第二类规则进行转换成 \(w\)。然后根据转换的成功与否,来决定 accept 还是 reject。
这样,我们就可以在有限时间内(其实还是指数时间内)模拟 \(A_{CFG}\)。从而必然停机,从而这个语言是 recursive。
\(E_{CFG} = \{G: \exists w: w \in L(G)\}\) is recursive¶
证明
我们可以直接把 CNF 规则变成逻辑:
\(G \in E_{CFG}\),当且仅当 \(G\) 中规则所代表的逻辑,最终可以推出 \(x_S\)。这个判定甚至是 \(\mathcal O(n)\) 的。
\(A_{TM}\) is recursively enumerate¶
证明
我们可以通过在通用图灵机上来模拟 \(A_{TM}\)。这个通用图灵机显然是 semi-decidable。
\(A_{TM}\) is NOT recursive¶
证明
通过证明 Rice's Theorem,这就是推论。
\(ALL_{PDA}\) is NOT recursive¶
证明
证明方法:将停机问题规约到 \(ALL_{PDA}\)。
思路:虽然 PDA 不能像图灵机一样计算,但是给出计算过程,PDA 可以判断这个计算过程是否 valid,以及最终是否 accept。
函数的可计算性¶
复杂度理论¶
交互式证明 (Interactive Proof System)¶
我们有一个 prover 和一个 verifier。假设是这样的:
- Prover is an oracle (i.e. has unlimited computation power), but can't be trusted
- Verifier has bounded computation power but can be trusted
- Usually we assume it's a probabilistic Turing Machine with polynomial time bound
下面两个性质是一个 interactive proof system 必须具备的:
- 完备性(completeness):如果 \(x \in L\),那么存在诚实的证明者 \(P\),使得 \(V\) 与 \(P\) 的交互之后,输出“\(x \in L\)”;
- 可靠性(soundness):如果 \(x \notin L\),那么对任意的证明者 \(P\),\(V\) 与 \(P\) 的交互之后,输出“\(x\in L\)”的概率很小(可以认为小于某一常数)。
有了这样的基础,我们就可以把 NP 问题变成 IP 问题的一个子类:
- \(V\) 和 \(P\) 事先约定一个多项式 \(l(|x|)\)
- \(V\) 和 \(P\) 接入到输入 \(x\)
- \(P\) 将解传输给 \(V\)。不论 \(P\) 传输多少个字符,\(V\) 只截取前 \(l(|x|)\) 个
- \(V\) 运行 \(M(x, w)\),accept iff \(x \in L\), reject iff \(x \notin L\)
NP-Complete Problems¶
SAT 问题(Satisfiability Problem)¶
定义: SAT 问题是一个逻辑问题,其目标是确定一个布尔公式是否可以通过某种变量赋值使其为真。
问题: 是否存在一个赋值,使得这个 SAT clause 为真
3-SAT 问题¶
定义: 3-SAT 是 SAT 问题的一个特例,其中公式被限制为三元子句的合取形式 (CNF,也就是 \((a \lor b \lor \lnot c) \land \dots\))。
问题: 是否存在一个赋值,使得这个 SAT clause 为真
Clique 问题¶
定义: Clique 问题涉及图论,目标是在一个无向图中找到一个完全子图,即图中的一个顶点子集,其中每两个顶点都直接相连。
问题: 是否存在一个(至少)包含 \(k\) 个 vertices 的完全子图?
Vertex Cover 问题¶
定义: Vertex Cover 问题也是一个图论问题,目标是在一个无向图中找到一个顶点覆盖集,即一个顶点子集,使得图中每条边至少有一个端点属于这个子集。
问题: 是否存在一个(至多)包含 \(k\) 个 vertices 的顶点覆盖?