非正则语言

泵引理(The Pumping Lemma)

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

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

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

为什么非正则语言不能被有限自动机识别

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

L=\lbrace a^nb^n\ for\ n=0,1,2,3,4,5,...\rbrace

该语言是正则语言language(a^\ast b^\ast)的子集,但是本身却不是正则语言,为了证明这点需要用归谬法,首先我们假设它是正则语言,那么一定有一个DFA识别它,由于DFA的状态数量是有限的,我们假设识别这个语言的DFA有95个状态,因为DFA识别L,因此s=a^{96}b^{96}也一定被该DFA识别,但是注意,由于DFA一共有95个状态,而sa的数量一共有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的状态上,也就是说,ss_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是任意无限长(这意味着有无限多个单词)的正则语言,存在字符串xyz,其中y\neq\varLambda,使得对于任意n\in\mathbb{N}^+,有xy^nz\in L
证明
假设存在具有k个状态的有限自动机M识别L,令w是任意L中长度大于k的单词,则根据鸽巢原理,M中必定存在回路,此时令w=xyz,其中x部分是在M中进入回路以前的字符串,y是在回路中循环一次的字符串,而z是离开回路之后的字符串,由于xyzM接受,因此xyyzxyyyz,一直到xy^nz\ for\ n\in\mathbb{N}^+都会在回路上多循环n-1次后进入z段所属的路径,进而在同样的停机状态被M接受。

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

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

之所以要完善这些,是因为他可以让证明步骤边的更加简单,某些情况下,没必要再去分情况的划分xy以及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}并非正则语言

迈希尔-尼罗德定理(Myhill-Nerode Theorem)

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

定理2
给定语言L,任意字符串xy,定义等价关系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\varLambdaw\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,则xaya一定属于同一等价类,因为对于任意字符串ixaiyai要么都属于L,要么都不属于L,这是因为如果令z=ai,那么xz和az就要么都属于L,或者都不属于L,对C_k中的所有字符串都这么做,得到一个新的集合C_r,用a边把C_kC_r连接起来,类似的,去把所有剩余的等价类用a边和b边连接起来,就可以得到一个对应的DFA
Q.E.D.

迈希尔-尼罗德定理的应用

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

语言的商

定义
RQ是不同的语言,有语言\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)}当且仅当QR包含一些相同的单词;也可能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中的每一个状态qQ中的每一个单词w,让wq开始运行,如果存在一个w能从q开始运行到M的某个停机状态,就给这个q状态打上标记,接着,构造一个和M拥有相同多的状态,相同的边的有限自动机M',区别在于M'中的某个状态q'是停机状态当且仅当q'对应的M中的状态q是被标记的。

  • 引理1: M'接受的所有字符串都属于P
    证明: 如果一个字符串sM'所接受,则他会从M'的起始状态开始,一直运行到停机状态,令这一段的字符串是w,接着把这个状态对应到M上,Q中存在某个单词可以从这个状态开始运行到M的停机状态,令这一段的字符串是k,这说明以M'的该停机状态为分界线,前半部分和后半部分字符串合在一起是R的单词,即wk\in R,而后半部分正好是Q中的一个单词,也就是k\in Q,这两条蕴含了w\in P
  • 引理2: P中的所有字符串都会被M'接受
    证明: 根据定义,对于P中的任意单词pQ中存在一个单词q,使得pq=w\in R,这意味着pq会被M所接受,也就是从起始状态运行到停机状态,注意pq由两部分组成,其中p部分被首先读入,并且在某个状态s处开始读取q部分,然而q\in Q并且q可以在s上运行到停机,这蕴含状态sM中是被标记的,也就是M'中的一个停机状态,因为p正好在M的状态s处结束读取,因此pM'上对应s的停机状态s'处停机,这证明了P中的任意字符串都会被M'接受

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

证明技巧

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


  1. 此处的|xy|等价于length(xy),因为xy是字母的集合,而|xy|是求xy的基数 ↩︎

乱我心者,今日之日多烦忧