Regular Languages
略
DFA
略.
NFA
考虑一个五元组$Q,\Sigma,\delta,q_{start},F$,比起DFA,这里的$\delta:Q\times \Sigma_{\epsilon}\to 2^Q$,也即现在一个点可能会有若干条字符相同的边指向若干其它结点.
利用NFA容易证明当$A,B$是正则语言的时候,$A\circ B,A^*,A\cup B$都是正则语言.
GNFA
考虑一个五元组$Q,\Sigma,\delta,q_{start},F$,这里其实一般认为$F=\{q_{end}\}$.比起NFA,其$\delta$变为了一个函数$(Q-F)\times (Q-\{q_{start}\})\to R$,其中$R$是正则表达式的集合,也就是每条边匹配的从一个字符变成了一个正则表达式.下面我们要证明所有的单接收状态GNFA都可以由RE表示.
证明比较平凡,直接考虑每次删掉一个点,然后把其它的所有点两两配对考虑经过这个点的情况,把相应的边concat起来.然后如果有自环就加$*$,如果有重边就加$|$,这样就搞定了.
显然DFA可以转为一个GNFA(接收状态稍微收集一下),这也证明了RE的表达能力不弱于DFA.
Pumping Lemma
如果$A$是一个正则语言,那么$\exists p\in \mathbb{N}$,使得只要$s\in A\land |s|\geq p$,那么存在一种切分$s=xyz$使得:
- $\forall i\geq 0,xy^iz\in A$.
- $|y|>0$.
- $|xy|\leq p$.
也就是足够长的串总会在不任意靠后的地方出现非平凡循环体.
证明办法的话,考虑先转为DFA,这个DFA总共就这么几个结点,不妨直接设$p=|Q|$,那么超过$p$后,考虑经过的状态点序列共有$|Q|+1$个,显然总会有重复的结点,也就是在它们中走了一个环,重复这个环即可.
我依稀记得我在coq中用induction技巧不途径DFA证明过这个,但我忘了咋搞的了x.
Context-Free Languages
考虑一个四元组$(V,\Sigma,R,s)$,其中:
- $V$是variables.
- $\Sigma$是terminals
- $R$是rules
- $s\in V$是start variable
PDA
考虑一个五元组$(Q,\Sigma,\Gamma,\delta,q_{start},F)$,比起NFA,它多了一个$\Gamma$表示堆栈的字母表.此时$\delta:Q\times \Sigma_\epsilon\times \Gamma_\epsilon\to \mathcal{P}(Q\times \Gamma_\epsilon)$.
转移现在成为了两串$s_0,\cdots,s_m$和$t_0,\cdots, t_m$,满足:
- $s_0=q_{start},t_0=\epsilon$.
- 当$t_i=ar,t_{i+1}=br$时,需要有$(s_{i+1},b)\in \delta(s_i,w_{i+1},a)$.
- $s_m\in F$.
现在我们来证明CFL和PDA等价.
先看如何证明能被CFL生成的都能被PDA识别.问题显然仅仅在于我不知道我当前在匹配哪条规则,所以我们直接把这个压入栈中就行了.后面匹配完成后再逐渐把后半部分的字符消灭掉,毛估估一下.
再看怎么证明PDA能识别的都能被CFL生成.我们先改造这个PDA满足:
- 只有一个接收节点.
- 接受的时候必须清空堆栈.
- 每次转移要么进行压入,要么进行弹出.
显然这些都可以做一些平凡的转化得到.
定义$A_{pq}$为:一个空栈从$p$出发,到$q$的时候栈仍然是空的情况.现在我们把以下两种规则加入:
- 对于状态$p,r,s,q$,如果遇到$a$字符,$p\to r$会压入$u$;遇到$b$字符,$s\to q$会弹出$u$.则将$A_{pq}\to aA_{rs}b$.
- 对于状态$p,r,q$,直接添加规则$A_{pq}\to A_{pr}A_{rq}$.
- 对于状态$p$,直接添加规则$A_{pp}\to \epsilon$.
其实还是在做括号序列.我们来看为何能被PDA识别的都能被CFL生成.原因是如果能被PDA识别,去看它的括号序列,就可以反映出上面的这些部分.
Pumping Lemma
如果$A$是一个CFL,则$\exists p\in \mathbb{N}$,使得$\forall s\in A$且$|s|\geq p$,那么可以划分$s=uvxyz$使得:
- $\forall i\geq 0,uv^ixy^iz\in A$.
- $|vy|>0$.
- $|vxy|\leq p$.
接下来我们考虑最简的一种推理方式,即运用最少次规则推导出来.
由于$|V|,|\Sigma|,|R|$都是有限的,我们考虑设$b=\max_{r\in R}(#\{\text{symbols in RHS of r}\})$,这里的symbols指的是Terminals或Variables.此时,一个高度为$h$的推理串,得到的长度最多是$b^h$.如果$h>|V|$,那么就至少存在一条推理串上,同一个Variable出现了两次.因此如果一个串的长度超过了$b^{|V|+1}$,则它的高度$h>|V|$,因此可以找到一个Variable最终递归调用回了自己.取$p=b^{|V|+1}$,我们假设这个做到了$B\to s_1Bs_2\to s_1s_3s_2$.容易把这个东西替换上去或者替换下去,这样就证明了(1).
现在来看(2),如果$|vy|=0$,这意味着我们做了一圈$B\to B$,这显然不是最简的推理方式.
最后来看(3),只需要找最靠下的$|V|+1$层,然后去做上面的过程就行.
Turing Machine
一个$k$-tape的图灵机是一个七元组$(Q,\Sigma,\Gamma,\delta,q_0,q_{accept},q_{reject})$.其中:
- $Q$作为状态集.
- $\Sigma$作为输入字符表.
- $\Gamma$作为tape字符表.
- $\delta:Q\times \Gamma^k\to Q\times \Gamma^k\times \{L,S,R\}^k$
一般而言,输入的字符在第一个纸带上.
我们说一个图灵机接受一个$w$,当且仅当存在一列configuration $C_0,\cdots,C_t$,使得上述转移.
我们称一个语言是Turing-recognizable的,当且仅当存在一个图灵机接受它(可以不停机或者拒绝).我们称一个图灵机是decidable的,当且仅当它永远不会陷入死循环,一定会到达一个Halt状态.
现在我们想要探索这些东西的边界:
- 是否存在一个语言不可被recognized.
- 是否存在一个语言可以被recognized,但是不可被decided.
对于(1)是一个很自然的事.图灵机的数量是可数的,但是语言的集合显然是不可数的.这就完蛋了.
称一个语言$A$对于$B$是mapping reducible的(记作$A\leq_m B$).如果存在一个decidable的函数$f:\Sigma_A^\to \Sigma_B^$,使得$\forall w,w\in A\Leftrightarrow f(w)\in B$.有如下性质:
- 如果$B$是decidable的,那么$A$一定是decidable的.
- 如果$A$是undecidable的,那么$B$一定是undecidable的.
- $A\leq_m B$当且仅当$\bar{A}\leq_m \bar{B}$.
来看:
- $UC=\{\alpha|M_\alpha(\alpha) \text{unaccept}\}$.
- $EQ_{TM}=\{(M_1,M_2)|L(M_1)=L(M_2)\}$.
- $E_{TM}=\{M|L(M)=\emptyset\}$.
- $HALT=\{(M,\alpha)|M(\alpha)\text{halt}\}$
- $A_{TM}=\{(M,\alpha)|M(\alpha)\text{accept}\}$
我们可以证明:
- $E_{TM}\leq_m EQ_{TM}$.
- $A_{TM}\leq_m \overline{E_{TM}}$.
- $A_{TM}\leq_m EQ_{TM}$.
- $UC,EQ_{TM},E_{TM},A_{TM},HALT$都是undecidable的.
- $\overline{UC},\overline{E_{TM}},A_{TM},HALT$都是recognizable的.
现在需要搞定$\overline{A_{TM}}$是unrecognizable的.
引理: 一个语言$A$是decidable的,当且仅当$A$和$\bar A$都是recognizable的.
这条引理可以证明$UC,E_{TM},\overline{A_{TM}},\overline{HALT}$都是unrecognizable的.现在来看如何证明$EQ_{TM}$和$\overline{EQ_{TM}}$都是unrecognizable的.
而$\overline{A_{TM}}\leq_m E_{TM}\leq EQ_{TM}$,这就证明了$EQ_{TM}$是unrecognizable的.
而显然$A_{TM}\leq_m EQ_{TM}$,同时取补得到$\overline{EQ_{TM}}$是unrecognizable.
Time Complexity
设$\mathrm{DTIME}(T(n))$为一个包含那些能在$O(T(n))$时间内解决的语言的集合.设$P$为$\bigcup_{c\geq 0}\mathrm{DTIME}(n^c)$,以及$EXP$为$\bigcup_{c\geq 0}\mathrm{DTIME}(2^{n^c})$.
定义$NP$为存在一个多项式时间的函数$P$以及一台多项式时间的验证机器$M$,使得对于每个$x$,要判断其$x\in L$,当且仅当存在一个$u\in \{0,1\}^{P(|x|)}$使得$M(x,u)=1$.
另一种定义NP的方式是用NDTM来定义,定义NP为所有可以被NDTM在多项式时间内判定的问题的集合.
下面我们来证明这两种定义等价.不妨设它们分别是NP1和NP2.
先证明$NP1\subseteq NP2$.说明$L\in NP1\Rightarrow L\in NP2$.这个方式看上去就比较简单,直接让NDTM跑的时候去猜$u$的每一位是什么就行.
对于$NP2\subseteq NP1$,只需要记录下来每一步走得什么选择,用这个反过来就可以得到一个确定性的图灵机.
Time Hierarchy Theorem
如果$f$和$g$满足$f\log f=o(g)$,则$\mathrm{DTIME}(f(n))\subsetneq \mathrm{DTIME}(g(n))$.
包含关系是显然的.问题在于找一个语言在$\mathrm{DTIME}(g(n))$中而不在$\mathrm{DTIME}(f(n))$中.
现在考虑一个$L$,对于一个输入$x$,如果$M_x(x)$在$g(|x|)$步内停机,那么$L$输出$M_x(x)$的取反;否则输出reject.显然$L\in \mathrm{DTIME}(g(n))$,现在来看假设$L\in \mathrm{DTIME}(f(n))$,则存在一台图灵机$M_z$能判定该问题,那至少其输入$z$后能在$O(f(|z|))$内输出$M_z(z)=L(z)$.可是通用图灵机模拟$M_z(z)$只需要$O(f(|z|)\log f(|z|))$,因此$L(z)$一定会是$M_z(z)$的取反.这就矛盾了.
P-NP
定义多项式时间归约当且仅当存在一个多项式时间计算的$f_p:A\to B$,使得$a\in A$当且仅当$f(a)\in B$.此时我们说$A\leq_p B$,能解决$B$就能解决$A$.
定义一个语言$L$,是NP-hard的,当且仅当$\forall A\in NP$,$A\leq_p L$.
定义一个语言$L$是NP-complete,当$L$是NP-hard而且$L$也是$NP$.
Cook-Levin Theorem
考虑一个Bool表达式(只包含原子变量和与或非),定义一个$\varphi$是CNF的当且仅当它始若干个OR连接的东西AND起来.大概长成$\land_i(\lor_j v_{i,j})$,其中$v_{i,j}$要么是一个变量,要么是一个变量取反.如果后面的$\lor_j v_{i,j}$的项数都不超过$k$,则称其为$k$-CNF.定义SAT是所有可满足的CNF公式,定义3-SAT是所有可满足的3-CNF公式.
下面我们证明SAT和3-SAT都是NPC.
显然SAT和3-SAT都是NP的(只要给一组赋值就行).下面我们来证明对于任意$L\in NP$,都总有$L\leq_p SAT$.
我们想要搞一个多项式时间可计算的函数$f:x\to \psi_x$,使得$x\in L$当且仅当$\psi_x$可满足.
考虑转化为对configuration序列进行判断,考虑搞一个$T(n)\times T(n)$大小的二维表格,第$k$行表示在第$k$时刻,纸带上的情况.所有的转移规则都可以用Bool表达式刻画.
唯一的问题在于层数.考虑你需要先读一下指针所指的位置,再用$\delta$转移,这个东西就会很复杂.现在我们尝试用一个oblivious图灵机:它的转移不依赖指针指向的位置,这样大概就行了吧……
下面来看怎么证明$SAT\leq_p 3SAT$.考虑缩减一下这个东西,如果$C_i=A_i\lor B_i$,其中$C_i$的变量数量超过了$3$,而$B_i$的变量数量为$2$.引入一个新的变量$u$,转化为$C_i=(A_i\lor u)\land (B_i\lor (\lnot u))$.