计算理论基础复习笔记

待更新

预备知识与基本文法理论（讲义第一章、第二章）

第一章大部分内容在其他课程里讲过了，新的内容只有：

前缀性质：L 中任何字符串都不是另一个字符串的真前缀

第二章讲了文法的基本概念。

文法 $G$ 是四元组 $(V, T, P, S)$， V 是变元的有限集，T 是终结符有限集，P 是生成式有限集， S 是开始符号。

=> 关系为直接派生，多步直接派生为派生。

文法 $G$ 产生的语言 $L(G)$ 是 S 派生出来的终结符号串的全体。

0型文法（短语结构文法 PSG ）：对生成式无限制。

1型文法（上下文有关文法 CSG ）：每个生成式左侧长度≤右侧长度

1°型文法（上下文有关文法的另一种形式）：每个生成式，左侧至少包含一个变元，删去该变元后的前缀与后缀（可为空）也是右侧的前缀与后缀。$\alpha_1A\alpha_2 \rightarrow \alpha1\beta\alpha_2, \beta不为空$，前缀$\alpha_1$和后缀$\alpha_2$即为上下文。

2型文法（上下文无关文法 CFG ）：每个生成式左侧仅包含一个变元

3型文法（正规文法 RG ）：每个生成式左侧仅包含一个变元，且右侧必须形如 $a$ 或 $aB$ ，$a \in T \ 或a为空串$

将1型文法转为1°型文法：

1. 对所有终结符$a$，添加变元$[a]$。
2. 将原有生成式中所有终结符替换为对应新变元（如将$a$替换为$[a]$）。此时，所有生成式都只含变元。
3. 对所有终结符$a$，添加生成式$[a]\rightarrow a$。
4. 对所有不符合1°型文法的生成式，若左侧为$A_1A_2\ …\ A_n$，右侧为$B_1B_2…B_m$ ，则添加$n$个变元，用新的 $2n$ 个生成式替换这个生成式。新的生成式中：
   • 第 $i+1$ 个生成式的左侧是第 $i$ 个生成式的右侧；
   • 前 $n$ 个生成式将 $A_1A_2…A_n$ 逐渐替换为 $C_1C_2…C_n$，每个生成式替换一个最靠前的 $A$（第一个生成式为$A_1A_2…A_n\rightarrow C_1A_2…A_n$）；
   • 接下来的 $n-1$ 个生成式将 $C_1C_2…C_n$ 逐渐替换为 $B_1B_2…B_{n-1}C_n$， 每个生成式替换一个最靠前的 $C$ （第 $n+1$个生成式为$C_1C_2…C_n\rightarrow B_1C_2…C_n$）；
   • 最后的生成式将 $C_n$ 替换为 $B_nB_{n+1}…B_m$ 。

2型文法的派生树：根节点为 S ；内部节点为变元；某个节点（有标记A）的孩子从左到右收集而成的字符串s，必有$A\rightarrow s$属于生成式集合（对应直接派生）；边缘是叶子节点从左到右收集而成的字符串（对应派生）。派生树可对应一个字符串从 S 开始的派生过程。

最左派生：派生过程每一步都只替换最左边的变元。（同理有最右派生）

多义：某个字符串有两种不同派生过程。

有穷自动机、正规表达式、正规集（讲义第三、四章，MIT教材第一章）

有穷自动机 （FA） 是五元组 $(Q,\Sigma,\delta,q_0,F)$，分别对应：有穷状态集、有穷输入字符表、转移函数、初始状态、终结状态集。

转移函数的输入为单个字符，可扩充为字符串。

FA 接收的字符串 s ：以 s 作为 FA 的输入，状态从初始的 $q_0$ 转移到 F 里的状态。

几种转换

