形式语言与自动机理论-05-正则语言的泵引理

考虑语言 \(L \subseteq \Sigma^*\)。假设 \(L\) 是正则的,那么存在有限状态自动机 \(M\) 识别该语言。记 \(M\) 的状态集为 \(Q\),则 \(n = \big| Q \big| \in \mathbb{N}\) 有限。然而 \(L\) 中可有任意长的字符串 \(s\),例如若取 \(\Sigma = \{0\}\), \(L = \Sigma^*\),则 \(L\) 为所有自然数的一进制表示的集合。因此若取 \(s \in L\) 使得 \(l = \big| s \big| > n\),则根据鸽子洞原理,由 \(s\) 标记的路径上至少有一个状态重复,因此该路径上有包含该状态的环。于是可以重复任意多次 \(s\) 中标记该环的子字符串,且产生的字符串仍然在 \(L\) 中。

于是有以下结论:

对于任何正则语言 \(L\),存在被称为泵长度的常数 \(n\),使得对于任何长度至少为 \(n\)\(x \in L\),其可写成如下形式:

\[ x = p \cdot q \cdot r \]

其中有:

  1. \(q \ne \varepsilon\)

  2. \(\big| p \cdot q \big| \le n\)

  3. \(\forall k \ge 0. pq^kr \in L\)

给出一正则语言的泵长度并非显而易见,然而由于泵引理中对“长度至少为 \(n\)”的要求,通常使用该引理时直接取 \(n\) 为识别 \(L\) 的状态机的状态数量。事实上,泵长度为状态机中到达并完成一个环路最长的路径长度。

另外,根据否定前件,若 \(L\) 中不存在任何可写成泵引理要求形式的字符串,那么一定有 \(L\) 是正则的。特别地,对于有限的语言,由于识别该语言的状态机中必然不存在环路,那么这样的语言的泵长度为 \(\infty\),而由于不存在无限长度的字符串,因此直接有有限语言为正则的。

证明语言 \(L = \{0^i1^i | i \ge 0\} = \{\varepsilon, 01, 0011, 000111, \dots\}\) 不是正则的。

假设 \(L\) 是正则的,设 \(L\) 的泵长度为 \(n\)

于是取字符串 \(x = 0^n1^n\),有 \(x \in L\)

由于要求 \(\big| pq \big| \le n\),因此只有可能有 \(p = 0^t, t \ge 1\),然而 \(pq^2r = a^{n+t}b^n \not\in L\)。因此 \(L\) 不可能是正则的。

注意:

  1. 正则语言的泵引理只能用来证明某个语言不是正则的,事实上存在满足泵引理条件的非正则语言。因此证明语言的正则性要求给出描述它的正则表达式或者识别它的状态机。

  2. 有些时候存在多种符合泵引理条件 1 和 2 的分解 \(x\) 的方法。仅当所有方法皆无法满足条件 3 时才可得出矛盾的结论并证明给定语言的非正则性。

  3. 有的时候也需要依赖正则语言的封闭性证明给定语言的非正则性。下面给出如此情况的例子

考虑 \(\Sigma = \{0, 1\}\),记语言 \(L\) 为所有包含相同数量的 \(0\)\(1\) 的字符串的集合,证明该语言的非正则性。

假设 \(L\) 是正则的,那么根据封闭性,有 \(L \cap 0^*1^* = \{0^i1^1 | i \ge 0\}\) 同样是正则的。然而如前文可证后者是非正则的,于是有 \(L\) 不可能是正则语言。