动机
正则约束可以检查有限状态信息,而下推自动机负责处理嵌套或匹配。让两台机器并行运行,就得到它们交集的上下文无关语言。这一有用的封闭性质不能与两个上下文无关语言的交运算封闭性混为一谈:两个相互独立的无界匹配要求,可能超出单个栈所能强制执行的范围。
下面的乘积构造在全部输入被消耗完之后按终态接受。静默的下推移动使有限自动机的状态保持不变。随后我们证明,上下文无关语言在交运算与补运算下不封闭,并给出具体反例。
定义
定义 2.8.1
(下推自动机与 DFA 的乘积)
设 是有限字母表 上按终态接受的非确定性下推自动机(PDA),设 为完全 DFA。乘积格局记录下推自动机的状态与栈,以及 DFA 的当前状态。若 读入 ,则乘积使 按 前进;若 执行 转移,则乘积保持 DFA 状态不变。当且仅当两个分量状态都是终态时,乘积状态才是终态。
定义 2.8.2
(上下文无关语言)
若一个语言被某个遵循此约定的非确定性 PDA 接受,则称其为上下文无关语言。此处使用它与上下文无关文法之间的标准等价性。补集是相对于固定的全集 而取的。
定理
定理 2.8.3
(与正则语言的交)
若 是上下文无关语言, 是同一有限字母表上的正则语言,则 是上下文无关语言。若 的 PDA 在通常的“无相互冲突的静默移动”定义下是确定性的,则乘积仍然是确定性的。
定理 2.8.4
(两个上下文无关语言的交可以不是上下文无关语言)
上下文无关语言
的交为 ,而它不是上下文无关语言。因此,上下文无关语言在交运算与补运算下均不封闭。
证明思路或证明
证明
(乘积自动机识别交集)
在乘积中,一次运行可投影为 的一次运行,以及 DFA 在迄今已消耗符号上的唯一运行。对乘积转移作归纳可证明:DFA 分量恰好是读完已消耗前缀后所到达的状态——输入移动使两个分量同时前进,静默移动只使 前进。到结束时,两台机器读过的是同一个完整的词。当且仅当 PDA 与 DFA 都接受该词时,乘积才接受它。乘积只有有限多个控制状态对,并沿用原来的栈字母表,因此它是一个 PDA。
若 是确定性的,则将其状态与 DFA 状态配对并不增加转移的选择。对每个输入符号,DFA 的转移是唯一的;而对同一个下推状态与栈顶符号,PDA 的 移动仍然排斥读入输入的移动。因此乘积保持确定性条件。这证明了对与正则语言的交运算封闭;它并没有证明任意两个确定性下推语言的交运算封闭。
证明
(两个配对约束不能共用一个栈)
文法 ,, 生成 。类似地,,, 生成 。同时属于两者的词具有有序形式 ,并满足 且 ,由此得到上面所示的交。
要证明该交不是上下文无关语言,假设上下文无关泵引理成立,泵长度为 ,并将其作用于 。在每一个满足 且 的允许分解 中,段 至多与三个连续符号块中的两个相交。向下泵(删去 与 )会从 或 中至少移除一个符号,同时至少一个完整符号块的个数保持不变。从 删去若干符号后仍是形如 的词,所以只需看计数,而三个计数不可能全部保持相等。这与泵引理矛盾。
证明透视
泵论证在何处用到它的假设
选取词 ,是为了使界 迫使被泵的段错过一整个符号块:单是 块的长度就是 。这是泵长度唯一发挥作用之处。选择向下泵,是因为删去符号不改变符号块的次序,只改变计数。假设 保证某个计数确实改变。不显然的一步是去数 碰不到的符号块,而不是追踪它碰到的符号。论证之所以封闭,是因为未被触及的符号块保持计数 ,而被触及的符号块降到 以下,所以不论引理给出哪种允许的分解,三个计数都不可能相等。
证明
(补运算封闭会推出交运算封闭)
上下文无关语言对并运算封闭:用一个新的开始符号来选择任一文法的开始符号即可。若它们在 上对补运算也封闭,则德摩根(De Morgan)恒等式 将推出对交运算封闭。上述反例排除了这一点,所以对补运算的封闭性同样不成立。
例题详解
例题 2.8.5
(匹配加上奇偶条件)
将 与含有偶数个 的词所构成的正则语言相交。DFA 记录奇偶性,PDA 检查匹配。乘积恰好接受 。
例题 2.8.6
(两种不同的匹配要求)
词 属于 ,因为 与 的个数相等;但它不属于 ,因为 与 的个数不同。词 同时属于两者。交运算同时强制两个等式成立。
例题 2.8.7
(一个被泵的见证)
取 与词 ,并假设被泵的部分完全落在 块内,且向下泵时至少移除了一个 。此时 与 的个数仍为三,而 的个数减少。所得的词不在 中。一般性的证明涵盖了所有允许的位置,包括跨越某一个边界的片段。
常见错误
反例模式
正则是一个真正的限制
一个诱人的论证是:PDA 可以与 DFA 并行运行,所以两个 PDA 也可以并行运行,因此两个上下文无关语言的交仍是上下文无关语言。 与 驳倒了这个说法。两者都是上下文无关语言(见上面明确给出的文法),并且 同时属于两者,但它们的交 却不是上下文无关语言。与 DFA 的乘积只额外存储有限个状态,而两个 PDA 需要两个无界的栈,一个比较 与 的个数,另一个比较 与 的个数,而第二个栈并不属于 PDA 模型。
常见错误
(不封闭不等于每个交都不是上下文无关语言)
不封闭的含义是:至少存在一对语言,其交落在该类之外;上下文无关语言的许多具体的交仍然是上下文无关的。同样,补运算的论证是相对于共同字母表进行的,并且用到了并运算的封闭性。它并不表明每一个上下文无关语言的补集都不是上下文无关的。
逐个转移地构造乘积
设 PDA 的控制状态集为 ,其转移关系包含形如 的移动,其中 为输入符号或 。乘积的控制状态是 中的对 。对读入输入的移动,加入
对静默移动,加入
开始状态由两个开始状态配对而成,初始栈保持不变。当且仅当 是 PDA 的终态且 是 DFA 的终态时,乘积状态才是终态。这些规则复制了 PDA 的每一个选择,并加上由所消耗符号唯一确定的 DFA 更新。
乘积的证明分两个方向。给定 PDA 在某个词上的一次运行,DFA 在该词上的唯一运行确定了每一步的第二个分量,从而得到一次乘积运行。反过来,把任何乘积运行投影到其 PDA 分量上,得到一次有效的 PDA 运行,并且通过归纳可知其 DFA 分量遵循正确的输入前缀。因此两个包含关系都不是预先假定的:交中的每个词都有一次接受的乘积运行,而每一次接受的乘积运行都见证了该词同时属于两个语言。
例题 2.8.8
(静默移动不改变奇偶性)
设 DFA 记录已消耗的 的个数是偶数还是奇数。若 PDA 在其 DFA 分量为奇时执行一次弹出栈符号的静默转移,则乘积仍保持为奇。只有读入 才会翻转奇偶性;读入 或执行静默移动都使其不变。若在静默移动上推进 DFA,就等于给一个从未被读入的符号赋予了奇偶性。
DFA 必须是完全的,上面所示的转移规则才对每个输入符号都有定义。部分 DFA 可以先用一个非接受的陷阱状态补全;在“缺失的转移即拒绝”的通常约定下,这样做保持其语言不变。如果两台机器是在不同的字母表上给出的,应先确定一个共同的字母表,并一致地解释缺失的符号。否则,连补集的全集或所要的交都可能不明确。
泵引理中的量词
上下文无关泵引理指出:若一个语言是上下文无关的,则存在泵长度 ,使得该语言中每个足够长的词都有某个允许的分解,使所有被泵出的词仍留在该语言中。要导出矛盾,须选取一个合适的长词,并证明每一个允许的分解都至少对某个泵指数失效。只挑选一个方便的分解并说明它失效,并不与引理的存在性结论相矛盾。
对 ,长度至多为 的片段不可能同时含有 与 :任何这样的片段都包含中间整个由 个 构成的块,以及两侧相邻块各至少一个符号。因此在删去 与 时,三个符号计数中至少有一个不受影响。由于 ,其余计数中至少有一个减少。未受影响的计数仍为 ,所以三个计数不可能全部相等。这一论证涵盖了被泵的部分落在一个块内或跨越单个边界的各种情形;它不需要对每个位置逐一列出单独的分解。
常见错误
(泵引理是必要条件,而不是刻画)
泵引理给出的是上下文无关性的必要条件,而不是完整的刻画。一个语言对某个特定分解、甚至对某个拟定的泵长度满足泵性质,并不自动意味着它是上下文无关的。在本证明中,矛盾来自对所选的词、引理所允许的全部分解所作的全称分析。
交与补
对固定的有限字母表,上下文无关语言类包含空语言与 ,且对有限并封闭。要把两个文法合并为并,先重命名变元使两者不相交,再引入一个全新的开始变元,让它选择任一旧的开始符号。变元重命名可防止一个文法的产生式意外地展开属于另一个文法的变元。这一构造接受的是并而不是交:最初的选择每次只沿着一个文法进行。
德摩根这一步是关于类性质的反证法。如果每个上下文无关语言的补集都是上下文无关的,那么公式中的两个补集都是上下文无关的。并运算封闭性使它们的并是上下文无关的,再次使用补运算封闭性就使交是上下文无关的。由于那个明确给出的交不是上下文无关的,所假定的普遍补运算封闭性不可能成立。该论证保证存在某个上下文无关语言,其补集不是上下文无关的,但它本身并不能确定两个中间补集中究竟哪一个提供了具体的见证。
例题 2.8.9
(正则过滤器可以保持较简单的交)
设 ,这是一个正则语言。 与 都已是 的子集,所以分别将其中任一个与 相交,都使它保持不变,仍然是上下文无关的。但这并不意味着它们彼此的交是上下文无关的。乘积定理一次只允许一个上下文无关语言与一个正则过滤器;除非已知第二个语言是正则的,否则无法对它应用该定理。
接受方式与确定性的适用范围
该构造保持了终态接受,因为它在整个输入读完之后检查两个终态控制状态。如果 PDA 原来是以空栈接受给出的,应先使用有效的转换化为所采用的约定,或者针对该约定重新陈述并证明乘积构造。对确定性机器而言,接受方式的转换须格外小心:额外加入的非确定性清理选择可能破坏确定性。这里关于确定性乘积的断言从一个确定性的终态接受机器出发,不依赖这样的转换。
DFA 分量不增加无界的存储:只有 个控制状态对,而乘积只有 PDA 栈的一份副本。这就是该构造保持在 PDA 模型之内的原因。第二个任意的栈将是另一种机器模型,所以“可以直接把两个 PDA 并行运行”这种直觉性的说法,并不构成上下文无关语言对交运算封闭的证明。
常见错误
(反例中的两个运算对象都是上下文无关语言)
不封闭的见证并没有断言 或 不是上下文无关语言;明确的文法表明情形恰好相反。产生非上下文无关语言的,是它们的交需要同时满足两个匹配约束。这一区分在设计归约时很有用:在利用运算对象的组合去反驳某个全称的封闭性质之前,应先证明这些运算对象确属所声称的类。
总结
DFA 可以与 PDA 结合:把它的有限状态存放在控制部分中,并且只在消耗符号时更新它。两个上下文无关的匹配语言的交可以是 ,这证明无限制的上下文无关语言交运算封闭与补运算封闭都不成立。
练习
快速检查
(在乘积构造中,PDA 执行静默移动时,DFA 的状态会怎样?)
比较静默移动消耗了什么,以及什么会让 DFA 前进。
解答 · 答案
它保持不变,因为没有消耗任何输入符号。
快速检查
( 是否属于 ?是否属于 ?)
对照 与 的定义,数一数 、、 的个数。
解答 · 答案
它不属于 :有两个 而有三个 。它也不属于 :三个 与零个 的个数不同。
快速检查
(为什么长度至多为 的片段不可能与 的三个块都相交?)
块与 块之间是哪一块?
解答 · 答案
要同时与 块和 块相交,必须跨越中间整个 块,并在两侧各至少包含一个符号,其长度大于 。
快速检查
(除补运算之外,德摩根论证中还用到了哪一个封闭性质?)
哪种运算能把两个文法合成一个?
解答 · 答案
并运算的封闭性,加上共同的补集全集,借助德摩根恒等式得出交运算的封闭性。