Skip to content

计算理论

  • 三种证明方法：数学归纳法、鸽巢原理、对角化
  • 字母表 \(\Sigma\) 和字符串都是有限的
  • 当 \(\Sigma=\emptyset\) 时，还是存在非空的语言 \(L=\{e\}\)
  • 根据 NFA 构造等价的 DFA
  • 正则语音在 并、拼接、\(*\)、补、交 运算下是封闭的
  • 正则语言 \(L\) 中所有字符串的反转构成的集合 \(L^R\) 也是正则语言（可通过构造 NFA 证明）
  • 单个正则语言是可数的（语言 \(L \subseteq \Sigma^*\) ，若 \(\Sigma\) 有限，那么 \(\Sigma^*\) 就是可数的）
  • 所有正则语言构成的集合也是可数的
  • 回文语言不是正则语言（但它是上下文无关语言）
  • 对正则语言进行无限次的并/交/拼接运算无法保证结果的正则性

  • (pumping theorem) 存在整数 N，对于所有长度大于 N 的字符串 w，都可以提取重复结构，且重复结构的数量可以任意变化

  • 规则集合: \((V-\Sigma) \times V^*\) 的有限子集

  • CFG 的解析树能够表示推导的等价类
  • 交换使用规则的先后顺序，产生一个偏序关系，且这两个推导是相似的，于是可以构造一个等价类
  • 最左推导：在偏序关系中最大的，即每次都选择最左边的非终结符进行替换（中序遍历）

  • ambiguous：不同的解析树生成相同的 \(w\)，有些语言只能用二义文语法来描述

  • PDA 的转移关系 \(\Delta\)：\((K \times (\Sigma \cup \{e\}) \times \Gamma^*) \times (K \times \Gamma^*)\) 的有限子集

    • K 为状态
    • \(\Sigma\) 为输入字母表
    • \(\Gamma\) 为栈字母表
    • 左边是读取的字符（或不读取）和要弹出的字符串，右边是要压入的字符串
  • PDA 的配置定义为 \(K \times \Sigma^* \times \Gamma^*\) 的一个成员，表示栈中所有的字符
    • 假如有配置 \((q,w,abc)\)，那么 \(a\) 在栈顶， \(c\) 在栈底
  • 上下文无关语言在 并、拼接和\(*\)上是封闭的
  • 上下文无关语言在补和交上不是封闭的

  • 上下文无关语言和正则语言的交集是上下文无关语言

  • 图灵机（原始）的纸带只有一遍无限

  • 图灵机的配置：状态、纸带上的字符、纸带上的位置
  • 所有配置均假设为从左端符号开始，且从不以空符号结尾，除非当前就扫描到了空符号
  • 复合图灵机的例子： 该机器从 \(M_1\) 的初始状态开始，先由 \(M_1\) 操作，直到其停机 若停机时，当前扫描到的符号为 \(a\) ，那么就启动 \(M_2\) 并以 \(M_2\) 完成后续操作；若扫描到的符号为 \(b\) ，那么就启动 \(M_3\) 并以 \(M_3\) 完成后续操作
  • M 在输入 \(w\) 上的初始配置(initial configuration) 为 \((s, \rhd, \sqcup w)\)，读写头在空格上
  • 递归可枚举：若停则接受，也称半判定

  • 递归语言的补也是递归的

  • 图灵机的拓展：多条、多头、两路无限纸带、多维

  • NTM:

    • 如果停机，称接受了 \(w\)；半判定
    • 存在 \(N\) 依赖于 \(M\)、\(w\)，\(N\) 步内停机；判定

  • 无限制文法的规则： \((V^* (V-\Sigma) V^*) \times V^*\) 的有限子集

  • 当且仅当语言是递归可枚举时，它由文法生成

  • 由 \(S wS\) 生成的 \(f(w)\) 是文法可计算的

  • 基础函数：

    • 零函数
    • 后继函数
    • 投影函数
  • 基础函数 + 复合 + 原始递归 = 原始递归函数
  • 按情况定义的函数（谓词）也是原始递归函数

  • 最小化：计算满足条件的最小整数

  • 递归可枚举语言类在补操作下不封闭