倒数第 n 位为 a 的正则语言

March 02, 2019

《编译原理》中的例 3.25,识别正则语言

Ln=(ab)a(ab)n1L_n = (a|b)^*a(a|b)^{n-1}

即倒数第 nn 位为 aa 的正则语言,识别它的确定性有限自动机至少需要 2n2^n 种状态。

为什么?

简单来说,DFA 的状态相当于记录了一个队列:队列中是最近出现的 nn 个字符。每遇到新字符,入队,同时丢弃掉队首字符;如果被通知读取结束,那么弹出队首字符确认是不是 aa

由于接收读取结束通知的时间不确定,所以队列中的所有字符都有意义。一共有 2n2^n 种不同的队列状态。

证明思路如下:

假设我们有一个识别倒数第 33 位为 aa 的 DFA,但只有 77 种状态。有一些字符串,前缀 33 位可以有下 88 种情况:

  1. aaa...aaa...

  2. aab...aab...

  3. aba...aba...

  4. abb...abb...

  5. baa...baa...

  6. bab...bab...

  7. bba...bba...

  8. bbb...bbb...

当读取了开始 33 个字符时,由于鸽笼原理,在如上 88 种前缀中必有至少 22 种情况,我们的 DFA 位于同一状态 SS,如果这 22 种前缀:

  • 11 位不相同(比如 abbabbbabbab):构造两个字符串,分别都只有这两个前缀,则 SS 无论是接受还是拒绝都矛盾。

  • 11 位相同,第 22 位不同(如 babbabbbabba):构造两个字符串以此两种为前缀,加一个相同字;那么此 DFA 读取最后一个字符后最终状态 SS' 必然相同, SS' 接受还是拒绝都矛盾。

  • 1,21, 2 位相同,第 33 位不同(如 abaabaabbabb):同理,后面添两个相同字符串。

一般地,构造方式是:以这两种前缀为基础构造字符串,寻找它们中第一个不同的字符,后面随便填满一些相同的字符串,使之成为我们构造的两个字符串的倒数第 nn 位。

识别这两种字符串的 DFA 最终都会到同一个状态,然而这两个字符串倒数第 nn 位一个是 aa,一个是 bb。于是得出矛盾。