1. $DFA \rightarrow Regular\ Expression$

   讲义上的方法是：

   • 如果有 $k$ 个状态，算出 $k^3$ 个正规表达式 $r_{ij}^k$，表示输入串使状态机从状态 i 到 j 中间不经过编号高于 k 的状态。

   • $k = 0$ 时，状态图中若有从状态 i 到状态 j 的箭头，就把箭头上的字符加到集合里。$i == j$ 时，这个集合里还要包含空串。

   • $k \ne 0$ 时，有递推式 $r_{ij}^k = r_{ik}^{k-1}(r_{kk}^{k-1})^*r_{kj}^{k-1} \cup r_{ij}^{k-1}$

   MIT 教材上的方法是：

   • 将 DFA 转为 GNFA （GNFA的转换条件可以是正规表达式）：添加两个状态 s 和 t ，s 为新的初始状态，t 为新的终结状态。s 通过 $\epsilon$ 动作到原有的每个初始状态，原有的每个终结状态通过 $\epsilon$ 动作到 t
   • 将 GNFA 的状态数缩减到2：下面的 RE 三种四句的反向操作，可将状态数减1
   • 将 2-state GNFA 转换为 RE：转换条件即为所求

2. $Regular Expression \rightarrow \epsilon-NFA$

   处理三种类型的子句即可。讲义 p65-p66 的三张图

   • $r_1+r_2$：两路分叉、两路归并
   • $r_1r_2$：前面的终结状态指向后面的初始状态
   • $r_1^*$：终结状态回到初始状态

3. $\epsilon-NFA \rightarrow NFA$

   讲义 p59

   先检查 $q_0$ 是否为终结状态。

   转移函数取一个闭包。

4. $NFA \rightarrow DFA$

   讲义 p55

   NFA 中，$\delta(q, a)$ 的结果是一个状态集。建立状态集到状态元组双射，把状态元组看作一个新的状态。将状态元组作为 $\delta$ 的输入，结果为元组中状态作为输入的结果的并集。一直做下去，直到不产生新的状态。

正规文法转为 $\epsilon-NFA$：

• 每个变元为状态，每个终结符为输入字符
• 转移函数的输入：派生左侧的变元、派生右侧的终结符（或 $\epsilon$）；输出为派生右侧的变元（或终结状态）

DFA 转为正规文法：同上。

缩胀定理

正规集缩胀定理：A 是正规集，则存在 p (pumping length) 使长度大于等于 p 的 A 中任意 s，可拆成三部分 $s=xyz$，满足：

• $xy^iz\in A, \forall i \ge 0$
• $|y| \gt 0$
• $|xy|\le p$

（讲义上的定理给 s 和 $xy^iz$ 加了前缀和后缀，移去了最后一个限制。）

正规集在并、连接、闭包运算（由正规表达式的定义）、补运算（终结状态取补）、交运算（两个 DFA 的状态集、终结状态集取笛卡尔积）、商运算（ 在 R1/R2 中，R1 状态集为 Q，建立 |Q| 个 DFA，分别以 Q 中每个状态为初始状态，检测这些 DFA 交 R2 是否为空）下封闭。这些性质可以用来判定某个集合 C 不是正规集：取已知正规集 A 和已知非正规集 B，使 A 和 C 在某种封闭运算下变为 B，则 C 不是正规集。

一些判定问题：具有 n 个状态的 FA 有以下性质

• 接受集合非空，iff 接受一个长度小于 n 的串
• 接受集合无穷，iff 接受一个长度在 [n, 2n) 之间的串
• 是否为空、是否无穷、是否等价 是可判定的

极小化算法

状态的等价：$\forall x \in \Sigma^*, \delta(p,x)\in F\ \leftarrow \ \delta(q,x)\in F$

商自动机：状态集是 Q 的各等价类；自动机和它的商自动机等价

极小化算法：

• 对所有状态对 {p, q} 画一个下三角矩阵
• 对 $p\in F,q\notin F$ 的 ${p, q}$，在相应位置做标记
• 重复此步直到矩阵不再变化：$\exists a\in\Sigma,{\delta(p,a),\delta(q,a)}$ 被标记，则标记 $(p,q)$
• 没被标记的状态对是等价的

Myhill-Nerode 定理

两个 DFA 同构：状态集存在双射，且满足一些性质

右不变：对于等价关系 R，xRy 可推出 xzRyz

