1. 识别非正则语言¶
1.1. 识别非正则语言¶
到目前为止，我们已经花了大量时间研究描述语言的多种方法。 但这些方法基本上都大同小异，因为它们描述的都是同一类语言：正则语言。 我们已经多次暗示，并非所有语言都是正则的。 所以，现在我们终于要认真面对下列两件事：（1）见识一些真正的非正则语言； （2）使用能够帮助我们证明给定语言是非正则的工具。
我们即将把这份幻灯片中的证明形式化为一种工具， 用来证明某些语言是非正则的。 但首先，让我们再多探讨一下 DFA 中的循环与正则语言之间的关系。
首先，我们知道循环并不总是导致语言非正则。 事实上，带循环或不带循环的 DFA 与无限语言或有限语言之间存在一种简单的关系。 也就是说，有限语言可以被任何在通向接受状态的路径上没有循环的 DFA 接受。 带有这种循环的 DFA 所接受的语言不可能是有限的， 因为我们无法控制机器绕循环运行的次数。 也就是说，机器可以接受有限语言中的所有串，但它还必须接受更多的串。 反过来，任何无限语言只能被带有一个或多个循环的 DFA 接受。
接下来，考虑我们可以用 DFA 来“计数”有限数量的东西。 例如，我们可以构造一个 DFA，使串中永远不会出现三个连续的 a， 或者使串中最多只有三个 a。 只要我们要计数的是固定数量（或最大数量）的东西，就没有问题。 当然，这样的机器可以在通向接受状态的路径上有循环。 例如，限制 a 的语言可能有一个循环，允许任意数量的 b。 循环影响计数过程是 不可能 发生的。 所以，数到三个 a 的那一系列状态可以包含一个循环来处理任意数量的 b， 因为这不会扰乱 a 的计数。 但如果循环中包含 a，那么我们就会“失去计数”，不知道已经看到了多少个 a， 因为我们无法控制经过循环的次数 （或者更准确地说，我们必须接受那些经过循环任意次数而增加了额外字符的串）。
1.2. 泵的概念¶
1.3. 泵引理¶
如何使用泵引理证明 L 不是正则语言：反证法
假设 L 是正则语言。
因此 \(L\) 满足泵引理。
选择一条足够长的串 \(w \in L\)，\(|w| \ge m\)。 记住，\(m\) 与机器中状态的数量有关， \(m\) 要足够大，以至于它必然触发至少一个循环。 我们选择哪条串至关重要。 我们必须选择一条会产生矛盾的串。 只要找到任何这样的串，证明就成功了， 即使存在其他无法让证明成立的串也没关系。
证明对于我们的串，\(w\) 不存在任何 \(xyz\) 划分 （我们必须考虑所有可能的划分），使得 \(|xy| \le m\)、\(|y| \ge 1\)，并且对 所有 \(i \ge 0\) 都有 \(xy^iz \in L\)。
如果我们证明了不存在任何可能的划分，那么我们就得到了矛盾！
\(\Rightarrow L\) 不是正则的。
不幸的是，泵引理是单向的： 对于（某些）语言，我们可以用泵引理证明它们 不是 正则的。 但我们不能借助泵引理来证明某个语言是正则的。 而且泵引理并不是万能药，它并不能总能让我们确定某个非正则语言确实是非正则的。 它只是工具箱中的一件工具而已。
1.4. 一些泵引理示例¶
现在让我们看一个不那么容易的例子，因为我们无法使用那个简单策略。 这意味着我们必须选择一条串 \(w\)， 它会导致分解为 \(xyz\) 时出现多种情况， 我们必须逐一处理这些情况才能完成证明。
1.5. 泵引理对抗博弈¶
这里是以对抗论证方式看待这一问题的角度。 你的目标是建立矛盾（证明该语言不是正则语言），而对手试图阻止这个证明。 总体思路是：证明中那些要求任意值都能成立的地方，是对手走的棋。 证明中由证明者选择值的地方，是证明者走的棋。
博弈中的步骤是：
对手选择 $m$。 [记住，证明必须对任意的 $m$ 都成立。]
我们在 $L$ 中选一条长度等于或大于 $m$ 的串 $w$。 [记住，只要 $win L$ 且 $|w|ge m$，我们就可以自由选择任何 $w$。]
对手选择分解 $xyz$，使得 $|xy|le m,|y|ge1$。 [记住，证明必须对任何分解都成立，所以我们可以指望对手会做出对我们赢得博弈最不利的选择。]
我们尝试选择 $i$，使得泵出的串 $w_i=xy^iz$ 不在 $L$ 中。 [记住，$w = xy^iz$ 必须对所有 $i$ 的值都属于该语言，所以我们可以挑一个能用的。] 如果我们能做到这一点，我们就赢了（$L$ 不是正则语言）。
如我们所看到的，这些对抗博弈是基于角色的博弈， 我们 致力于证明该语言是非正则的， 对手 则致力于阻止我们。
为了把对抗博弈与泵引理证明联系起来， 我们把证明分成如下步骤：
在下面的对抗博弈中，有一列可供选择的语言。 其中有些是正则语言，有些是非正则语言。 如果你认为该语言是非正则的，那么你应该选择让计算机先走。 这样计算机选择 \(m\)，然后你选择一条能够让你完成证明的串 \(w\)， 这样你就赢了。
然而，如果你认为某个语言是正则的，那么你应该选择先走 （也就是说，你选择 \(m\) 的值，这实际上是在证明的语境中选择识别该语言的机器）。 在这种情况下，你要走出能够阻止证明的棋 （对于计算机选择的任何串 \(w\)，你都要为 \(xyz\) 做出有效的分解）， 这样你就赢了。
1.6. 使用闭包性质证明 L 非正则¶
有时我们无法用泵引理证明某个语言是非正则的。 也许是我们在开始时找不到合适的串，或者我们想不明白为什么会矛盾的论证。 无论哪种情况，有其他工具来证明语言非正则都是有帮助的。 所以这里介绍另一种我们可以使用的工具。
回想一下，正则语言在特定运算下是封闭的。 例如，两个已知正则语言的并集本身就是正则语言。 这是使用闭包性质证明语言正则的一个例子： 如果 \(L = L_1 \cup L_2\)，而我们已知 \(L_1\) 和 \(L_2\) 是正则的， 那么 \(L\) 也必然是正则的。
类似地，我们可以用闭包性质来证明某个语言 不是 正则的。 其思路是使用特定的运算，推导出一个我们已经知道是非正则的语言。
再做一个快速的例子。 使用闭包运算证明 \(L_1 = \{a^nb^na^n\ |\ n > 0\}\) 是非正则的。
假设 \(L_1\) 是非正则的，然后推导出矛盾。
目标是尝试构造 \(\{a^nb^n | n > 0\}\)，我们知道它不是正则的。
注意，尝试与 \(\{a^{*}b^{*} \}\) 求交集 并不 能帮我们， 因为这个交集只是空集。
设 \(L_2 = \{a^{*}\}\)。\(L_2\) 是正则的，因为它是用正则表达式定义的。
现在定义 \(L_3 = L_1 \backslash L_2 = \{a^nb^na^p\ |\ 0 \le p \le n, n > 0\}\)。 这里使用了右商运算，我们知道它在正则语言上是封闭的。 在这个例子中，我们只是从 \(L_1\) 的末尾剪掉一些 a。 有时我们把 \(L_1\) 末尾的 a 全部 剪掉。
由交集的闭包性，\(L_4 = L_3 \cap \{a^{*}b^{*}\} = \{a^nb^n\ |\ n > 0\}\) 是正则的。 注意，我们必须先做剪掉字母的那一步， 因为仅仅把 \(L_1\) 与 \(a^*b^*\) 求交集并不能得到我们想要的结果。
我们已经证明 \(L_4\) 不是正则的。矛盾。
\(\Rightarrow L_1\) 不是正则的。
1.7. 值得思考的问题¶
回顾一下我们现在已知的：有些语言是正则的，有些语言是非正则的。 正则语言可以用若干种可互换的方式中的任意一种来表示。 有些非正则语言可以用泵引理、闭包性质等工具证明是非正则的。
这些事实应该引导我们提出一些更广泛的问题。 特别是，是否每种语言要么是正则的、要么是非正则的？ 如果是这样，我们是否总能 判定 每种语言是正则还是非正则？
记住语言是什么：它不过是串的集合。 大多数串的集合是无限的，因为无限串集合的数量远多于有限串集合的数量。 （这个论断 真的 成立吗？这真的有道理吗？有限串集合有无限多个。） 一个要点是，语言并不仅仅是可以被描述的那些串集合，例如正则表达式 （当然不是，因为并非所有语言都是正则的）。 语言甚至也不仅仅是那些可以用英语、或英语与数学符号混合来描述的集合。
我们稍后会回到这些问题以及其他类似的问题。 它们关系到图灵可判定语言与图灵可接受语言、P 与 NP， 以及关于语言的什么问题可判定、什么问题不可判定。 到本书结束时，我们应该会对这些问题有一些答案， 并更好地理解我们在认识语言方面的极限。 .. odsascript:: DataStructures/PIFrames.js .. odsascript:: AV/PIFLA/NonRegular/introNonRegularFS.js .. odsascript:: AV/VisFormalLang/NonReg/Proof1NonRegularCON.js .. odsascript:: AV/PIFLA/NonRegular/introPumpingFS.js .. odsascript:: AV/VisFormalLang/NonReg/PumpingLemmaCON.js .. odsascript:: AV/PIFLA/NonRegular/PLExampanbnFS.js .. odsascript:: AV/PIFLA/NonRegular/PLExampwwRFS.js .. odsascript:: AV/PIFLA/NonRegular/PLExampa3bncn3FS.js .. odsascript:: AV/PIFLA/NonRegular/ClosPropFS.js .. odsascript:: AV/PIFLA/NonRegular/ClosPropEx1FS.js .. odsascript:: AV/PIFLA/NonRegular/ClosPropEx2FS.js
