正则语言.doc

正则语言的性质 本章中我们将会探讨正则语言的性质，在此过程中我们所使用的第一个工具是一个定理，它能够证明某个语言不是正则的。该定理叫做“泵引理”，我们将在第4.1节中介绍它。 正则语言的一类很重要的性质是“闭包性质”，该性质使得我们能够从一些语言出发，通过一定的运算符，来构造能够识别另一些语言的自动机。例如，两个正则语言的交仍然是正则语言。因此，给定能够识别两个不同的正则语言的自动机，我们可以机械地构造一个恰好识别这两个语言的交的自动机。由于这样构造出来的自动机可能比给定的两个自动机的状态都多，因此这种“闭包性质”可以作为一种构造复杂的自动机的工具。第2.1节中用很实质的方式使用了这种构造过程。 正则语言的另一类很重要的性质是“判定性质”，通过对这些性质学习使得我们能够给出用来回答关于自动机的很重要的问题的算法。一个核心的例子是用来判定两个自动机是否定义了同样语言的算法。我们能够判定该问题的能力使得我们能够把自动机“最小化”，也就是说，找到一个自动机，它等价于某个给定的自动机，并且使它有尽可能少的状态。这是一个数十年里在开关电路的设计方面的很重要的问题，原因是电路的成本（电路所占有的芯片面积）趋向于随着电路所实现的自动机的状态数减少而减少。 证明语言的非正则性 我们已经确认正则语言类至少有四种不同的描述方法，它们分别是：DFA所接受的语言类、NFA所接受的语言类、ε-NFA所接受的语言类以及正则表达式所定义的语言类。 然而并不是所有的语言都是正则语言。在本节中，我们将会介绍一个强有力的技术，叫做“泵引理”，它能够证明某个语言不是正则的。接着我们会给一些非正则语言的例子。在第4.2节中我们将会看到怎样先后使用泵引理和正则语言的闭包性质来证明另外一些语言不是正则的。 正则语言的泵引理 我们考虑语言L01 = {0n1n | n≥1}。该语言包含所有如下形式的串：01, 0011, 000111等等，也就是有一个或多个0后面跟着相同数目的1所构成的串。我们将要证明L01不是正则语言。一个靠直觉得到的证据是：如果L01是正则的，那么L01就是某个DFA A的语言。该自动机有若干个状态，比如说有k个状态。想象一下，当把由k个0组成的串作为输入时，这个自动机在分别消耗了k+1个输入的不同前缀ε, 0, 00, …, 0k时所处在的k+1个状态，因为它总共只有k个不同状态，所以由鸽笼原理可知在它读入了其中两个不同的前缀比如0i和0j之后应该处在同一个状态q。 然而，假设在它读入了i或者j个0之后，接下来的输入是若干个1。当读入了i个1之后，如果开始它读入了i个0的话，那么它必须接受，否则如果开始它读入了j个0的话它必须不接受。而当开始读入1时它处在的状态是q，因此它无法“记住”刚才读入的是i个还是j个0，因此我们可以“愚弄”A从而使它犯错误：接受本不该接受的或者没有接受本应该接受的。 上面的证明是非形式化的，但我们可以使它更加准确。不过，可以通过一个更一般的结果来得到跟上面同样的结论，这个更一般的结果如下： 定理4.1：（正则语言的泵引理）设L是正则语言，则存在与L相关的常数n满足：对于任何L中的串w，如果|w|≥n，则我们就能够把w打断为三个串w=xyz使得： y ≠ ε。 |xy| ≤ n。 对于所有的k ≥ 0，串xykz也属于L。 换句话说，我们总能够在离w的开始处的地方找到一个非空的串y，然后可以把它作为“泵”，也就是说，重复y任意多次，或者去掉它（k=0的情况），而所得到的结果串仍然输入L。 证明：假设L是正则的。那么存在某个DFA A使得L = L(A)。假设A有n个状态。考虑长度不小于n的串w = a1a2…am，其中m ≥ n且每个ai都是输入符号。对于i = 0, 1, …, n定义状态pi为，其中δ是A的转移函数，q0是A的开始符号。也就是说，pi是当A读入了w开头的i个符号后所处在的状态。注意p0 = q0。 由鸽笼原理，对于i = 0, 1, …, n，相应的n+1个pi不可能全都不同，因为总共只有n个不同的状态。因此，我们能够找到两个不同的整数i和j，满足0 ≤ i j ≤ n以及pi=pj。现在，我们就可以把w打断为w=xyz如下： x = a1a2…ai。 y = ai+1ai+2…aj。 z = aj+1aj+2…am。 换句话说，x把我们带到pi一次，y把我们带离pi后再带回pj（因为pi就是pj），然后z是w剩下的部分。这些串和状态之间的关系如图4.1所示。注意x可以为空，也就是i=0的情况。同样z也可以为空，也就是j=n=m。然而，y不可以为空，因为i严格小于j。 开始 图4.1：每个比状态数长的串一定会导致一个重复的状态 现在，考虑当自动机A接受输入xykz时所发生的事，其中k是任何大于或等