计算理论知识纲要
Part Ⅰ 正则语言
有穷自动机
形式化定义
$$
(Q,\Sigma,\delta,q_0,F)
$$
分别表示字母表，状态集合，转移函数，起始状态，接收状态集合
正则语言
-
有穷自动机判定的语言叫做 正则语言。
-
正则语言在正则云算下是封闭的，包括并、连接和*
-
非确定性有穷自动机和确定性有穷自动机等价。因此，正则语言也可与被非确定性有穷自动机识别。
-
正则表达式是用正则运算构造的表达式，和有穷自动机具备等价性。
广义非确定有穷自动机
仅有一个起始状态和一个接收状态。形式化定义为$(Q,\Sigma,\delta,q_{start},q_{accept})$。分别表示字母表，状态集合，转移函数，起始状态，接收状态。
关于正则语言的泵引理
用于证明非正则语言。
若$A$是一个正则语言，存在一个泵长度$p$，使得，如果$s$是$A$中任一长度不小于$p$的串，那么$s$可以被分为$3$段，$s=xyz$，满足：
- 对于每一个$i \ge 0,xy^iz \in A$
- $|y| > 0$
- $|xy | \le p$
练习
- 给出语言，画出有穷自动机（例 ）
- 非确定性有穷自动机转为确定性有穷自动机（例1.16）
- 根据正则表达式转为非确定有穷自动机（例1.30，练习17，19，28）
- 确定有穷自动机转化为广义非确定有穷自动机。（练习1.21）
- 用泵引理证明不是正则的。（例题、练习1.29）
part Ⅱ 上下文无关文法
上下文无关文法的形式化定义
一个文法由一组替换规则组成，替换规则又称为产生式，符号称为变元，字符串由变元和终结符组成。终结符一般为大写字母。
正则语言 都可以用上下文无关文法表示。
乔姆斯基范式
形如：
$$
A \rightarrow BC
\newline
A \rightarrow a
$$
此外，允许$S \rightarrow \epsilon$
下推自动机
$$
(Q,\Sigma,\Gamma,\delta,q_0,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,\Sigma,\Gamma,\delta,q_0,q_{accept},q_{reject})
$$
分别是状态集、输入字母表、带字母表、转移函数、起始状态、接受状态、拒绝状态。
图灵可识别
可能会循环，或者接受，或者停机
图灵可判定
或者接受，或者停机
多带图灵机
多带图灵机和单带图灵机等价，可以转换。
非确定性图灵机
等价于确定性图灵机；
练习
-
给出图灵机和输入，模拟运行（例3.4，例3.5）
-
可判定问题的证明
-
确定性有穷自动机接受问题
-
非确定有穷自动机的接受问题
-
正则表达式的派生问题
-
确定性自动机、上下文无关文法的空性问题、等价性问题、派生问题
-
线性界限自动机（例5.8）
-
-
存在不能被任何图灵机识别的语言（例4.15）
-
图灵可识别，补可识别的语言，就是图灵可判定的（例4.16）
-
满映射、相同规模、对应的定义（4.10，4.12）
-
证明不可判定；假设可判定，构造图灵机，找到矛盾；
- 停机问题、空性问题、正则问题、等价性问题（5.1到5.4）
- 计算历史的定义、线性界限自动机的定义（接受性问题、空性问题）、可计算函数的定义、映射可规约的定义和相关结论。
Part Ⅳ 可计算性理论高级专题
递归定理
- 证明$A_{TM}$不可判定
MIN极小图灵机
- 定义
- 不是图灵可识别的
Part Ⅴ 时间复杂度
时间复杂度的定义
- 图灵机经过的最大的步数
大O计法的定义
- 由函数写出渐进函数。
时间复杂度类的定义
模型之间的关系，两个结论
- 多带图灵机和单带图灵机之间的复杂度关系
P和NP类相关
- P类的定义
- NP类的定义