一个相当玄学的课，很多时候觉得自己充分理解了，结果全错了……

计算理论备忘

自动机与语言

正则语言

有穷自动机 DFA

• 语言描述
• 形式化定义：$(Q,\sum,\delta,q_0,F)$
• 接受的语言 $A=L(M)$
  • 正则语言
• 设计方法：把自己假想为机器
• 工具箱：正则运算——并、连接、星号
  • 正则语言在正则运算下封闭

非确定型 NFA

• 非确定型
  • 方便证明正则运算的封闭性
• 语言描述
• 形式化定义
• NFA=DFA
  • NFA 转 DFA 方法

正则表达式 REX

• 形式化定义
  • $\epsilon$ 和 $\emptyset$ 的区别
• $L(R)=L(M_{DFA})=(L_{NFA})$
  • R 转 NFA 办法

非正则语言

• 泵引理

  • 条件 1 中的 $i$可以为 0
  • 条件 3 在证明非正则性很有用

• 典型非正则语言

  • $\{0^n1^n|n\geq 0\}$
  • $\{\omega|\omega\text{中 0 和 1 的个数相等}\}$
  • $\{\omega\omega|\omega\in\{0,1\}^*\}$

上下文无关文法

上下文无关文法概述 CFG

• 形式化定义：$(V,\sum,R,S)$
  • 歧义性：最左派生
• 设计上下文无关文法：考察子串
• 乔姆斯基范式

下推自动机 PDA

• PDA=非确定型有穷自动机+栈
  • 非确定型下推自动机=上下无关文法
    • PDA 转 CFG
    • CFG 转 PDA
• 形式化定义：$(Q,\sum,\Gamma,\delta,q_0,F)$
  • 检验空串：$\$$
• 正则语言 $\in$ 上下文无关语言

非上下文无关语言

• 泵引理

  • 条件 1 中的 $i$可以为 0
  • 条件 3 在证明非上下文无关语言很有用

• 典型非上下文无关语言

  • $\{a^nb^nc^n|n\geq0\}$
  • $\{a^ib^jc^k|0\leq i \leq j\leq k\}$
  • $\{\omega\omega|\omega\in\{0,1\}^*\}$

可计算理论

丘奇——图灵论题

图灵机 TM

• TM=无限大容量存储+任意访问内部数据+有穷自动机
• 停机=接受/拒绝
• 形式化描述：$(Q,\sum,\Gamma,\delta,q_0,q_{accept},q_{reject})$
• 接受，除此之外拒绝或不停机——图灵可识别 $L(TM)$
• 接受，除此之外拒绝——图灵可判定

图灵机的变形

• 多带图灵机=单带图灵机
• 非确定型图灵机=确定型图灵机
• 图灵可识别的语言=能被枚举器枚举的语言

可判定性

可判定语言

• 可判定语言：$A_{DFA},A_{NFA},A_{REX},E_{DFA},EQ_{DFA}，A_{CFG},E_{CFG}$
  • A 接受串问题、E 空性质测试、EQ 判断是否为统一语言
  • $\text{正则语言}\subset\text{上下文无关的}\subset\text{可判定的}\subset\text{图灵可识别的}$

不可判定性

• 不可判定的：$A_{TM}$
  • 但是可识别
• 补图灵可识别
  • 可判定的语言=图灵可识别+补图灵可识别

可归约性

语言理论中的不可判定问题

• 不可判定的：$HALT_{TM},E_{TM}$

复杂性理论

事件复杂性

• 渐进记法：大 O
• 时间复杂性类：$TIME(t(n))$，$O(t(n))$ 的图灵机判定所有语言的集合
• 复杂性关系
  • $t(n)$ 多带图灵机=$t^2(n)$ 单带图灵机
  • $t(n)$ 非确定型单带图灵机=$2^{t(n)}$ 确定型单带图灵机
  • 模型为单带图灵机的时间复杂度类 $TIME(O(nlogn))$ 判定的语言都是正则语言

P 类

• P：确定型单带图灵机在多项式时间内可判定的语言类
  • 所有的上下文无关语言都是 P 的成员

NP 类

• NP：非确定型多项式时间图灵机 NTM 判定
  • 证明每一分支最多使用多项式个步骤

NP 完全性

• NP-complete：NPC 问题多项式时间可解，则所有的 NP 问题多项式时间可解

• NPC 问题：可满足性问题 SAT

• 多项式时间可归约：$A\leq_pB$，$\omega\in A \Leftrightarrow f(\omega)\in B$

  • NPC 证明：1. 属于 NP 2. 能够归约一个 NPC

• 库克-列文定理：SAT 是 NP 完全的

  • 3SAT 是 NP 完全的
  • HAMPATH 是 NP 完全的