计算理论

文章发布时间:

最后更新时间:

目录

1. 正规语言与有限自动机 (01-08)

这一部分涵盖了乔姆斯基谱系中的 3 型文法，是编译原理中词法分析的基础。

  • 语言基础

  • 有限状态机与有限状态自动机

  • 确定有限自动机 (DFA)

  • 非确定有限自动机 (NFA)

  • 正则语言的性质

  • 正则表达式

  • 正则文法

  • 正则语言泵引理及其示例

2. 上下文无关语言与下推自动机 (09-16)

这一部分涵盖了 2 型文法，主要用于描述编程语言的语法结构。

  • 上下文无关文法 (CFG)

  • 上下文无关文法的范式

  • 下推自动机 (PDA)

  • PDA 对上下文无关语言的识别

  • 确定性下推自动机 (DPDA)

  • 上下文无关语言的性质

  • 上下文无关语言泵引理及其示例

3. 图灵机与可判定性理论 (17-22)

这一部分探讨计算的极限，即哪些问题是计算机可以解决的，哪些是不可以的。

  • 图灵机基础与变体

  • 通用图灵机

  • 可判定性

  • 不可判定性

  • 可判定性归约

4. 计算复杂度与 NP 完全性 (23-27)

这一部分关注计算的效率，即解决问题需要多少时间资源。

  • 时间复杂度基础

  • NP 完全性 (NPC)

  • NP 完全性归约

  • 2-可满足性问题 (2SAT)

  • 更多 NPC 问题与近似算法

文法：

Vn一坨东西，Vt一个字母，"->"“可能为” S开始变元：最后的那一坨；句型：和s等价的所有一坨 推导：一个句型 =》另一个句型

nfa和正则

确定的有限状态自动机 dfa nfa 不确定 delta(q0,0) = {q0, q1} nfa转dfa：把所有{qi, ……}的状态都转一遍，并且只要包含之前结束状态就是结束状态

空-NFA （转移条件可能是空 空nfa转nfa：读 空*a空*到达的状态，所有读空*到终止的都是终止 dfa表示正则语言：把所有可能列出来。a+b或 a*b连接 a*闭包 正则语言的性质：（用dfa证明） 差集：所有状态的非可转移条件都指向终点

dfa化简：如果两个点等价（出度相同）就合起来

dfa相关判定：用另一个dfa交这个dfa，判断是不是空集

泵引理

对于正则语言 \(L\)，存在一个常数 \(p\)（泵长度）（p为状态个数），使得任何长度 \(|s| \ge p\) 的字符串 \(s\) 都可以拆分为三部分 \(s = xyz\)：

  1. \(|y| > 0\)：被重复的部分不能为空。

  2. \(|xy| \le p\)：循环发生在字符串的开头附近。

  3. 对于所有 \(i \ge 0, xy^iz \in L\)：无论你把中间的 \(y\) 重复多少次（包括 0 次，即删除它），得到的新串都必须在 \(L\) 中。

使用选一个和p有关的字符串，如\(s = a^p b^p\)，由|xy|<=p得y一定为……

CFG 上下文无关语法

派生树，最左派生，二义性（存在两个派生树生成一个句子） 两个cfg 并集，连接，闭包还是cfg

简化： 1. 去掉无用符号 - 从符号集开始倒推 \(若N推出T^*中的一个,N加入T\) - 在用这个集合里，从S开始推出所有有用符号 2. 去掉空产生式，把 A->sigma 融入其他产生式 A|sigma 3. 去单一产生式，推和被推都是一个符号（非终结符 - 如何是S->A，就把A的复制粘贴到S上

CNF 乔姆斯基范式（标准化 1. 化简CFG 2. 保留 A->一个终结符 3. S->Abc: S->ABC,B->b 4. A->ABCD: A->AE…… 派生长度n的字符串需要2n-1步

PDA：下推自动机可以看作是有限自动机加上一个栈。转移函数为：当前状态，pop出来的栈顶元素（空表示不pop），输入字符 -> {对栈顶修改，状态转移}所有可能性

d/n之中只有npda计算能力大于dpda，

CYK：用动态规划凑一个知道文法的上下文无关文法（CNF）中的一个字符串 dp[i][j]: 所有能够生成子串【i，j】的非终结符集合。分成【i，k】和【k+1，j】两个终结符。

泵引理

对于 CFL，字符串 \(s\) 被拆分为五部分 \(s = uvxyz\)：

  1. \(|vy| > 0\)：\(v\) 和 \(y\) 不能同时为空（至少有一个可以泵）。

  2. \(|vxy| \le p\)：中间待泵的部分不能太长。

  3. 对于所有 \(i \ge 0, uv^ixy^iz \in L\)：\(v\) 和 \(y\) 必须同步增加或减少。