关于集合 A 的 Myhill-Nerode 关系：右不变、细分A、具有有穷指数

DFA 与 Myhill-Nerode 的关系：

• DFA M $\rightarrow$ Myhill-Nerode 关系 $R_M$：$xR_My\leftarrow\delta(q_0,x)=\delta(q_0,y)$

• Myhill-Nerode 关系 $\rightarrow$ DFA $M_R$ : $Q = {[x]|x\in\Sigma^*}, q_0 = {[e]}, F = {[x]|x\in A}, \delta([x],a)=[xa]$，有 $L(M_R) = A$

反复横跳：

• $R_{M_R}=R$，R 是 Myhill-Nerode 关系
• $M_{R_M}$ 同构于 $M$，M 是 FA

等价关系 $R_A$：$xR_Ay:\forall z\in\Sigma^*,xz\in A \leftarrow yz \in A$. $R_A$ 右不变、细分 A

Myhill-Nerode定理：

• 正规集有一个 Myhill-Nerode 关系 $R_M$
• 若 A 有 Myhill-Nerode 关系，则 $R_A$ 有有穷指数
• 若 $R_A$ 有有穷指数，则$R_A$ 是 $Myhill-Nerode$ 关系，构造 $M_{R_A}$ 接受 A

$M_{R_A}$ 是状态数最少的。

归纳：判定某个集合不是正规集

• 缩胀定理
• 利用封闭运算
• 集合的关系 $R_A$ 没有有穷指数

上下文无关文法、下推自动机（讲义第五、六章，MIT教材第二章）

化简 CFG

无用符号：$X\in V\cup T$ 但 $X$ 不出现在 S 派生出的字符串中；$X\in V$ 但 X 不能派生任何终结符号串

消去无用符号的步骤：

• 先消去 (2) 类无用符号（引理5.1）：构造新的 $V’$ ，若生成式 $A\rightarrow X_1X_2…X_n$ 右侧的每一 $X_i \in T^*\cup V’$，则把 A 加到 $V’$ 中。
• 再消去 (1) 类无用符号（引理5.2）：构造新的 $V’$ 和 $T’$，首先将 S 放入 $V’$ 中，若某个生成式左侧的变元属于 $V’$，则将该生成式右侧的变元放入 $V’$ 中，终结符放入 $T’$ 中。

变元 A 可为零：A 可以派生空串

$\epsilon$-生成式：右端为空

消去 $\epsilon$-生成式（使 $L(G’) = L(G) -{\epsilon}$）的步骤：

• 确定可为零的变元集 Z：先把直接派生空串的变元放入 Z 中，然后检查右侧全为变元的生成式，若右侧变元全在 Z 中，则把该生成式左侧变元放入 Z 中。
• 构造新的生成式集合 $P’$：对 $P$ 中所有生成式，检查右侧的每一个符号，如果不属于 Z 则不改变，属于 Z 则改为 $\epsilon$ 或不改变（不改变的情况是防止修改后右侧全为 $\epsilon$）。
• 消去无用符号

单一生成式：左右端皆为一个变元

不含空串的 CFL，消去单一生成式的步骤：

• 构造新的生成式集合 $P’$：先将 $P$ 中非单一生成式放入 $P’$，对单一生成式 $A\rightarrow B$，如果 $B\rightarrow \alpha$ 是 $P’$ 中元素，则将 $A\rightarrow \alpha$ 放入 $P’$。
• 消去无用符号

CFG 范式

Chomksky 范式：每个生成式右侧为两个变元或一个终结符

不含空串的 CFL 转为 Chomsky 范式的步骤：

• 消去单一生成式、$\epsilon$-生成式和无用符号
• 如果某生成式右侧只有一个符号，则它一定是终结符
• 如果某生成式 $p$ 右侧同时包含变元和终结符，则对每个终结符 $a$，添加变元 $C_a$ 和生成式 $C_a \rightarrow a$ ，用这个变元替换掉 $p$ 右侧的对应终结符
• 此时，所有生成式除去形如 $A\rightarrow a$ 的，其他生成式右侧不含终结符。如果某个生成式仅包含 $m(m\ge 2)$ 个变元，则添加 $m-2$ 个变元和若干个生成式，使每个生成式右侧仅含2个变元。如 $A\rightarrow B_1B_2B_3$ 可拆成 $A\rightarrow B_1D_1, D_1 \rightarrow B_2B_3$

