形式语言与自动机理论-08-上下文无关语言的泵引理

考虑语言 \(L \subseteq \Sigma^*\)。假设 \(L\) 是上下文无关的,那么存在下推自动机 \(M\) 识别该语言。记 \(M\) 的状态集为 \(Q\),则 \(p = \big| Q \big| \in \mathbb{N}\) 有限。然而 \(L\) 中可有任意长的字符串 \(s\),因此若取 \(s \in L\) 使得 \(l = \big| s \big| > n\),则根据鸽子洞原理,由 \(s\) 标记的路径上至少有一个状态重复,因此该路径上有包含该状态的环。由于该环路可任意重复无数次,故总体来讲,一整次循环要么净入栈,要么净出栈。若是前一种情况,则该循环之后的路径上必然存在另一净出栈的循环;而后一种情况类似。

\(s\) 从起始节点到达第一循环的路径由输入字符串 \(u\) 标记,完成数次入栈循环的路径由 \(v\) 标记,两循环之间的路径由 \(w\) 标记,完成数次出栈循环的路径由 \(x\) 标记,从第二个循环到达接受状态的路径由 \(y\) 标记,于是有以下结论:

对于任何上下文无关语言 \(L\),存在被称为泵长度的常数 \(p\),使得对于任何长度至少为 \(p\)\(s \in L\),其可写成如下形式:

\[ s = uvwxy \]

其中有:

  1. \(v \ne \varepsilon \vee x \ne \varepsilon\)

  2. \(\big| vwx \big| \le p\)

  3. \(\forall i \ge 0. uv^iwx^iy \in L\)

即,若 \(v\) 由完成 \(n\) 次入栈循环的路径标记,\(x\) 由完成 \(m\) 次出栈循环的路径标记,那么由于 \(m\) 次出栈循环刚好可以将 \(n\) 次入栈循环入栈的符号出栈,则类似的断言对 \(mi\)\(ni\) 也成立。因此 \(v\)\(w\) 可重复相同多的次数而所得到的字符串依旧在 \(L\) 中。

证明语言 \(L = \{a^ib^ic^i | i \ge 0\}\) 不是上下文无关的。

假设 \(L\) 是上下文无关的,设 \(L\) 的泵长度为 \(p\)

于是取字符串 \(s = a^pb^pc^p\),有 \(s \in L\)

显然 \(s\) 符合泵引理的条件 1、2.

\(v\)\(x\) 包含多于一种字符,则 \(uv^2wx^2y \not\in a^*b^*c^* \supset L\),于是 \(uv^2wx^2y \not in L\).

\(v\)\(x\) 皆各仅包含一种字符,那么 \(uv^2wx^2y\) 则不可能包含同样数量的 \(a, b, c\),因此也有 \(uv^2wx^2y \not\in L\)

因此 \(L\) 不可能是上下文无关的的。