计算理论导引笔记整理 第一部分 第十章 非正则语言 – Dylech30th's Blog

  在之前数章中，我们一直致力于有关正则语言的部分，无论之前提到的各种正则语言多么复杂，无非都是那么几种，比如以某某字母开头或结尾，或者要求有连续两个某某字母。而第二章中出现了一种语言PALINDROME，虽然可以用自然语言描述，但是它不能够被正则表达式所定义，也不能被有限自动机识别，这种语言是非正则语言(Nonregular languages)，为了识别他们，需要更加强大的自动机

DEFINITION 任何不能被正则表达式所定义的语言都是非正则语言(Nonregular languges)

根据Kleene定理，可以得知非正则语言同样不能被有限自动机或者状态转移图接受，所有语言要么是正则的，要么是非正则，但不能同时是两者。

  给出一种\varSigma=\lbrace a.b\rbrace上面的语言

该语言是正则语言language(a^\ast b^\ast)的子集，但是本身却不是正则语言，为了证明这点需要用归谬法，首先我们假设它是正则语言，那么一定有一个DFA识别它，由于DFA的状态数量是有限的，我们假设识别这个语言的DFA有95个状态，因为DFA识别L，因此s=a^{96}b^{96}也一定被该DFA识别，但是注意，由于DFA一共有95个状态，而s中a的数量一共有96个，根据鸽巢原理，一定有一个状态会被重复访问至少一次，也就是说DFA中一定存在一个回路(也就是一个由若干个状态被a边连接所构成的一个循环)，使得从该状态出发有一条路径回到该状态，就像一个圆环，s在这个圆环上不停的被读取，直到所有的a都被读取完毕，s会沿着b边离开这个回路。   假设这个回路中包含了n个状态，那么从回路的一个状态出发，读n个字符就会再回到这个状态，既然s可以被接受，那么设想s_1=a^{96+n}b^{96}在该DFA上会怎么运行呢？最开始它的路径和s一模一样，直到在回路中读取了96个a以后，在s中，此时就应该沿着b边离开回路，但是在s_1中，它沿着这条回路又多走了一圈，然后回到同一个位置，再沿着b边离开回路，接下来经历的路径又是和s完全一样，最终会停留在接受s的状态上，也就是说，s和s_1都会被该DFA接受，可是问题在于，s_1并不属于语言L，归纳可得，诸如a^{96+2n}b^{96},a^{96+3n}b^{96},...,a^{96+mn}b^{96}这些并不属于L的字符串都会被DFA接受，这个DFA并不仅仅接受L，而且还接受不属于L的字符串，因此可以说，该DFA并不能识别L。这就是泵引理(The Pumping Lemma)的核心思想，之所以叫做"泵"，是因为该定理的核心就是把字符串分开，然后在中间的部分"泵"出更多的字符串，之所以叫引理，是因为该定理常用于证明其他的定理，最常见的是证明一个语言是非正则的。

定理1 令L是任意无限长(这意味着有无限多个单词)的正则语言，存在字符串x，y和z，其中y\neq\varLambda，使得对于任意n\in\mathbb{N}^+，有xy^nz\in L 证明 假设存在具有k个状态的有限自动机M识别L，令w是任意L中长度大于k的单词，则根据鸽巢原理，M中必定存在回路，此时令w=xyz，其中x部分是在M中进入回路以前的字符串，y是在回路中循环一次的字符串，而z是离开回路之后的字符串，由于xyz被M接受，因此xyyz，xyyyz，一直到xy^nz\ for\ n\in\mathbb{N}^+都会在回路上多循环n-1次后进入z段所属的路径，进而在同样的停机状态被M接受。

在如上的定理中存在一个微妙的事实，而定理本身没有展示出来，注意x段经过的所有状态都是之前没有被到达过的，也就是"新的"，而y段的所有状态也是新的，因为在字符串xyz中，第一次访问已经到达过的状态是在处理完y段以后，也就是说在处理完y段以前，所有的状态都是第一次到达，也就是说xy的总长度，不超过状态机的总状态数，根据这一点，可以得到一个更完善的定理

定理1(更加完善的版本) 令L是被具有N个状态的有限自动机识别的任意无限长(这意味着有无限多个单词)的正则语言，则对于所有长度大于N的L中的单词，存在字符串x，y和z，其中y\neq\varLambda并且|xy|\leqslant N1，使得对于任意n\in\mathbb{N}^+，xy^nz\in L