Greibach 范式：每个生成式右侧的第一个符号为终结符

不含空串的 CFL 转为 Greibach 范式的步骤：

• 转为 Chomsky 范式
• 对变元进行编号。保证每个形如 $A_k \rightarrow A_j\alpha$ 生成式右侧的第一个变元编号 $A_j$ 大于左侧变元，如果不大于则用已检查过的 $A_j \rightarrow A_m\alpha$ 替换，这样右侧第一个变元的编号严格递增，这一步可以在有限次数内完成。如果遇到 $A_k \rightarrow A_k\alpha$ 则加入新的生成式 $B_k \rightarrow \alpha,\ B_k \rightarrow \alpha B_k,\ A_k \rightarrow \beta B_k$，对一切已有的 $A_k \rightarrow \beta$
• 处理 $A_i \rightarrow A_j \gamma\ ,j>i$。左部变元编号从大到小开始处理：编号为最大时，生成式右侧第一个符号必为终结符；其他情况，右侧第一个变元用已有生成式代入，代入后编号递增，达到编号最大时，再代入一次，右侧第一个符号也变为终结符。
• 处理以新加入的 $B_i$ 变元为左部的生成式。其右侧第一个符号只可能是是终结符或 $A_j$，出现后者时再做一次编号递增即可。

下推自动机

