天塌了（
| 章节列表 |
|---|
| 集合，关系和语言 |
| 有限自动机 |
| 上下文无关语言 |
| 图灵机 |
| 不可判定性 |
| 语言 | 自动机 |
|---|---|
| 正则语言 | 确定性/非确定性有限自动机 |
| 上下文无关语言 | 下推自动机 |
| 递归可枚举语言 | 图灵机 |
TODO list
- primitive recursive function
- automata encoding
- simple TMs (elementary Turing Machine)
- 证明语言递归、递归可枚举
- 规约
- 判定递归语言
- CFG 2 PDA
- chomsky hierachy
14 - 15年考卷
选择题答案已经修正
判断题
(a)
False
(b)
False
\(\{a^ib^jc^k|i,j,k\in\mathbb{N}~\mathrm{and}~i+j\not\equiv k~(\mod3)\}\)
(c)
True
regular与non-regular并运算
(d)
False
正则的子集不一定正则
(e)
True
\(\{xcy|x,y\in\{a,b\}^*~\mathbb{and}~|x|\le|y|\le2|x|\}\) is context-free
(f)
False
?
(g)
True
(h)
False
半判定，因为没说对不接受的串能否停机
(i)
False
?
(j)
True
(k)
True
(l)
True
简答题
1
(a)
No
take \(a^{2n}ca^n\),
复习PPT考点
- 正则语言
- DFA / NFA => regex
- regex => DFA / NFA
- 判断一个语言是否正则
- 是：DFA / NFA / closure property
- 否：closure property / pumping theorem
- 上下文无关语言
- context-free lang => grammar
- grammar => PDA
- lang => PDA
- 判断一个语言是否上下文无关
- 递归可枚举语言
- 设计图灵机计算一个函数 / 判定 半判定语言
- TM => function
- 判断函数是否为 primitive recursive function
- 不可判定性
- 判断语言递归可枚举 / 不递归
- 乔姆斯基层次（此条与下述来自更以前的PPT）
- 邱奇图灵论题
- 通用图灵机
- 停机问题
- 一些不可判定的问题
- P与NP
- 判断语言属于P问题还是NP问题
- NP完全
- show a given lang be NP-complete by reduction
知识点
Chomsky Hierarchy
- 0型
- 1 - 上下文相关
- 2 - 上下文无关
- 3 - 正则
下推自动机
六元组 \(M=(K,\Sigma,\Gamma,\Delta,s,F)\)
- \(K\) 状态集合
- \(\Sigma\) 输入字母表
- \(\Gamma\) 栈字母表
- \(s\in K\) 初始状态
- \(F\subseteq K\) 终结状态集
- \(\Delta\) 转移函数
\(\Delta=\{((p,\alpha,\beta),(q,\gamma))\}\)
- \(p\) PDA 当前的状态
- \(\alpha\) 读入的字母
- \(\beta\) 栈顶的元素
- \(q\) 要转移到的状态
- \(\gamma\) 将栈顶的元素修改到的元素
接受条件：
- 处理完输入，栈为空
- PDA 到达终结状态（之一）
图灵机
五元组 \(M=(K,\Sigma,\delta,s,H)\)
- \(K\) 状态集合
- \(\Sigma\) 输入字母表
- \(\sqcup\) 为空符号
- \(\rhd\) 为纸带最左端
- \(s\in K\) 初始状态
- \(H\subseteq K\) 停机状态集
- \(\delta\) 转移函数
\(K=\{(q,w\underline au)\}\)
这里与张海的复习笔记有出入，后者记这个集合是 \(\delta\)。
Context Free Grammar 上下文无关语法
\(G=(V,\Sigma,R,S),R=\{A\to u\}\)
其中：
- \(V\) 为字母表
- \(\Sigma\subseteq V\) 为终结符号的集合
- \(S\in V-\Sigma\) 为起始符号
- \(R\) 为规则，是\((V-\Sigma)\times V^*\) 的子集
Chomsky Normal Form
\[ S\to\epsilon \\ A\to a \\ A\to BC \]
CFL to CFG
手动构造。
常见例子就是回文，两种字母个数相等，字母个数有等式或者不等式限制等等。
CFL to PDA
也只能手动构造，同上。
CFG to PDA
\(G=(V,\Sigma,R,S)\)
\(M=(K,\Sigma,\Gamma,\Delta,s,F)\)
给出文法 \(G\)，则 PDA 的参数可定义为：
- \(K=\{p,q\}\)
- \(\Gamma=V\)
- \(s=p\)
- \(F=\{q\}\)
- \(\Delta\) 包括以下三种变换：
- \(((p,e,e),(q,S))\) 接受
- \((q,e,A),(q,x)\) 生成, for each rule \(A\to x\in R\)
- \(((q,a,a),(q,e)), \forall a\in\Sigma\) 匹配
对于正则语言的泵定理
Let \(L\) be a regular language, then there exists an integer \(n\ge1\) that any string \(w\in L\) with \(|w|\ge n\) can be written as \(w=xyz\) such that:
- \(y\ne e\)
- \(|xy|\le n\)
- \(\forall i>0,xy^iz\in L\)
想不明白了，先睡觉。
先背下来再说。
对于上下文无关语言的泵定理
引理
高度为 \(h\) 的任何 \(G\) 的parse tree 长度不超过 \(\phi(G)^h\)
定理
Let \(G=(V,\Sigma,R,S)\) be a CFG, then any string \(w\in L(G)\) of length greater than \(n\ge \phi(G)^{|V-\Sigma|}\) can be written as \(w=uvxyz\) such that:
- \(vy\ne e\)
- \(|vxy|\le n\)
- \(\forall i \ge 0,uv^ixy^iz\in L(G)\)
NFA to DFA
子集构造法
DFA 的每个状态对应 NFA 的一个状态集合。
输入：NFA \(N\)
输出：DFA \(D\)
构造转换表 \(Dtran\)
\(D\) 的状态集合 \(Dstates\)
\(N\) 的单个状态记为 \(s\)，\(N\) 的一个状态集记为 \(T\)。
\(\epsilon-closure(s)\)
\(\epsilon-closure(T)=U_{s\in T}\epsilon-closure(s)\)
\(move(T,a)\) 从 \(T\) 的某个状态 \(s\) 出发，通过标号为 \(a\) 的转换能到达的 NFA 的状态集合。
开始时，\(\epsilon-closure(s_0)\) 是 \(Dstates\) 中的唯一状态且未加标记。
while \(Dstates\) 中有一个未标记状态 \(T\)
标记 \(T\)
foreach 输入符号 \(a\)
\(U=\epsilon-closure(move(T,a))\)
if \(U\not\in Dstates\)
将 \(U\) 加入 \(Dstates\) 且不加标记
\(Dtran[T,a]=U\)
判断语言是否为正则语言
正则语言对于交、并、补、差，连接，克林闭包封闭。
- F - 正则语言的子集都是正则语言
- F - 正则语言都有正则的真子集（空集没有）
- T - 正则语言 \(L~x,y\in L,\{xy|x\in L,y\not\in L\}\) 是正则语言（补集与连接）
- F - \(\{w|w=w^R\}\) 是正则语言
- T - \(\{w|w\in L ~\text{and}~ w^R\in L\}\) （\(L\) 是正则语言，\(L'=L\cap L^R\)）
- F - If \(C\) is any set of regular languages, then \(\cup C\) is a regular language. （无限集）
- T - \(\{xyx^R|x,y=\Sigma^*\}\) 是正则语言（\(x\) 可以为空，\(y=\Sigma^*\) ）
判断语言是否为上下文无关
上下文无关语言对于并，连接与克林闭包封闭，对交、补、差不封闭。
正则语言与上下文无关语言的交集还是上下文无关语言。
- \(\{a^mb^nc^p\}\) 其中 \(m,n,p\) 三者有两个相等或者不等，是上下文无关语言。三者均相等不是上下文无关语言。均不等呢？
- \(L=\{w\in \{a,b,c\}^*|\text{其中三个字母出现次数均不相等}\}\) 是上下文无关的，由三者中两个不等并运算得到。
- \(L\): CFL, \(R\): RL
- \(L-R\in\) CFL, for \(L-R=L\cap\bar{R}\)
- \(R-L\) 不一定，具有反例：\(R=a^*b^*c^*,R-L=\{a^nb^nc^n\}\)
判断语言是否为递归语言
递归语言对于交、并、补、差，连接，克林闭包封闭。
判断语言是否为递归可枚举
递归可枚举语言对于交，并，连接和克林闭包运算封闭。对补与差运算不封闭。
递归函数
可被一个图灵机计算的函数。
Basic Functions
\[ zero_k(n_1,\dots,n_k)=0 \\ id_{k,j}(n_1,\dots,n_k)=n_j \\ succ(n)=n+1 \]
Primitive Recursive Functions
原始递归函数即上述三种基本函数的组合可得到的函数。
- \(\mu-recursive\)
不可判定性
\(L(M)\) : 图灵机 \(M\) 半判定的语言。
Tiling 问题是不可解的。
图灵机有可数无限多个。
邱奇-图灵论题
算法
判定
半判定
不可判定
函数
递归语言
图灵机可以停机并给出判定的语言。
若语言 \(L\) 与 \(\bar{L}\) 均为递归可枚举语言（即正反都能停机判定），则 \(L\) 为递归语言。
对于补运算封闭。
递归可枚举语言
图灵机对于接受的字符串可以停机，对于不接受的字符串可能不停机的语言。
递归可枚举语言即图灵可枚举语言。
通用图灵机
\(U(M,w)=M(w)\)
Rice 定理
设 P 是任何图灵机的语言的非平凡属性。确定某一图灵机的语言是否具有属性 P 这一问题是不可判定的。
If \(C\) is a proper and non-empty subset of recursively enumerable languages, then it is undecidable for a Turing Machine \(M\), whether \(L(M)\in C\)
所以几乎所有关于“图灵机是否在此种输入上停机”的问题都是不可判定的。
e.g:
- \(L(M)=\emptyset\)
- \(L(M)\) is finite
- \(L(M)=\Sigma^*,e\in L(M)\)