动机
有限自动机可以读入任意长的输入,但它只有有限多个状态。在足够长的输入上,它必然会重新访问某个状态。夹在两次访问之间的那一段输入可以被重复或删除,而不会改变其余计算的起点。这个简单的循环观察,成为证明某些语言不能被任何有限自动机识别的有力方法。
这一证明技巧是一场选择的博弈。假想的自动机决定泵长度;我们选取一个足够长的单词;对手给出该单词的一个合法分解;最后我们必须找到一个重复次数,使得该单词落到语言之外。只用一个方便的分解是不够的,因为未知的自动机可能给出不同的循环。我们还将看到一个通过了泵检验的非正则语言,可见该检验有明确的局限。
定义与定理
定义 1.4.1
(单词的幂与长度)
固定有限字母表 。对于单词 ,记 ,;当 为非负整数时, 表示 个 的连接。单词 的长度记作 。
定理 1.4.2
(正则语言的泵引理)
若 是正则的,则存在整数 ,使得每个满足 的 都有分解 ,满足 、,并且对每个整数 都有 。
量词的顺序十分重要。同一个 必须对 中每个足够长的单词都适用。对每个这样的单词,合适的分解可以依赖于该单词,而且之后每个重复次数都必须保持该单词属于语言。引理并没有说每个分解都可行。它也允许删除,因为 包含在内。
定理 1.4.3
(用于非正则性证明的逆否命题)
若对每个整数 ,都存在 且 ,使得每个满足 且 的分解 都存在某个 使 ,则 不是正则的。
逆否命题中的重复次数可以依赖于分解。在特别简洁的论证中,像 这样的同一个次数对所有合法分解都有效。如果对手给出非法分解(例如 ),则无需考虑。
证明:重复的状态产生循环
证明
(重复的状态给出循环)
设 被一个有 个状态的完全确定型有限自动机识别。令 。设 的长度至少为 。考虑读完长度为 的各前缀之后所经过的 个状态。由鸽巢原理,其中有两个相同。选取出现这一重复的下标 。令 为前 个符号, 为接下来的 个符号, 为剩余的后缀。
于是 ,且 。读入 会使自动机回到读完 后所处的同一状态。对任意 ,恰好读入 次 之后自动机仍停留在该状态;随后读入 时,所走的路径与原单词一样通向接受。因此对所有 都有 。
这一证明为每个正则语言给出了一个泵长度,但不一定是最小的。当 不含长度至少为 的单词时它同样成立:此时关于这类单词的全称命题是空真的。非确定型自动机也不构成问题,因为每个正则语言都有与之等价的有限确定型自动机。
证明透视
为什么鸽笼计数给出合法的循环
这个证明有一个不显然的步骤:它数的是前缀,而不是状态。长度为 的 个前缀经过 个状态,比可用的 个状态多一个,所以必有两个相同;这正是循环落在前 个符号之内、从而 的原因。严格不等式 使 非空,循环才真的消耗输入。重复循环用到确定性:从重复出现的状态出发,读入 总是沿同一条路径回到该状态,所以循环可以走任意多次,之后 再沿原来的路径通向接受。最后, 是 的某台固定自动机的状态数,因此不依赖于 ;这就是引理中量词的顺序。若状态集不是有限的,鸽笼步骤就没有可数的东西。
例题详解
例题 1.4.4
(两个块中的数目相等)
令 。假设它是正则的,并设 为其泵长度。选取 。每个合法分解都满足 ,所以其非空的 只由符号 构成:对某个 有 。向下泵(取 )得到 ,两个块的长度不同,它不属于 ,与引理矛盾。因此 不是正则的。
这个单词依赖于 ,但它是在分解之前选定的。论证一次性处理了每个合法的 ,并没有假设循环的长度为一。
例题 1.4.5
(平方数长度的一元语言)
令 。给定任何假设的泵长度 ,选取 。合法的 长度为 ,其中 。再向上泵一次,取 。新的长度 严格大于 ,并严格小于 。因此它不是平方数。这证明了即使在只有一个符号的字母表上, 也是非正则的。
相邻平方数之间的间隙是关键所在。仅仅说重复一个块会改变平方数的长度是不够的,因为某些改变可能得到另一个平方数。
例题 1.4.6
(回文需要匹配相距遥远的符号)
令 为 上的全部回文。对于泵长度 ,选取 。该单词是回文,且长度足够。每个合法的非空 都落在前 个字母之中,且对某个 有 。向下泵得到 ,它不是回文,因为唯一的 两侧的 的个数不同。因此 是非正则的。
例题 1.4.7
(正则语言也有不好的分解)
取 与单词 。取 ,分解 、、 就长度限制而言是合法的,但 不在 中。这并不与正则性矛盾:一个好的分解是 、、,对它而言,对每个 , 都仍在 中。引理保证的是存在合适的分解,而不是原单词中所有可能的循环都可行。
选取有效的单词
第一次尝试选取的见证单词,可能给了对手过多自由。例如,为研究数目相等的条件而使用 ,会引入多个块,必须逐一追踪它们的变化。较短的单词 则把整个被允许的前缀都放在第一个块里。这样,证明在不确切知道 从哪里开始、有多长的情况下,就知道了 的形式。相反,选取像 这样固定的单词,无法战胜任意大的泵长度:它可能比 还短,此时引理对它什么也没有说。
有时有用的重复次数是删除,有时增长更清晰。在平方数的论证中,从 中删去至多 个符号,对 恰好也避开了前一个平方数,但 的情形需要另外处理。向上泵则统一地使用简单的不等式 。好的做法是写出新的确切长度,找出相邻的两个允许长度,并证明严格不等式。如果泵后的单词长度正确却违反了顺序条件,就应当给出关于顺序的论证。
长度条件 是信息的来源,而不是 从单词开头开始的保证。前缀 的长度可以是从零到 的任何值。对于一元前缀,这种不确定性无关紧要:每个非空的连续子串都由同一个字母构成。对于较复杂的前缀,证明必须既覆盖跨越内部边界的循环,也覆盖位于单个块内的循环。
其他工具有时能更容易地得出同样的结论。例如,若有一族前缀,它们两两要求不同的未来响应,就可以确立有无穷多个可区分的状态。这种方法通过状态数的下界来证明非正则性,而不是通过选取重复。泵引理依然有用,因为一个简短而量词正确的单词论证,往往能揭示学生需要理解的具体记忆需求。
通过检验的非正则语言
反例模式
通过泵检验并不蕴涵正则
一个诱人的逆命题是:只要语言中每个足够长的单词都可以泵,语言就是正则的。泵引理是正则性的必要条件,而不是充分条件。考虑 上的语言
它在 时满足泵结论。对于 中任意非空单词,取 ,并令 为其第一个符号。若单词以 开头,则泵只改变开头 的个数。只要至少还剩一个 ,原有的等式 仍然成立;若一个 也不剩,则另一种情形 使结果无论如何都是语言的成员。若单词以 或 开头,则它已经有 ,重复或删除这第一个符号既保持块的形式,也保持 这一情形。因此对所选的分解,所有重复次数都有效。
然而 是非正则的。若它是正则的,则它与正则语言 的交,由有限自动机的乘积构造,也是正则的。但这个交恰好是 。设该交集的泵长度为 ,选取 。合法的非空 包含在前 个符号之内,这些符号都位于 块之前。若 含有开头的 ,向下泵就删去了唯一的 ;否则它删去一个或多个 ,而保留 个 。无论哪种情形,结果都在该交集之外。于是泵引理证明该交集是非正则的,矛盾。
这一构造展示了一个有用的证明策略:与一个简单的正则语言取交,以暴露语言中困难的部分。它也恰好说明了,为什么仅仅在每个长单词中找到可泵的片段,并不能构造出有限自动机。
常见错误
常见错误
(自行选定分解)
非正则性证明不能自行选定分解,再说明某一次泵失败:自动机的循环可能对应另一个分解。正确的做法是选取一个单词,使其前 个位置约束所有可能性,然后陈述每个合法的 必须是什么样子。
常见错误
(先看到单词才选 )
不要对调泵长度与单词的角色。我们不能在看到有利的单词之后才选择 。在正则性的假设之下,我们接受任意一个有效的 ,并构造依赖于它的单词。我们也不必指出实际的自动机或其状态数;矛盾对每个正的 都成立。
常见错误
(未依语言定义就断言泵出语言之外)
泵出语言之外必须依据语言的定义来论证。对于平方数长度的例子,间隙的计算说明不会落到另一个平方数。对于块语言,必须检查块的顺序以及各计数之间所需的关系。仅仅改变单词本身,并不足以证明它不是成员。
文法可以同步重复两段,有限状态集却做不到。
通往推广的路径
对上下文无关语言,什么改变了?
文法可以同步重复两段,有限状态集却做不到。
对上下文无关语言,重复涉及两段。存在 ,使每个 ()都可写成 ,满足 、,且对所有 有 。这与上下文无关的 并不矛盾,却能推翻 :在 中,窗口 不可能同时碰到 和 ,因此泵动时某个字母的个数不变,而另一个改变。
总结
有限状态的重复,使每个足够长的被接受单词的前 个符号之内都存在一个循环。要证明非正则性,就要迫使每个可能的循环落在这样一个区域:改动它会破坏成员资格。保持量词的原有顺序,并使用像零或二这样具体的次数。逆命题不成立:仅仅通过泵性质并不能保证正则性。
练习
快速检查
(证明 是非正则的。)
选取一个前 个符号全是 的单词。
解答 · 答案
假设存在泵长度 ,并选取 。每个合法的 都是 ,其中 。向下泵得到 。成员资格要求 ,而这对 不可能成立。这与引理矛盾。
快速检查
(利用相邻二的幂之间的间隙,证明 是非正则的。)
向上泵一次,并把新长度与 、 比较。
解答 · 答案
对任意假设的 ,选取 。因为 ,它的长度足够。每个合法循环的长度 满足 。取 来泵,得到长度 。由于 ,该长度严格介于 与 之间,因而不是二的幂。该矛盾证明了非正则性。
快速检查
(对于 ,给出一个泵长度,并为每个足够长的单词给出有效的分解。须处理以任一字母开头的单词。)
泵长度取 已经足够;令 为第一个符号。
解答 · 答案
取 。对于以 开头的非空单词,选取 与 ;重复或删除这个开头的 ,剩下的是一个 块后接一个 块。对于以 开头的非空单词,该单词不含 ,选取第一个 作为 ,剩下的是 中的单词。每个所需的泵次数都保持成员资格。
快速检查
(对于上面的语言 ,解释为什么单词 在删去开头的两个 之后仍属于 ,尽管它原本的成员资格也用到了 。)
回想 的定义是一个析取。
解答 · 答案
删去两个 得到 ,其开头 的个数为零。 的定义使用的是包容的“或”,所以 这一情形就足够了。在这个特定单词中,等式 也仍然成立,但开头 个数为零这一情形,即使在数目不等时也会使其成为成员。