5.1. 识别非正则语言¶
5.1.1. 识别非正则语言¶
我们如何证明一个语言是正则的？我们的工具箱中有多种方法。
构造一个 DFA。
构造一个 NFA。
写出一个正则表达式。
写出一个正则文法。
从已知的正则语言出发，应用已知对正则语言保持闭包的运算。
既然有这么多构造正则语言的方法，那么是否存在不是正则的语言呢？（我们居然会关心这个问题，这一事实本身就暗示着这种情况是可能发生的。）
我们先从一些基本问题开始。首先，如果一个语言 \(L\) 是有限的，那么 \(L\) 是正则的吗？是的！所有有限语言都是正则的。[为什么？]
如果 \(L\) 是无限的，那么 \(L\) 是正则的吗？它可能是，也可能不是。例如，\(L_1 = \{a^nb^m | n > 0, m > 0 \} = aa^*bb^*\) 就是一个无限的正则语言。
那么，之前提到过的那个没有明确结论的语言呢？ \(L_2 = \{a^nb^n | n > 0 \}\) 是一个无限语言。[我们怎么知道这一点？]
证明 \(L_2 = \{a^nb^n | n > 0 \}\) 不是正则的。下面的可视化呈现了对此的证明 1。
5.1.1.1. 泵的概念¶
证明 2（反证法，但表述略有不同）
证明：假设 \(L_2\) 是正则的。那么存在一个识别 \(L_2\) 的 DFA \(M\)。\(M\) 有有限个状态，假设有 \(k\) 个状态。考虑一条长串 \(a^kb^k \in L_2\)。因为有 \(k\) 个状态和 \(k\) 个 a （后面跟着若干 b），当沿着 \(a^k\) 的路径行进时，\(M\) 中的某个状态必然会被访问不止一次。在这种情况下，路径上存在一个含有一个或多个 a 的循环 （假设有 \(t\) 个 a，其中 \(t > 1\)）。假设我们从初始状态出发，沿着 \(a^kb^k\) 的同一路径行进， 但对这个 a 的循环多走一次（“泵”这个循环）。我们最终会停在 \(a^kb^k\) 所停的同一个终态上。因此，字符串 \(a^{k+t}b^k\) 会被 \(M\) 接受， 但这个字符串不在 \(L_2\) 中。矛盾！所以，\(L_2\) 不是正则的。
在证明 2 中，我们引入了绕循环行进时“泵”字符串的概念。循环正是我们得到无限语言的方式。它们也是我们失去计数能力、从而失去区分被处理字符串的各种性质的能力的原因。
换个角度来说，DFA 的“记忆”就明确地体现在它的状态集合中。由于状态的数量是有限的，记忆也是有限的。此外，传统编程语言中的程序可以有一个整数（从概念上说它至少能存储无数个值，即使实际上并非如此），而 DFA 没有这样的东西。
一般来说，考虑带或不带循环的 DFA。如果没有循环，所接受的语言是有限的。如果有一个或多个循环，那么语言就是无限的。但实际上，我们对这种语言还能再多说一点。为了解释这个概念，假设恰好只有一个循环。在这种情况下，这个循环可能被跳过、执行一次、或执行多次。
当这个循环恰好执行一次时，我们可以把该 DFA 接受的任何字符串看作具有形式 \(w = w_1vw_2\)，其中 \(v\) 表示字符串中被这个循环捕获的部分。现在，如果跳过这个循环，我们得到 \(w = w_1w_2\)；如果执行两次，我们得到 \(w = w_1v^2w_2\)。一般来说，DFA 接受所有形如 \(w = w_1v^*w_2\) 的字符串。
5.1.1.2. 泵引理¶
如何使用泵引理证明语言 L 不是正则的：
我们将使用反证法来证明。所以我们先假设 L 是正则的。因此 \(L\) 满足泵引理。选择一条长串 \(w \in L\)，\(|w| \ge m\)。 字符串的选择至关重要。我们必须选择一条能产生矛盾的字符串。证明 \(w\) 没有 任何 \(xyz\) 划分 （我们必须考虑所有可能的划分）能够满足 \(|xy| \le m\)、\(|y| \ge 1\)，并且 \(xy^iz \in L \forall i \ge 0\)。如果我们证明了不存在任何可能的划分， 那么我们就得到了矛盾！\(\Rightarrow L\) 不是正则的。
不幸的是，泵引理是单向的：对于（某些）语言，我们可以用泵引理证明它们 不是 正则的。但我们不能借助泵引理来帮助我们证明某个语言是正则的。而且泵引理也不是判断某个语言为非正则的万灵药。它只是工具箱中的一件工具而已。
重要的是要理解，泵引理说的是：存在 某种 满足这些条件的（字符串分解）方式。只挑选一个你自己喜欢的 \(m\) 值（对这个值，语言看起来"不可能是正则的"）是不够的。你必须证明 任何 令人满意的 \(m\) 都不 可能存在。
这里是以对抗论证的方式来看待这个问题。你的目标是建立矛盾（即证明该语言不是正则的），而对手则试图阻止这个证明。博弈中的步骤是：
对手选择 \(m\)。
我们在 \(L\) 中选择一条长度等于或大于 \(m\) 的字符串 \(w\)。 只要 \(w \in L\) 且 \(|w| \geq m\) 成立，我们就可以自由选择任何 \(w\)。
对手选择分解 \(xyz\)，使得 \(|xy| \leq m, |y| \geq 1\)。 对手会做出对我们赢得博弈最不利的选择。
我们尝试选择 \(i\)，使得泵出的字符串 \(w_i = xy^iz\) 不在 \(L\) 中。 如果我们总能做到这一点，我们就赢了（\(L\) 不是正则的）。
存在 一个常数 \(m > 0\) [＝ 对手 为 \(m\) 选择一个值。]
... 使得 任何 \(w \in L\) 且 \(|w| \ge m\) [＝ 我们 选择自己的 \(w\)。]
... 都可以 分解为三个部分 \(w=xyz\) [＝ 对手 选择 \(xyz\)] （但必须满足关于 \(xy\) 和 \(y\) 的长度条件）
... 使得对 所有 \(i\ge 0\) 都有 \(xy^iz \in L\) [＝ 我们 为 \(i\) 选择一个值。]
下面这个练习让你可以扮演这个对抗论证"博弈"中的任意一方。
5.1.1.3. 使用闭包性质证明 语言 \(L\) 不是正则的¶
利用正则语言的闭包性质，构造一个"应该"是正则的、但你已经证明它不是正则的语言。矛盾。
证明提纲：假设 \(L\) 是正则的。对 \(L\) 和其他正则语言应用闭包性质，构造出一个你确定不是正则的语言 \(L'\)。闭包性质 \(\Rightarrow L'\) 是正则的。矛盾。所以 \(L\) 不是正则的。