下推自动机 PDA 是七元组 $(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$，比 DFA 多了 $\Gamma$ 有穷的栈符号表，$Z_0$ 栈底符号。

转移函数的形式是 $\delta(q,a,Z) = {(p_1,\gamma_1),…,(p_m,\gamma_m)}$，表示当状态为 q，读入字符 a，且栈顶为 Z 时，将状态改为 p，栈顶改为 $\gamma$。

瞬时描述 ID 是三元组 $(q,w,\gamma)$，w 为未读过的输入，$\gamma$ 为栈中符号串（左侧为栈顶）。$(p_1,\gamma_1) \in \delta(q,a,Z)$ 可表示为 $(q,aw,Z\alpha) \vdash (p_1, w, \gamma_1\alpha)$

L(M) 是 M 按终结状态方式接受的语言，N(M) 是 M 按空栈方式接受的语言。它们是等价的。

已知 $M_1$， 构造 $M_2$ 使 $L(M_1) = N(M_2)$：

• 添加两个状态 $q_e, q_0’$，$q_e$为接受完毕并准备清空栈，$q_0’$为新的初始状态。添加栈符号 $X_0$ 作为栈底符号
• 初始：$\delta’(q_0,\epsilon,X_0)={(q_0,Z_0X_0)}$，$Z_0$ 为 $M_1$ 栈底符号
• 终结：$\delta’(q,\epsilon,Z)包含(q_e,\epsilon)$，当 q 是终结状态，并清空栈：$\delta’(q_e,\epsilon,Z)={(q_e,\epsilon)}$

已知 $M_1$， 构造 $M_2$ 使 $N(M_1) = L(M_2)$：

• 添加新的初始状态、终结状态、栈底符号
• 初始：状态改为 $M_1$ 的初始状态，将 $M_1$ 的栈底符号压入栈
• 终结：当栈顶符号为 $M_2$ 栈底符号是，说明栈为空，如果没有输入了，就转至终结状态

已知 CFL L，构造 PDA M 使 $L = N(M)$：

• 若 L 接受空串，则加上 $\delta(q,\epsilon,S) = {(q,\epsilon)}$
• 除去空串，设 G 为产生 L 的 Greibach 文法，构造转移函数：若 $A\rightarrow a\gamma\in P$ 则 $\delta(q,a,A) 包含 (q,\gamma)$

已知 PDA M， 构造 CFL L 使 $L=N(M)$：

• 构造 $V={[q,A,p]|q,p\in Q,A\in\Gamma}\cup{S}$
• 初始：$S\rightarrow [q_0,Z_0,q], q \in Q$
• 当 $\delta(q,a,A)包含(q_1,B_1B_2…B_m)$ 则有 $[q,A,q_{m+1}]\rightarrow a[q_1,B_1,q_2][q_2,B_2,q_3]…[q_m,B_m,q_{m+1}]$。

缩胀定理

基础版：

$\forall k\ge 0,\exists z\in L, |z| \ge k, z = uvwxy, |vx|\ge 1,|vwx|\le k, \exists i \ge 0, uv^iwx^iy \notin L$， 则 L 不是 CFL。

步骤：

• 拆成5份
• 中间部分不超过k，要扩展的部分不都为空
• 将第2、4部分进行复制，或删除

Ogden 定理：

若 L 是 CFL，存在 $k\ge 0$，对每个 $z\in L, z=uvwxy$，在 z 中标出 $\ge k$ 个特别符号，使：vx 至少包含一个特别符号、vwx 最多包含 k 个特别符号。

CFL 在并、连接、闭包运算下封闭，在交、补运算下不封闭（不可判定）。

CFG 接受的语言是否为空、是否有穷的问题可判定。

成员资格问题的 CYK 算法：

• 将 CFG 转为 Chomsky 范式。记 $x_{ij}$ 为 $x.substr(i,j)$。
• 判别 $x_{ij}$ 可由哪些变元派生，从 $j=1\ to\ n$ 依次判别。
  • 当 j = 1 时，可由生成式得出。
  • 当 j > 1 时，A 可派生出 $x_{ij}$，当且仅当 $\exists A\rightarrow BC$ 且 B 派生 $x_{ij}$ 的前一段，C 派生 $x_{ij}$ 的后一段。

图灵机、递归集、不可判定性（讲义第七、八章）

确定的单带图灵机 TM 是9元组 $(Q,\Sigma,\Gamma,左端标记,空白符号,\delta,初始状态,接受状态,拒绝状态)$

$\delta(p,a)=(q,b,R)$

瞬时描述 ID 为 $\alpha_1 q \alpha_2$，（读写头左侧，状态，读写头及其右侧）

完全的图灵机：对一切输入都能停机

图灵机接受的语言：递归可枚举集（r.e.）

完全图灵机接受的语言：递归集

图灵机的构造技术

• 有限控制器中的存储：状态可以是 n 元组
• 移动：将带上符号吸收到状态上
• 多道技术：每个带符号是 n 元组
• 查讫符号：带符号是2元组 (字符，标记)
• 子程序技术
  • 调用：转到子程序的初始状态
  • 返回：到达子程序的返回状态

图灵机的类型

• 双向无限带
• 多带
• 非确定
• 双栈
• 带字母最少
• 枚举器

递归集与不可判定问题

	递归集	递归可枚举
补	封闭	如果 L 和 L 的补是递归可枚举的，它们是递归的
并	封闭	封闭
交	封闭	封闭

通用图灵机 U 是能模拟任何图灵机的图灵机

$L(U)={M#x|x\in L(M)}$，#为分隔符

任意给定的 TM M 对任意给定的输入串 x 是否停机的问题是不可判定的。

对任意给定的 TM M 和输入串 x，M 是否接受 x 的问题是不可判定的。

给定一个 TM M，它是否接受空串的问题是不可判定的。

A 到 B 的归约：存在函数 f，$x\in A \leftarrow f(x) \in B$，记 $A\le_m B$，m 表明归约是多对一的。

若 $A\le_m B$：

• B 是 r.e. => A 是 r.e.
• B 是递归集 => A 是递归集

性质 是一个映射：定义域是 $\Sigma^*$ 的 r.e. 子集，值域是 {True, False}

平凡性质：映射只取 True 或 False

Rice 定理：r.e. 集合类的任一非平凡性质都是不可判定的。