Skip to content

重要知识点(复习)

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

JPEG图像-4C8F-A71A-70-0

相比 NFA 来说,这个 pushdown automaton

  1. 所有箭头处增加了 \(? \to ?\) 这一个标志,也就相当于,如果你希望走这一步,那么就必须在栈顶进行这样的变换
  2. 最后必须状态在 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 范式只包含下面三个:

  1. \(A \to BC\)
  2. \(A \to \alpha\)
  3. \(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\)(下面是它的伪代码):

def Maw():
    if Ma(w):
        return True;
    else:
        while (1);

然后,\(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),也即:

\[ \begin{aligned} S &\to \varepsilon \newline A &\to a \newline A &\to BC \end{aligned} \]

如果 \(w = \varepsilon\),那么 \(\langle G, w \rangle \in A_{CFG}\) 当且仅当 \(S \to \varepsilon \in G\)

如果 \(w \neq \varepsilon\),那么我们的策略就是:

  1. 首先,将 \(S\) 不断使用某一个第三类规则进行延长,直到延长到 \(|w|\)。我们将分别尝试每一种延长的方式。
  2. 然后,将所有 symbol,试图通过第二类规则进行转换成 \(w\)。然后根据转换的成功与否,来决定 accept 还是 reject。

这样,我们就可以在有限时间内(其实还是指数时间内)模拟 \(A_{CFG}\)。从而必然停机,从而这个语言是 recursive。

\(E_{CFG} = \{G: \exists w: w \in L(G)\}\) is recursive

证明

我们可以直接把 CNF 规则变成逻辑:

\[ \begin{aligned} S &\to \varepsilon : x_S\newline A &\to a : x_A\newline A &\to BC: x_B \land x_C \to x_A \end{aligned} \]

\(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 的顶点覆盖?