8.1.1. 上下文无关语言的性质¶

下列哪些语言是上下文无关语言？

• \(L = \{a^nb^nc^j \mid 0 < n\le j\}\)

  备注

  非上下文无关语言

• \(L = \{a^nb^ja^nb^j \mid n>0, j>0\}\)

  备注

  非上下文无关语言

• \(L = \{a^nb^ja^kb^p \mid n+j \le k+p, n>0, j>0, k>0, p>0 \}\)

  备注

  上下文无关语言

• \(L = \{a^nb^ja^jb^n \mid n>0, j>0\}\)

  备注

  上下文无关语言

正则语言的泵引理

设 \(L\) 为正则语言，则存在常数 \(m\) ，使得对于 \(w\in L\) 、 \(|w|\ge m\) 、 \(w = xyz\) ，有

• \(|xy| \le m\)

• \(|y| \ge 1\)

• 对于所有 \(i\ge 0, xy^iz \in L\)

我们能够证明 \(a^nb^n\) 不是正则语言。

CFL 的泵引理

令 \(L\) 为任意无限上下文无关语言。则存在一个仅依赖于 \(L\) 的常数 \(m\) ，使得对于 \(L\) 中满足 \(|w| \ge m\) 的每个字符串 \(w\) ，我们可以将 \(w = uvxyz\) 划分为：

\(|vxy| \le m\) ，（子串长度限制）| \(|vy| \ge 1\) ，（ \(v\) 与 \(y\) 不全为空）| 对所有 \(i \ge 0, uv^ixy^iz \in L\)

证明： （概要）

存在一个 CFG \(G\) ，使得 \(L = L(G)\) 。

考虑 \(L\) 中一个长字符串的语法分析树。

对于任何长字符串，某个非终结符 \(N\) 必定在路径中出现两次。

证毕

证明： （反证法）

假设 \(L\) 是上下文无关语言并应用泵引理。| 令 \(m\) 为泵引理中的常数，并考虑 \(w = a^mb^mc^m\) 。注意 \(|w|\ge m\) 。

证明不存在将 \(w\) 划分为 \(uvxyz\) 的方式，使得 \(|vy|\ge 1\) 、 \(|vxy|\le m\) 和 \(uv^ixy^iz \in L\) 对所有 \(i = 0, 1, 2, \ldots\) 成立。

| 情况 1： \(v\) 和 \(y\) 都不能包含 2 个或更多 不同符号。如果 \(v\) 包含 \(a\) 和 \(b\) ，则 \(uv^2xy^2z \notin L\) ，因为在 \(a\) 之前会有 \(b\) 。

因此， \(v\) 和 \(y\) 只能是 \(a\) 、 \(b\) 或 \(c\) （不能混合）。

| 情况 2： \(v = a^{t_1}\) ，则 \(y = a^{t_2}\) 或 \(b^{t_3} (|vxy| \le m)\)

如果 \(y = a^{t_2}\) ， 则 \(uv^2xy^2z = a^{m+t_1+t_2}b^mc^m \notin L\) ，因为 \(t_1 + t_2 > 0, n(a) > n(b)\) （ \(a\) 的数量大于 \(b\) 的数量）

如果 \(y = b^{t_3}\) ，则 \(uv^2xy^2z = a^{m+t_1}b^{m+t_3}c^m \notin L\) ，因为 \(t_1 + t_3 > 0\) ，要么是 \(n(a) > n(c)\) 要么是 \(n(b) > n(c)\) 。

| 情况 3： \(v = b^{t_1}\) ，则 \(y = b^{t_2}\) 或 \(c^{t_3}\) 。| 如果 \(y = b^{t_2}\) ，则 \(uv^2xy^2z = a^mb^{m+t_1+t_2}c^m \notin L\) 因为 \(t_1 + t_2 > 0, n(b) > n(a)\) 。

如果 \(y = c^{t_3}\) ，则 \(uv^2xy^2z = a^mb^{m+t_1}c^{m+t_3} \notin L\) ，因为 \(t_1 + t_3 > 0\) ，要么是 \(n(b) > n(a)\) 要么是 \(n(c) > n(a)\) 。

| 情况 4： \(v = c^{t_1}\) ，则 \(y = c^{t_2}\) 。| 那么， \(uv^2xy^2z = a^mb^mc^{m+t_1+t_2} \notin L\) 因为 \(t_1 + t_2 > 0, n(c) > n(a)\) 。

| 因此，不存在将 \(w\) 分解为 \(uvxyz\) 的方式，使得 \(|vy| \ge 1\) 、 \(|vxy| \le m\) 且对所有 \(i\ge 0\) ， \(uv^ixy^iz\) 属于 \(L\) 。

这是一个矛盾，因此， \(L\) 不是上下文无关语言。证毕。