浙江大学 计算理论 提纲

天塌了(

章节列表
集合,关系和语言
有限自动机
上下文无关语言
图灵机
不可判定性
语言 自动机
正则语言 确定性/非确定性有限自动机
上下文无关语言 下推自动机
递归可枚举语言 图灵机

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)\)