之所以要完善这些，是因为他可以让证明步骤边的更加简单，某些情况下，没必要再去分情况的划分x和y以及z，因为|xy|被要求不能大于N。   比如要证明语言\text{PALINDROME}(简称\mathcal{P})是非正则的，第一个版本的定理在这里是不适用的，因为对于ab^na来说，第一版本的定理可以得到\mathcal{P}并非非正则这一点结论。此时可以使用第二个版本的泵引理去证明：令识别\mathcal{P}的DFA拥有k个状态，考虑a^nba^n,n\in\mathbb{N}^+\land n\geqslant k，由泵引理可知存在w=xyz并且|xy|\leqslant k，也就是说|xy|\leqslant n，因此xy中全部都是a，此时观察xy^nz,n\in\mathbb{N}^+，会发现这样得到的字符串是给开头的a^n部分加入更多的a，而结尾的a^n部分不变，还是n个，因此\forall_{n\in\mathbb{N}^+\land n\geqslant 2}(xy^nz\notin\mathcal{P})，所以\mathcal{P}并非正则语言

  泵引理仅仅是证明一个语言是否是正则语言的必要条件，而非充分条件，它只能用来证明某个语言是非正则的，而不能用于证明某个语言是正则的，而迈希尔-尼罗德定理则对语言的正则与否提供了充要条件

定理2 给定语言L，任意字符串x和y，定义等价关系R_L=\lbrace\langle x,y\rangle|\forall_{z\in\varSigma^\ast}((xz\in L\land yz\in L)\lor (xz\notin L\land yz\notin L))\rbrace，则语言L是正则的，当且仅当L派生出的等价类是有限多个

证明 1. 如果L是正则语言，则L派生出的等价类是有限多个 因为L是正则语言，所以存在一个DFA识别L，而R_L在DFA上所表现出的，就是从某两个状态开始处理同一个字符串z，要么都停机，要么都不停机。而DFA的状态是有限多个的，因此R_L所划分的等价类的数量一定是有限的。 2. 如果L派生出的等价类是有限多个，则L是正则语言 这一部分的证明将会尝试从等价类的集合构造出一个DFA，令等价类分别是C_1,C_2,C_3,...,C_n，其中\varLambda\in C_1，则C_1必定是起始状态，因为只有\varLambda是不读入任何字符就可以维持在起始状态上的，接着注意，假如\exists_{w\in C_m}(w\in L)，则\forall_{w\in C_m}(w\in L)，为了证明这点，令s,w\in C_m，并且s\in L，我们知道s\varLambda和w\varLambda要么都在L中，要么都不在，而因为s\in L，所以s\varLambda\in L，所以可知w\varLambda\in L，这蕴含着w\in L，而因为这些字符串都是L中的单词，所以这意味着集合C_m应当是停机状态，因为所有可能被接受的字符串都蕴含在C_m里。接着观察对于除了C_m以外的任意等价类，比如C_k，令x,y\in C_k，则xa和ya一定属于同一等价类，因为对于任意字符串i，xai和yai要么都属于L，要么都不属于L，这是因为如果令z=ai，那么xz和az就要么都属于L，或者都不属于L，对C_k中的所有字符串都这么做，得到一个新的集合C_r，用a边把C_k和C_r连接起来，类似的，去把所有剩余的等价类用a边和b边连接起来，就可以得到一个对应的DFA Q.E.D.

  迈希尔-尼罗德定理提供了一种更简单的方法来判断某语言是否是正则的，比如，对于语言L=\lbrace a^nb^n\rbrace，因为对于任意的a^m，只有z=b^m的时候a^mz才会属于L，也就是对于a^m和a^n，存在一个z使得a^mz和a^nz中的任意一个属于L，而另一个不属于，因此每个a^m都会构成一个单独的等价类，也就是说语言L派生出了无限多个等价类，因此它不是正则语言

定义 令R和Q是不同的语言，有语言\text{Pref(Q in R)}=\lbrace p\in\varSigma^\ast|\exists_{q\in Q}\exists_{w\in R}(pq=w) \rbrace

注意，\varLambda\in \text{Pref(Q in R)}当且仅当Q和R包含一些相同的单词；也可能Q中没有任何单词能够通过增加某些前缀来获得一个R中的单词，这时说\text{Pref(Q in R)}=\phi，并且\text{Pref(Q in R)}Q\neq R，因为Q中可能有很多单词根本无法通过添加前缀构成R中的单词。

定理3 如果R是正则语言，而Q是任意语言，则P=\text{Pref(Q in R)}是正则语言 证明 令M是识别R的有限自动机，接着对于M中的每一个状态q和Q中的每一个单词w，让w从q开始运行，如果存在一个w能从q开始运行到M的某个停机状态，就给这个q状态打上标记，接着，构造一个和M拥有相同多的状态，相同的边的有限自动机M'，区别在于M'中的某个状态q'是停机状态当且仅当q'对应的M中的状态q是被标记的。

引理1和2一起，蕴含有限自动机M'识别语言P，因此P是正则语言 Q.E.D.

  可以通过泵引理或者迈希尔-尼罗德定理尝试证明某个语言是非正则的，对于前者，假定一个具有k状态的有限自动机M_k识别语言L，找出一个w\in L使得w没有任何办法被分割成合适的xyz三部分；对于后者，找出两个字符串(任意的)x和y，使得对于字符串z，xz和yz至少有一个属于L