动机
对于上下文无关文法,可以通过标记可产生(productive)变元来检验其语言是否为空。人们自然会问:它是否生成其终结符字母表上的全部单词?或者两个这样的文法是否生成相同的语言?这些问题的答案截然不同。我们将把 Post 对应问题归约到文法普遍性问题,并明确说明归约的方向。
该构造使用一个分隔符和一个反向排列的骨牌编号列表。下推机可以把一个单词与这些编号所指定的连接结果自右向左进行比较。更微妙的是,它还可以接受每一个格式错误或不匹配的字符串。这两种不匹配语言的并集恰好在不存在对应匹配时是普遍的。
定义
定义 5.5.1
(Post 对应问题实例与解)
一个 Post 对应问题实例含有有限多块骨牌 ,,其上、下单词都是有限字母表 上的非空单词。一个解是一个非空序列 ,使得 。配套的不可判定性一章证明了:在这种单词非空的约定下,判定解是否存在仍然是不可能的。
定义 5.5.2
(编码的匹配语言)
设 为一个与 不相交的编号符号字母表,设 为一个全新的分隔符,并令 。定义
编号符号是终结符,即使它们显示的名字看起来像整数。各字母表互不相交,因此当一个字符串具有预期的语法时,其分隔符位置和编号后缀是唯一确定的。
定理
定理 5.5.3
(普遍性的不可判定性)
不存在这样的算法:给定一个上下文无关文法及其所述的有限终结符字母表,判定其语言是否为该字母表上全部单词的集合。
定理 5.5.4
(可有效构造的不匹配语言)
由这些骨牌可以有效地构造出 与 的上下文无关文法。因此可以构造出 的文法。
我们使用配套的“下推机到文法”的有效构造,以及上下文无关语言对并运算的封闭性。我们把不匹配下推机描述得足够明确,以便证明它的行为;不假定上下文无关语言对补运算封闭。
证明
检测不匹配的栈机
下面证明“可有效构造的不匹配语言”这一定理。
证明
(不匹配语言的确定性栈机)
对于上方单词 ,构造一个带有永久栈底标记的确定性下推机。在读到分隔符之前,它把 中的每个符号压入栈中。输入在此前缀模式下结束时为接受:不含分隔符的字符串不属于 。在该模式下遇到编号符号或任何其他语法违规,则进入一个接受陷阱状态,并消耗余下的全部输入。
读到第一个 时,转入一个就绪状态;若此时输入结束,该状态也是接受的:因为尚未出现任何编号,而 要求至少有一个编号。读到编号 时,开始一串有限的 转移,把 逆序地与栈顶比较。有限控制部件记录当前在固定单词 中的位置。对每个期望的符号,弹出一个匹配的栈符号;若发生不匹配,或过早到达栈底标记,则进入接受陷阱状态。每个骨牌单词都是有限的,因此这个比较阶段总会结束。
比较成功后,一次对栈的 检查会选择两个就绪状态之一。若栈底标记已暴露,则刚读入的编号后缀恰好描述了到目前为止压入的单词;若此时输入结束,这个就绪状态是拒绝的。再读入任何编号都会进入接受陷阱状态,因为每个骨牌单词都非空,而栈中已无剩余符号。若栈底标记未暴露,则该就绪状态在输入结束时是接受的,因为仍有未匹配的前缀。它可以读入另一个编号并开始下一个有限的比较阶段。编号后缀中出现分隔符或 的符号则属格式错误,进入接受陷阱状态。
所有临时的比较状态与栈检查状态都是非接受状态。这在刚消耗完最后一个输入符号时十分重要:是否接受由有界的 阶段稳定之后决定,而不是由某个中间状态决定。每个就绪状态只有消耗输入的转移,每个临时状态只有针对当前栈符号的指定 转移,因此不存在非确定性选择或冲突的转移。如通常那样,接受意味着在全部输入被消耗之后到达一个接受状态。
如果输入具有预期语法且等于 的某个元素,则每次比较都匹配,并且栈恰好在最后一个编号之后变空,使机器处于拒绝的就绪状态。如果某个字母不同、栈过短、输入结束时栈过长,或者在栈恰好耗尽之后又来了更多编号符号,机器就接受。缺少分隔符、缺少编号以及格式错误的符号同样被接受。因此它恰好接受 。
对 采用同样的构造,则接受 。这是一个可有效构造的有限下推机:其比较状态由有限的骨牌单词所决定。配套的构造把它转换为上下文无关文法。再添加一个全新的并集起始符号来合并这两个文法,得到文法 ,其语言为
证明透视
从右侧比较连接结果
分隔符之后的第一个编号是 ,所以机器逆序弹出 ;然后逆序弹出 ,依此类推。在非空编号后缀之后栈恰好被耗尽,等价于原来自左向右的前缀就是 。此处默默用到的唯一假设是每个骨牌单词都非空:一旦栈只剩底部标记,再读入任何编号都必须弹出一个不存在的符号,所以只能进入接受陷阱状态,不可能出现第二个拒绝的格局。
从对应问题的归约
普遍性的不可判定性由下面的归约得出。
证明
(从 Post 对应问题的归约)
如果 Post 实例有解 ,则其公共单词后接 同时属于 和 。它不在 中,所以 不是普遍的。反过来, 中的字符串在两侧具有相同的显式反向编号后缀。把该后缀反转即确定了同一个非空编号序列,而两个前缀相等就是一个 Post 解。因此
该构造是有效且有限的。若存在普遍性判定器,则把它应用于 ,并把它的是/否答案取反,就能判定该 Post 实例是否有解。这与所述的不可判定性前提相矛盾。对判定问题的归约而言,答案取反是无害的,但必须明确说明:存在匹配使文法非普遍。
包含与等价的推论
推论 5.5.5
(包含与等价的不可判定性)
不存在这样的算法:给定同一终结符字母表上的两个上下文无关文法,判定第一个的语言是否包含于第二个的语言;也不存在判定两个语言是否相等的算法。即使要求其中一个文法生成该字母表上的全部词,这两个问题仍然不可判定。
证明
(把普遍性归约到包含与等价)
的文法可以有效构造,例如用一条起始规则,它要么停止,要么产生一个终结符再接起始符号。如果一个上下文无关文法的语言是否包含于另一个上下文无关文法的语言是可判定的,那么检验 就能判定普遍性。同样,若两个上下文无关文法的等价性可判定,就能判定 是否成立。因此一般的上下文无关文法包含问题与等价问题都是不可判定的。
第一个论证在包含关系的左侧使用的是一个正则语言。它并不蕴含相反方向的包含问题(左侧为任意上下文无关语言、右侧为正则语言)也不可判定。后一问题可以借助正则语言的补运算、上下文无关语言与正则语言的交运算,以及上下文无关语言的空性判定来处理。
例题详解
例题 5.5.6
(一块相匹配的单骨牌)
取一块骨牌 。单词 同时属于 和 ,因此被排除在所构造的不匹配语言之并集之外。该文法不是普遍的,这与单骨牌解的存在性相符。
例题 5.5.7
(仅在一侧不匹配)
对于单骨牌 ,字符串 属于 但不属于 。下方的不匹配机接受它,所以并集文法包含它。这个字符串不能见证非普遍性。
例题 5.5.8
(反向的编号顺序)
设上方单词为 与 。编号序列 给出 。压入 之后,机器读到 并弹出 ,再读到 并依次弹出 和 。栈恰好在末尾变空。
例题 5.5.9
(不完整的前缀)
只有一块上方骨牌 时,字符串 在唯一的编号之后仍在栈中留下一个 。它不属于 ,非栈底的就绪状态在输入结束时接受这个不匹配。相比之下, 以栈底标记结束,被该不匹配机拒绝。
常见错误
反例模式
取补运算不保持上下文无关性
也许有人会想:上下文无关语言的补集仍是上下文无关语言,因此直接对 的文法取补即可。这在一般情形下是错的。在 上取上下文无关语言 与 。词 同时属于两者,当且仅当 且 ,所以 ;由上下文无关语言的泵引理可知它不是上下文无关语言。若取补运算保持上下文无关性,而并运算也保持,则 (补集在 中取)就会是上下文无关语言,这是矛盾。因此,这里的证明是为这两个特定的编码语言构造专门的不匹配机,并且只在确认两个不匹配语言都是上下文无关之后才使用并集。
常见错误
(按原来的顺序读取编号后缀)
编号后缀必须反转。栈先暴露最后压入的符号,所以分隔符之后的第一次比较必须是与最后一块骨牌的单词作逆序比较。若按原来的顺序读取编号,一般会把错误的骨牌与前缀的末端比较。
常见错误
(让临时状态决定是否接受)
按所述约定,在仍有输入未读时到达某个状态,本身并不构成接受。这就是为什么带有未匹配栈符号的接受就绪状态之后还可以读入另一个编号,并可能转入拒绝的精确匹配状态。反过来,临时的 比较状态也决不能在比较完成之前误接受一个有效的字符串。
两个包含方向的比较
不可判定的方向是:一个正则语言是否包含于某个上下文无关语言之中。普遍性问题问的是 中的每个单词是否都属于该文法的语言。相反的方向结构不同。若 是正则语言而 是上下文无关语言,则 恰好当 为空。有限自动机经确定化之后可以取补;它与下推机的乘积仍是下推机。由此得到的上下文无关语言空性问题,可由配套的可产生性构造判定。
这一比较说明了为什么归约应当明确指出输入的顺序。只写“包含问题不可判定”会掩盖一个有用的不对称性,并可能使读者推断每个受限的包含问题都是困难的。上面的证明对一般的文法包含问题建立了不可判定性,即使左侧是实例字母表上固定的正则语言 也是如此。
有限控制的实现不需要把骨牌单词存放在栈上。每块骨牌都属于用来构造机器的固定输入实例,所以它的符号与当前位置可以编码在有限多个状态之中。栈中存放的是任意长度的单词前缀。正是这种分工使构造是有效的,同时又允许输入单词具有无界的长度。一块骨牌可以含有多个字母,但它的比较阶段有固定的有限最大长度。因此在消耗完最后一个编号之后,它不可能永远停留在仅含 转移的阶段;它要么检测到不匹配,要么到达两个就绪状态之一。
总结
一个编码后的 Post 解恰好就是 中的一个单词。专门的栈机通过把反向编号后缀与已压入的前缀比较,来识别这两个语言的补集。它们的并集恰好在不存在匹配时是普遍的。因此,普遍性判定器就能判定 Post 对应问题,而一般的包含问题与等价问题也继承了这种不可能性。
练习
快速检查
(对于上方骨牌 ,,编号序列 对应的编码字符串是什么?)
先按编号的顺序连接上方词,再把编号按相反顺序写出。
解答 · 答案
连接后的上方词是 ,反向的编号后缀是 ,得到 。
快速检查
(为什么要求 是一个全新的、既不在单词字母表也不在编号字母表中的符号?)
想一想在编码字符串中,单词部分在哪里结束、编号的部分从哪里开始。
解答 · 答案
它标出单词前缀与编号后缀之间唯一的边界。各字母表互不相交,使得归约两个方向所用的解码都没有歧义。
快速检查
(如果 Post 实例有解,所构造的并集文法是普遍的还是非普遍的?请解释。)
看看公共单词后接其反向编号序列,相对于 、 及该文法的语言处于什么位置。
解答 · 答案
非普遍。公共单词后接其反向的非空编号序列,同时属于两个编码语言,因此位于它们补集之并集的外部。
快速检查
(文法等价性判定器如何能判定 上的普遍性?)
应该把输入文法与哪一个固定的文法比较?
解答 · 答案
构造 的文法,并检验它是否与输入文法等价。相等恰好发生在普遍的情形。