动机
有限自动机读入一个足够长的单词时,必然会重复某个状态。上下文无关文法拥有另一种有限记忆:在语法分析树的足够长的分支上,非终结符可以重复出现。非终结符的重复产生两段相互嵌套的推导,它们可以被同时插入。上下文无关泵引理正是把这一观察精确化。
该引理是语言为上下文无关的必要条件,因此它的逆否命题可以用来证明某个语言不是上下文无关的。它不是定义,也不是充分的判别法。在证明非上下文无关性时,我们必须击败引理所允许的每一种分解,尽管我们可以自行选择单词与泵取指数。
定义
定义 2.7.1
(分解与泵取)
设 是有限字母表上的语言。单词 的一个分解,是由五个连续字符串 构成的列表,满足 。除非所述条件排除,否则这些字符串可以为空。泵取是指把 与 同时替换为相同数目的副本,而中间的 保持不动。例如,指数为零的泵取同时删去 与 ,而指数为一则还原原单词。
定义 2.7.2
(带受保护起始规则的乔姆斯基范式)
我们使用乔姆斯基(Chomsky)范式的上下文无关文法,其规则为 或 ,并可能带有一条受保护的起始规则 。对于一个所生成的非空单词,其语法分析树具有二叉的变元节点与终结符叶子。范式转换是前面已有的标准结果;下面的论证也说明了为什么空单词这一例外不会造成问题。
定理
定理 2.7.3
(上下文无关泵引理)
若 是上下文无关语言,则存在整数 ,使得每个满足 的 都有一个分解 ,满足 、,并且对每个整数 都有 。
定理 2.7.4
(一个非上下文无关语言)
语言 不是上下文无关的。
证明
证明:语法分析树路径上的重复变元
证明
(由最长路径上重复的变元得到泵取)
取 的一个范式文法,设其有 个变元,并令 。一棵二叉树若其每条路径至多含有 个二叉变元节点,则它至多有 个叶子。因此,长度至少为 的单词的语法分析树中,有一条从根到终结符的路径含有多于 个变元出现。选取一条最长的这样的路径。在它最低的 个变元出现中,有两个带有相同的变元标号;把较高的出现记为 ,较低的出现也记为 。
把较高子树的终结符产出写成 ,其中 是较低子树的终结符产出。该子树之前的周围部分产出 ,之后的部分产出 。于是文法有如下形式的推导:
所显示的字符串 是相关兄弟子树的终结符产出,不一定是单个文法步骤所产生的符号。把较低的 子树替换为较高 子树的一个副本,就重复了外层推导;把较高子树直接替换为较低子树,则将其删去。因此对每个 , 都被生成。
上方的出现位于最长路径上最低的 个变元出现之内。它下面的所有路径都不长于该最长路径的相应后缀,所以它的子树至多有 个终结符叶子。故 。由于这两个出现是不同的,从上方 到下方 的路径含有一条二叉规则。其兄弟子树至少产生一个终结符:在这棵非空单词的分析树上,受保护的起始符之下没有变元使用空规则。因此 。这也说明了为什么 变化时,泵取确实会改变单词的长度。可能存在的规则 只处理空单词,而空单词短于 ,且不在这棵树中使用。
证明透视
为什么最长路径很重要
树的深处某处出现的重复变元会给出可泵取的分解,但其本身并不能限制整个子树的大小。选取最长的根到叶路径底部附近的重复出现,可以控制上方出现之下的每一个分支,并得到 。
证明三个相等的块不是上下文无关的
证明
(三个相等的块击败每一个分解)
假设 是上下文无关的,用反证法,并设 为其泵取长度。选取 。它属于 ,且长度至少为 。引理保证存在某个满足其条件的分解。我们并不选择该分解,而是考虑任意一个满足条件的分解。
连续子串 的长度至多为 。它不可能同时含有 与 ,因为这样的子串必然也包含中间全部 个 ,长度至少为 。因此 与 合起来至多含有三种块类型中的两种的符号,至少有一种类型未被触及。由于 ,取 时,另外两种类型中至少有一个的计数减少。
删去 与 会保持其余字母的次序。未被触及的类型仍出现 次,而被触及的某个类型出现次数少于 。三个计数不再相等,所以 。这与引理对所保证的分解的结论相矛盾。由于该论证涵盖每一个允许的分解,这一矛盾是有效的。
例题详解
例题 2.7.5
(上下文无关语言的一个允许分解)
文法 生成 。对于 ,取 、、、。泵取得到 ,它仍在该语言中。这说明了两个同步的片段;它并不证明该语言中每个单词都满足泵引理。
例题 2.7.6
(较短的中间部分可能跨越边界)
对于 ,所设想的子串 可能完全位于一个块内,也可能跨越 边界或 边界。在长度至多为四的条件下,它不可能从一个 延伸到一个 。计数论证并不枚举 与 的确切位置,而是观察到整整一种符号类型未被触及,而删除会改变至少另一个计数。
例题 2.7.7
(同时泵取很重要)
对于 ,取 、、、。取 时结果为 。若只泵取 ,则得到 ,但引理并不断言这种单边操作仍留在语言中。两个片段使用的是同一个指数。
常见错误
选择的顺序
泵引理陈述的是一连串的选择与义务。首先,上下文无关语言提供一个对所有足够长的单词都适用的 。然后,任何符合条件的单词都必须至少有一个良好的分解。最后,对该分解,每个非负指数都必须成立。
在反证法的证明中,可以设想一个对手宣布 。你依据 选择一个单词。对手可以选取任何满足长度与非空条件的分解。然后你必须给出一个指数(可以依赖于该分解),使得泵取后的单词离开该语言。上面选用的 是统一适用的,但并非每个证明都有这样方便的统一指数。
仅有一个坏的分解什么也证明不了:上下文无关语言也可能有许多无法泵取的分解。仅检查块与块之间明显的分割也是不够的。论证必须考虑位于某个块内部的片段、跨越边界的片段,以及 之一为空的情形。
反例模式
一个坏的分解并不构成矛盾
断言:要否证上下文无关性,只需找出某个长单词的一个不能泵取的分解。在上下文无关的语言 中,取 和分解 、、、、,此时 ,。向下泵取得到 ,它不在该语言中,所以这个分解失败。然而该语言是上下文无关的,而且前面的例题给出了一个对每个指数都能泵取的分解(、)。引理要求的是存在一个好的分解,所以否证必须击败每一个允许的分解。
常见错误
(单词必须依赖于泵长度)
在反证法中,泵长度 由假设存在的文法给出,而且是未知的。固定的单词(例如 )不可行:若 ,引理对长度为 的单词什么也没有说。应当用 来选取单词,例如 。
常见错误
(把引理读反了)
引理的形式是:上下文无关蕴涵可泵取。证明所用的是它的逆否命题:不可泵取蕴涵不是上下文无关。其逆命题,即可泵取蕴涵上下文无关,并没有被断言,所以找到某个能泵取的分解绝不能证明一个语言是上下文无关的。
该引理能说明什么与不能说明什么
对于 ,障碍在于两个短的可泵取片段无法改变全部三个分隔开的块,而等式要求它们的计数一同变化。固定的中间块迫使短子串至少错过一种符号类型。该论证同时用到了 的局部界与 的非空性。
该引理并不意味着每个非上下文无关语言都能用这一特定方法证否。即使某个语言满足泵性质,仅凭这一事实也不能给出上下文无关文法。可能需要封闭性质、更强的泵引理陈述或其他方法。反过来,在排除所有允许的分解之前,未能找到良好分解并不构成证明。
把该引理应用于新的语言时,首先要检查,对每个宣布的 ,所选取的单词都属于该语言。然后确定短的连续区间无法覆盖什么。最后计算一个具体的泵取结果,并准确说明哪一条成员资格要求不成立。若泵取既改变了计数又改变了次序,则任何一种失败都已足够,但应当明确陈述,而不是想当然。
第二种障碍:交叉的等式
考虑 。这里有两个等式,而不是要求四个计数全部一致。我们仍然可以利用两个被泵取片段的局部跨度。假设 是上下文无关的,取其泵取长度 ,并选取 。长度至多为 的子串不可能同时含有 与 :整整一个含 个符号的中间块位于二者之间。类似地,它也不可能同时含有 与 。
对任何允许的分解,四种类型中至少有一种出现在 中。若被改变的类型是 或 ,则等式 中与之配对的另一方不在整个跨度 中。若是 或 ,则等式 中与之配对的另一方不在其中。向下泵取会减少被改变类型的计数,而其配对方仍为 。因此无论删去了其他哪些符号,至少有一个所需的等式不成立。这证明了 不是上下文无关的。
等式的次序很重要。相比之下, 是上下文无关的:一个文法生成相等的 对,另一个生成相等的 对,再由新的起始符号把它们的输出连接起来。一个具体的文法是 ,,。给出文法并追踪其两个独立的选择,可以避免依赖对栈能记住什么、不能记住什么的直观图像。
该语言的证明不需要文法的实际变元个数,也不需要显式的 值。它对引理可能给出的每个正整数都成立。这很有用,因为在反证法中所假设的文法可能完全未知。若不参照 而选取一个固定的单词,一般来说是不够的:未知的泵取阈值可能比该单词更大。
总结
沿着语法分析树长路径出现的重复变元,提供了两个同步的可泵取片段。子树大小的界使它们合起来的跨度是局部的。在非上下文无关性的证明中,单词是在泵取长度之后选取的,但论证必须击败每一个被允许的分解。
练习
快速检查
(对于 与 ,给出一个 与 均非空、且在 内可泵取的分解,并计算其 与 的结果。)
解答 · 答案
取 、、、。向下泵取得到 ,泵取两次得到 。每个指数都产生 。
快速检查
(证明: 中同时含有 与 的子串,其长度至少为 。)
解答 · 答案
该子串始于最后一个 或其之前,止于第一个 或其之后。它含有这两个端点符号以及中间全部 个 ,共至少 个位置。
快速检查
(在 的证明中,设 为空,而 含有一个或多个 且没有其他符号。解释向下泵取之后出现的矛盾。)
解答 · 答案
向下泵取至少删去一个 ,而不删去任何 或 。所得的计数分别为 、少于 、,因此即使一个被泵取的片段为空,结果仍在 之外。
快速检查
(某学生选取 的单个分解,证明它在 时失败,并由此断言语言非上下文无关。指出缺失的量词,并修补该论证提纲。)
解答 · 答案
引理允许文法提供任何合适的分解,而不一定是该学生所选的那个。固定任意一个满足 与 的分解。其跨度至少错过三种符号类型之一;删去这对非空片段会改变另一个计数,而被错过的类型的计数仍为 。因此每个允许的分解在指数为零时都失败。