Regular Languages

略

DFA

略.

NFA

考虑一个五元组,比起DFA,这里的,也即现在一个点可能会有若干条字符相同的边指向若干其它结点.

利用NFA容易证明当是正则语言的时候,都是正则语言.

GNFA

考虑一个五元组,这里其实一般认为.比起NFA,其变为了一个函数,其中是正则表达式的集合,也就是每条边匹配的从一个字符变成了一个正则表达式.下面我们要证明所有的单接收状态GNFA都可以由RE表示.

证明比较平凡,直接考虑每次删掉一个点,然后把其它的所有点两两配对考虑经过这个点的情况,把相应的边concat起来.然后如果有自环就加,如果有重边就加,这样就搞定了.

显然DFA可以转为一个GNFA(接收状态稍微收集一下),这也证明了RE的表达能力不弱于DFA.

Pumping Lemma

如果是一个正则语言,那么,使得只要,那么存在一种切分使得:

  1. .
  2. .
  3. .

也就是足够长的串总会在不任意靠后的地方出现非平凡循环体.

证明办法的话,考虑先转为DFA,这个DFA总共就这么几个结点,不妨直接设,那么超过后,考虑经过的状态点序列共有个,显然总会有重复的结点,也就是在它们中走了一个环,重复这个环即可.

我依稀记得我在coq中用induction技巧不途径DFA证明过这个,但我忘了咋搞的了x.

Context-Free Languages

考虑一个四元组,其中:

  1. 是variables.
  2. 是terminals
  3. 是rules
  4. 是start variable

PDA

考虑一个五元组,比起NFA,它多了一个表示堆栈的字母表.此时.

转移现在成为了两串和,满足:

  1. .
  2. 当时,需要有.
  3. .

现在我们来证明CFL和PDA等价.

先看如何证明能被CFL生成的都能被PDA识别.问题显然仅仅在于我不知道我当前在匹配哪条规则,所以我们直接把这个压入栈中就行了.后面匹配完成后再逐渐把后半部分的字符消灭掉,毛估估一下.

再看怎么证明PDA能识别的都能被CFL生成.我们先改造这个PDA满足:

  1. 只有一个接收节点.
  2. 接受的时候必须清空堆栈.
  3. 每次转移要么进行压入,要么进行弹出.

显然这些都可以做一些平凡的转化得到.

定义为:一个空栈从出发,到的时候栈仍然是空的情况.现在我们把以下两种规则加入:

  1. 对于状态,如果遇到字符,会压入;遇到字符,会弹出.则将.
  2. 对于状态,直接添加规则.
  3. 对于状态,直接添加规则.

其实还是在做括号序列.我们来看为何能被PDA识别的都能被CFL生成.原因是如果能被PDA识别,去看它的括号序列,就可以反映出上面的这些部分.

Pumping Lemma

如果是一个CFL,则,使得且,那么可以划分使得:

  1. .
  2. .
  3. .

接下来我们考虑最简的一种推理方式,即运用最少次规则推导出来.

由于都是有限的,我们考虑设,这里的symbols指的是Terminals或Variables.此时,一个高度为的推理串,得到的长度最多是.如果,那么就至少存在一条推理串上,同一个Variable出现了两次.因此如果一个串的长度超过了,则它的高度,因此可以找到一个Variable最终递归调用回了自己.取,我们假设这个做到了.容易把这个东西替换上去或者替换下去,这样就证明了(1).

现在来看(2),如果,这意味着我们做了一圈,这显然不是最简的推理方式.

最后来看(3),只需要找最靠下的层,然后去做上面的过程就行.

Turing Machine

一个-tape的图灵机是一个七元组.其中:

  1. 作为状态集.
  2. 作为输入字符表.
  3. 作为tape字符表.

一般而言,输入的字符在第一个纸带上.

我们说一个图灵机接受一个,当且仅当存在一列configuration ,使得上述转移.

我们称一个语言是Turing-recognizable的,当且仅当存在一个图灵机接受它(可以不停机或者拒绝).我们称一个图灵机是decidable的,当且仅当它永远不会陷入死循环,一定会到达一个Halt状态.

现在我们想要探索这些东西的边界:

  1. 是否存在一个语言不可被recognized.
  2. 是否存在一个语言可以被recognized,但是不可被decided.

对于(1)是一个很自然的事.图灵机的数量是可数的,但是语言的集合显然是不可数的.这就完蛋了.

称一个语言对于是mapping reducible的(记作).如果存在一个decidable的函数,使得.有如下性质:

  1. 如果是decidable的,那么一定是decidable的.
  2. 如果是undecidable的,那么一定是undecidable的.
  3. 当且仅当.

来看:

  1. .
  2. .
  3. .

我们可以证明:

  1. .
  2. .
  3. .
  4. 都是undecidable的.
  5. 都是recognizable的.

现在需要搞定是unrecognizable的.

引理: 一个语言是decidable的,当且仅当和都是recognizable的.

这条引理可以证明都是unrecognizable的.现在来看如何证明和都是unrecognizable的.

而,这就证明了是unrecognizable的.

而显然,同时取补得到是unrecognizable.

Time Complexity

设为一个包含那些能在时间内解决的语言的集合.设为,以及为.

定义为存在一个多项式时间的函数以及一台多项式时间的验证机器,使得对于每个,要判断其,当且仅当存在一个使得.

另一种定义NP的方式是用NDTM来定义,定义NP为所有可以被NDTM在多项式时间内判定的问题的集合.

下面我们来证明这两种定义等价.不妨设它们分别是NP1和NP2.

先证明.说明.这个方式看上去就比较简单,直接让NDTM跑的时候去猜的每一位是什么就行.

对于,只需要记录下来每一步走得什么选择,用这个反过来就可以得到一个确定性的图灵机.

Time Hierarchy Theorem

如果和满足,则.

包含关系是显然的.问题在于找一个语言在中而不在中.

现在考虑一个,对于一个输入,如果在步内停机,那么输出的取反;否则输出reject.显然,现在来看假设,则存在一台图灵机能判定该问题,那至少其输入后能在内输出.可是通用图灵机模拟只需要,因此一定会是的取反.这就矛盾了.

P-NP

定义多项式时间归约当且仅当存在一个多项式时间计算的,使得当且仅当.此时我们说,能解决就能解决.

定义一个语言,是NP-hard的,当且仅当,.

定义一个语言是NP-complete,当是NP-hard而且也是.

Cook-Levin Theorem

考虑一个Bool表达式(只包含原子变量和与或非),定义一个是CNF的当且仅当它始若干个OR连接的东西AND起来.大概长成,其中要么是一个变量,要么是一个变量取反.如果后面的的项数都不超过,则称其为-CNF.定义SAT是所有可满足的CNF公式,定义3-SAT是所有可满足的3-CNF公式.

下面我们证明SAT和3-SAT都是NPC.

显然SAT和3-SAT都是NP的(只要给一组赋值就行).下面我们来证明对于任意,都总有.

我们想要搞一个多项式时间可计算的函数,使得当且仅当可满足.

考虑转化为对configuration序列进行判断,考虑搞一个大小的二维表格,第行表示在第时刻,纸带上的情况.所有的转移规则都可以用Bool表达式刻画.

唯一的问题在于层数.考虑你需要先读一下指针所指的位置,再用转移,这个东西就会很复杂.现在我们尝试用一个oblivious图灵机:它的转移不依赖指针指向的位置,这样大概就行了吧......

下面来看怎么证明.考虑缩减一下这个东西,如果,其中的变量数量超过了,而的变量数量为.引入一个新的变量,转化为.