计算理论知识纲要

Posted on Edited on

Part Ⅰ 正则语言

有穷自动机

形式化定义

(Q, Σ, δ, q0, F)

分别表示字母表，状态集合，转移函数，起始状态，接收状态集合 ### 正则语言

  • 有穷自动机判定的语言叫做 正则语言。

  • 正则语言在正则云算下是封闭的，包括并、连接和*

  • 非确定性有穷自动机和确定性有穷自动机等价。因此，正则语言也可与被非确定性有穷自动机识别。

  • 正则表达式是用正则运算构造的表达式，和有穷自动机具备等价性。

广义非确定有穷自动机

仅有一个起始状态和一个接收状态。形式化定义为(Q, Σ, δ, qstart, qaccept)。分别表示字母表，状态集合，转移函数，起始状态，接收状态。

关于正则语言的泵引理

用于证明非正则语言。

若A是一个正则语言，存在一个泵长度p，使得，如果s是A中任一长度不小于p的串，那么s可以被分为3段，s = xyz，满足：

  1. 对于每一个i ≥ 0, xyiz ∈ A
  2. |y| > 0
  3. |xy| ≤ p

练习

  • 给出语言，画出有穷自动机（例 ）
  • 非确定性有穷自动机转为确定性有穷自动机（例1.16）
  • 根据正则表达式转为非确定有穷自动机（例1.30，练习17，19，28）
  • 确定有穷自动机转化为广义非确定有穷自动机。（练习1.21）
  • 用泵引理证明不是正则的。（例题、练习1.29）

part Ⅱ 上下文无关文法

上下文无关文法的形式化定义

一个文法由一组替换规则组成，替换规则又称为产生式，符号称为变元，字符串由变元和终结符组成。终结符一般为大写字母。

正则语言 都可以用上下文无关文法表示。

乔姆斯基范式

形如： $$ A \rightarrow BC \newline A \rightarrow a $$ 此外，允许S → ϵ

下推自动机

(Q, Σ, Γ, δ, q0, F)

分别表示状态集、输入字母表、栈字母表、转移函数、起始状态、接受状态集。

上下文无关文法与下推自动机对应。具有等价性。

泵引理

对于一个上下文无关语言，存在一个p，使得A中任意长度不小于p的s能够分为5段，s = uvxyz，满足： $$ 对于i \ge 0,uv^ixy^iz \in A \newline |xy| \gt 0 \newline |vxy| \le p $$

练习

  • 将上下文无关文法转化为等价的下推自动机
  • 利用泵引理证明（练习2.32）

Part Ⅲ 可计算性理论

图灵机

形式化定义

(Q, Σ, Γ, δ, q0, qaccept, qreject)

分别是状态集、输入字母表、带字母表、转移函数、起始状态、接受状态、拒绝状态。

图灵可识别

可能会循环，或者接受，或者停机

图灵可判定

或者接受，或者停机

多带图灵机

多带图灵机和单带图灵机等价，可以转换。

非确定性图灵机

等价于确定性图灵机；

练习

  • 给出图灵机和输入，模拟运行（例3.4，例3.5）

  • 可判定问题的证明

    • 确定性有穷自动机接受问题

    • 非确定有穷自动机的接受问题

    • 正则表达式的派生问题

    • 确定性自动机、上下文无关文法的空性问题、等价性问题、派生问题

    • 线性界限自动机（例5.8）

  • 存在不能被任何图灵机识别的语言（例4.15）

  • 图灵可识别，补可识别的语言，就是图灵可判定的（例4.16）

  • 满映射、相同规模、对应的定义（4.10，4.12）

  • 证明不可判定；假设可判定，构造图灵机，找到矛盾；

    • 停机问题、空性问题、正则问题、等价性问题（5.1到5.4）
    • 计算历史的定义、线性界限自动机的定义（接受性问题、空性问题）、可计算函数的定义、映射可规约的定义和相关结论。

Part Ⅳ 可计算性理论高级专题

递归定理

  • 证明ATM不可判定

MIN极小图灵机

  • 定义
  • 不是图灵可识别的

Part Ⅴ 时间复杂度

时间复杂度的定义

  • 图灵机经过的最大的步数

大O计法的定义

  • 由函数写出渐进函数。

时间复杂度类的定义

模型之间的关系，两个结论

  • 多带图灵机和单带图灵机之间的复杂度关系

P和NP类相关

  • P类的定义
  • NP类的定义