例子 \(L = \{a^n b^n c^n \mid n \ge 0\}\)

  • 拆分 \(s = uvxyz\)：根据规则 \(|vxy| \le p\) 且 \(|vy| > 0\)。

    • 因为 \(|vxy| \le p\)，所以 \(vxy\) 这段长度有限的部分不可能同时包含 \(a\)、\(b\) 和 \(c\) 这三种字符（因为它们被分成了三块，每块长度都是 \(p\)）。

    • 这意味着 \(v\) 和 \(y\) 中只可能包含 \(\{a, b\}\)、\(\{b, c\}\) 或单一字符。

  • 泵起（Pumping）：我们令 \(i = 2\)，查看串 \(uv^2xy^2z\)。

    • 如果你增加（泵起）\(v\) 和 \(y\)，那么只会增加其中一两种字符的数量，而第三种字符的数量保持 \(p\) 不变。

    • 结果导致三个字符的数量不再相等，\(uv^2xy^2z \notin L\)。 证明两个数量增加，另一个不变

图灵机

读入字符（把这个字符变为，左移/右移） 实现加法和compare：3&4：11101111 -> 3+4=7 -> 1111111 ### 递归可枚举 (Recursively Enumerable) 这是乔姆斯基谱系中 0 型语言 的别称。它对应于能够被图灵机识别的所有语言。 接受/不接受/死循环

证明不同图灵机等价

多轨和多带，多轨还是标准，但是符号从单个字母变成了多个字母。 多轨模拟多带（n带），n*2个轨道，存每个轨道的磁头在哪里（0/1） 图灵机可以靠状态来记忆 q_remember_a_for_tape1。 ### 图灵机可判定语言（递归语言） 不能死循环 A_DFA 各种dfa -> 用dfa的性质转化为可接受or判定空 cfg：可接受or空 EQ_CFG不可判定 ### 不可判定的证明 对角化方法（）： 1. 证明“A_TM图灵机接受串”是不可判定的。反证，D<M>:非(H<M>:判定M接受串<M>); D<D>矛盾 反证： 2. 证明“tm停机“是不可判定的。反证：假设xx可判定，得到tm可判定 3. 证明“tm为空”不可判定。对于特定串w，构造M1拒绝除w之外的所有串，若输入为w模拟M（M1不空<=>M接受） 4. 证明“tm识别正则语言”不可判定。反证：构造M1，M1正则<=>M接受w - 若M不接受w，M1仅接受0n1n - 若M接受w，M1接受(0+1)n （注意不接受的情况比接受的情况少） 归约： tm停机，tm可判定 归约到 问题X可判定 构造M‘模拟M，且用问题X判定

\(A_{TM}\) 的不可判定性意味着其补集 \(\overline{A_{TM}}\) 必然是不可识别的。反证：非atm接受就不接受，atm接受就接受 ### 归约

复杂度

P多项式 NP所有能被非确定性图灵机在多项式时间内解决的问题集合 哈密顿：恰好路过每个点一次 团问题 (The Clique Problem)：判定一个给定的图中是否存在大小为 \(k\) 的完全子图（即每两个顶点之间都有边的子图） 布尔可满足性问题 (Satisfiability Problem / SAT)：2-CNF：(a||b)&&(a||c)&&(b||c)

NP完全 -》sat NP难 && NP = NP完全 证明NP完全：sat 多项式时间归约到 问题X， a+b = (a+c)^(b+~c)

3sat to clique：不同子句中的非矛盾符号连边，k是子句个数 图G:<V,E> v={d1,d2,d3}, e={(xi, yi)|} 复杂度|G|=|V| |E| 1. 构造 2. 正确性证明：<=> 3. 复杂度

  • 从 3-SAT 到 团问题 (Clique)：

    • 设计：将布尔表达式的子句转化为图中的顶点，将不矛盾的变量关系转化为边。 8888

    • 实现：证明原表达式可满足，当且仅当生成的图中存在大小为 \(k\) 的团。 9999

  • 从 团问题 到 独立集问题 (Independent Set)：

    • 设计：利用图的补图性质。 10101010

    • 实现：证明图 \(G\) 中的最大团即为其补图 \(\bar{G}\) 中的最大独立集。 11111111

  • 从 独立集问题 到 顶点覆盖问题 (Vertex Cover) 用点管住边：

    • 完成工作：证明在一个拥有 \(n\) 个顶点的图中，\(S\) 是独立集（s中两点之间没有边）当且仅当 \(V-S\) 是顶点覆盖（v-s可以覆盖所有边）。 12121212

  • 其他涉及的问题：

    • 哈密顿回路 (Hamiltonian Cycle) 与 旅行商问题 (TSP)。 13131313

    • 子集和问题 (Subset Sum)：证明在给定集合中寻找是否存在和为特定值的问题也是 NP完全的。 14 证明 2SAT 属于 P 类问题（多项式时间可解），而其优化版本 Max2SAT 是 NPC 问题 # TODO： 图灵机例题 递归定理 团的npc

≡