动机
前面的上下文无关一章已证明文法可由栈机器模拟,但泵引理显式假设范式定理,机器到文法的反向构造也留待后续。本章补上两项证明。前者简化规则而保持终结字,后者用进入状态、一个栈符号及退出状态,概括可能很长的计算。
文法变元不一定表示可见的语法成分,也可以表达计算承诺。下文的 表示从状态 开始,完成移除一个栈符号 的全部工作,并在状态 结束。内部可以任意嵌套,但接口只有三个有限标签。这解释了为何有限文法足够。
定义
定义 2.2.1
(可空变元、单位产生式与范式)
CFG 的变元若能推导空串,称为可空变元。 且两者均为变元的规则是单位产生式。非空串的 乔姆斯基(Chomsky)范式只允许 或 ,其中大写为变元、小写为终结符。若要保留空串,可额外允许新开始变元的规则 ,但 不得出现在任何右侧。
沿用前章 NPDA 约定:一次转移读 ,把栈顶符号替换为有限串并改变状态;接受要求输入及栈同时为空,栈顶写在左边。转移表有限,不代表运行长度有界。
定义 2.2.2
(受保护移除)
读取 的受保护移除从状态 、栈 出发,在状态 、栈 结束,并且直到最后一步才首次暴露下层后缀 。后缀的任何符号都未被检查或改变。由于转移只访问栈顶,同一串步骤对任意后缀都成立。等价地,可在只有 的栈上检验,取首次变空时结束的运算,并记录状态与读入字。
定理/命题
定理 2.2.3
(上下文无关范式)
每个 CFG 语言 都有范式文法生成 。若 ,以新开始变元的唯一例外空规则可保留整个语言。构造有限且有效,但不保证保持原来的分析树或歧义。
定理 2.2.4
(从空栈 NPDA 构造文法)
每个按空栈接受的有限 NPDA 都有有限 CFG 生成 。结合前章反向模拟,CFG 与空栈 NPDA 描述完全相同的语言类。
证明思路
证明
(以可空删除、单位消除与二叉化得到范式)
先加入从不出现在右侧的新开始变元及 。计算可空变元:先标记有空规则者,再反复标记具有右侧全为已标记变元的规则的左侧。变元有限,过程必稳定。按标记阶段归纳可证标记者确实可空;对空串的分析树归纳,则每个可空变元最终都被标记。
对每条规则,加入删除任意若干可空变元出现位置所得的所有非空右侧版本。删除原空规则;当原开始变元可空时,仅保留 。原分析树中剪去产生空串的子树,就得到新文法的非空串分析树。反向,在每个删去位置插回该变元的一个空串推导,就恢复原树。每条右侧只有有限个位置,所以新规则有限。这同时证明两个语言包含方向。
再计算沿单位产生式的自反传递可达关系 。对每对可达变元,把每个非单位产生式 复制为 ,然后删除所有单位产生式。原推导中的一串单位步骤及随后的非单位步骤可缩成复制规则;反向沿有限单位路径展开。由于 从不在右侧,其他变元不能经单位路径到达它,故例外空规则不会传播到其他变元。
对长度至少二的右侧中的终结符 ,用新变元 替代,并加入 。这只细分终结叶。最后把长度 的右侧 改为
每条规则各用自己的新链变元。展开恰得原右侧,收缩链又恢复原树。其余规则便是二变元或单终结符形式。去掉开始空规则得到非空语言;若无非空串,开始变元没有产生式就正确生成空语言。
证明
(三元变元描述受保护移除)
对 NPDA,为每个 引入变元 ,另设开始变元 ,对每个 加入 。考虑一次转移:在 读 ,把 替换为 ,进入 。若 ,加入 ,其中 表示空右侧。若 ,对全部中间状态 加入
时右侧就是 。状态、转移及每次推入长度都有限,所以得到有限文法,并没有给运行长度加上限制。
按分析树归纳, 的一次推导先选最初转移,再依次完成移除 的子推导。归纳假设给出各自受保护运算;在未改动的下层后缀之上依次执行,读取各子字,便完成受保护移除 。直接弹出规则是一步的基础情形。
反向对受保护移除的步数归纳。第一步若推入零个符号,就已首次暴露后缀,整段仅一步,直接弹出规则恰好生成读入字。若推入 个符号,在首次依次暴露 、 直到 的时刻分段。每步栈高至多下降一,且下层不能先于上层被访问,所以这些时刻都存在。每段比原运算短,是移除一个 的受保护运算,读取连续输入因子。由归纳得到相应三元变元推导,再选取记录实际中间状态的产生式,便生成全部输入字。
接受运算从 首次变空必在最后,因为本模型空栈后无转移,且接受要求输入读完。故它是从 到某个 的受保护移除。开始规则于是精确生成所有接受字,而非含糊地说“文法记住整个栈”。
证明透视
为什么运算会在首次暴露处分段
关键一步是反向的归纳,由三件事合起来支撑。转移只查看栈顶符号,所以在它上面的符号全部被移除之前,下层符号既不能被查看也不能被改变。栈高度每一步至多降低一,所以从 降到 的过程中,栈会依次首次到达各个后缀 。这些时刻把运算切成 个相连的片段,每个片段都是对某个 的受保护移除,且步数少于整个运算。最后,切分点上的状态恰好就是产生式所需的标记 ,所以构造要遍历中间状态的每一种选择:正确的产生式之所以存在,是因为它对所有选择都已加入。若转移能够查看栈顶以下的符号,切分点就不存在,三元组也就不能概括一个片段。
这里的构造证明可以有效得到有限描述,并未无条件承诺相对于原始表示大小的多项式界。含许多可空出现位置的规则,可能产生许多删除版本;较长的压栈串也可能要求枚举许多中间状态组合。这不影响语言等价性的证明,却影响把文法大小本身算作输入时的复杂度分析。后续算法必须计入变换后的描述大小,或另行证明一种控制大小的规范化。存在性、有效构造与高效构造是不同的结论,不能悄悄把表示定理加强成效率定理。
例题
例题 2.2.5
(归一化匹配文法)
的非空语言可由 、、、 生成。第一分支是 ,第二分支是 ,归纳得恰好 、。若要保留空串,加入开始变元 及 。 不在右侧, 则在;空规则的特殊地位属于 。
例题 2.2.6
(单位循环不产生新终结字)
取 、、。单位可达关系使三个变元都可达 ,因此每个都收到到 的规则。删除单位产生式后,语言仍只有 。在 之间无限旅行本来就不是另一个终结字的有限推导;语言只量化有限推导。
例题 2.2.7
(一个栈符号与一个三元变元)
单状态机器从 开始,读 时把 换成 ,读 时弹出 ,没有其他转移。唯一三元变元 给出 。字 对应 及栈高 。 不接受,因为第一个 已清空栈而输入未完,机器不能重启。变元表示完整的一次移除,不是清空后又重新开始的任意运算段。
概念视角结构
变元作为计算接口
忘记嵌套工作的细节,只保留外部计算需要的进入状态、被移除符号及下层首次可见时的退出状态。双向证明验证了接口。只用状态会丢失栈任务;每个完整栈串各设一个变元又会无限。三元组正是有限而够用的中间层。
常见错误
常见错误
(可空并不表示只能产生空串)
可空只表示能产生空串,不表示只能产生空串。删除可空出现位置是增加一个选择,不是把它在所有规则使用中永久删去。
常见错误
(二叉化的链变元必须逐规则新设)
二叉化时链变元应逐规则新设,否则不同规则可能混接,产生额外字。
常见错误
(受保护移除不能先检查下层再恢复)
NPDA 构造是非确定性的;文法猜中间状态没有证明确定性栈机器也足够。受保护移除不能先检查下层后再恢复它;首次暴露条件正是递归组合正确的保障。
反例模式
只指定一个终止状态并不足够
断言:对于空栈 NPDA,只需对某个选定的状态 加入一条开始规则 。取 ,起始状态 ,初始栈符号 ,且恰有两条转移:在 读入 时把 替换为 并进入 ;在 读入 时把 替换为 并留在 。单词 和 都被接受,因为各自在输入耗尽时清空了栈,而且没有其他单词被接受,所以 。构造给出 与 ,没有其他右部非空的规则。只用 时,文法只生成 ;只用 时,只生成 。空栈接受并不指定最后的状态,所以修正后的说法是对每个 都加入 。
总结
有限规则变换保持非空串并产生二叉分析树,补全泵引理所需前提。三元变元概括受保护栈移除,为每个空栈 NPDA 产生 CFG,与前章一起完成语言等价。
练习
快速检查
(对 、、,找可空变元并消除空及单位产生式。)
解答 · 答案
只有 可空, 不可空,故 也不可空。删除 的空规则并在 中加入删去 的版本 ,再去单位产生式,得 、、,语言为 ,与原来相同。
快速检查
(为什么把 改为 、 安全,而任意跨规则共用链变元未必安全?)
解答 · 答案
两分支共有起始 , 的两个选择恰好是原后缀,故安全。若把 、 改成 、、,就额外产生 、。逐规则使用新变元可阻止混接。
快速检查
(用每个前缀及全字的 个数刻画上述单状态机器的语言。)
解答 · 答案
前缀 后栈高为 。全字须有 比 多一;每个真前缀必须栈高正,即 ,否则过早变空或无符号可弹。反向,这些条件保证每步合法,并在输入结束时恰好清空,所以充要。
快速检查
(对于单状态 NPDA,转移为 与 ,写出由该构造给出的文法,并描述它的语言。)
解答 · 答案
只有一个三元变元 和开始规则 。读入 的转移压入一个符号,故 ;读入 的转移弹出,故 。语言是 ,这正是机器所接受的语言:读入 时保持 不变,在唯一的 上清空栈。