动机
下推自动机可以这样描述:当输入被读完并且到达某个终结状态时接受。另一种常见约定是:当输入被读完并且栈为空时接受。这两种定义看上去要求不同的东西:终结状态不必对应空栈,而空栈也未必能揭示控制状态。对于非确定性的机器,这两种约定识别的语言类是相同的。下面的转换说明了额外的非确定性选择究竟用在何处,以及为什么必须引入一个全新的栈底标记。
这个等价性讨论的是由可能不同的非确定性机器所识别的语言,而不是把两种接受判定应用于同一台机器。它也并不断言确定性下推自动机在这两种约定下具有相同的表达能力。我们首先固定一个精确的模型,使各个构造可以被逐一检验,而不必依赖非形式化的栈示意图。
定义
定义 2.1.1
(非确定性下推自动机及其转移)
一台非确定性下推自动机具有有限的状态集 、有限的输入字母表 、有限的栈字母表 、起始状态 以及初始栈符号 。一条转移 读入 ,弹出栈顶符号 ,压入字 (其最左端符号位于栈顶),并将状态由 改变为 。只要输入符号与栈顶符号相匹配,就可以选择该转移。一次计算是有限的;即使仍有可用的转移,计算也可以停止。
定义 2.1.2
(格局与两种接受约定)
格局 由当前状态、尚未读入的输入以及栈组成,栈内容自栈顶写起。标记为 的转移不消耗输入。在此模型下,栈为空时没有任何转移可用,因为每条转移都需要一个栈顶符号。若存在某个有限计算到达 且 为终结状态(无论 为何),则称机器按终结状态接受。若存在某个有限计算到达 (无论 为何),则称机器按空栈接受。两种情形下,整个输入都必须被读完。
定理
定理 2.1.3
(终结状态到空栈)
对于每台按终结状态接受的非确定性下推自动机 ,都存在一台按空栈接受的非确定性下推自动机 ,它们的输入语言相同。
定理 2.1.4
(空栈到终结状态)
对于每台按空栈接受的非确定性下推自动机 ,都存在一台按终结状态接受的非确定性下推自动机 ,它们的输入语言相同。
证明思路
证明
(由终态到空栈:先复制,再清理)
两种构造都先引入一个不属于 的栈符号 以及一个全新的起始状态。在 且栈顶为 时,新机器把它替换为 并进入 。新机器的初始栈只含 。在模拟过程中,每条原有转移都作用于 之上的原栈部分,既不能检查也不能移除该标记。因此,被模拟的栈恰好是原栈后面接上 。
对于从终结状态到空栈的构造,复制每条原有转移,并增加一个全新的清理状态 。对于每个原终结状态以及 中每个可能的栈顶符号,增加一条进入 的 转移,并移除该栈顶符号。在 中,对每个可能的栈顶符号增加一条移除它的 转移。清理阶段不消耗输入,并且可以把整个栈清空。若 接受某个字,则 模拟其接受计算,随后进行清理,因此 按空栈接受该字。
反过来, 移除 的唯一途径是清理,所以一个按空栈接受的计算必定是从某个原终结状态进入了清理。进入清理之前的部分都是原机器的计算。清理阶段不读入输入,而接受要求输入已读完;因此原计算在到达该终结状态时已经消耗了全部输入。在输入尚未读完时过早地猜测进入清理,不会造成错误的接受。这一论证同样允许原栈在终结状态时为空:此时新标记位于栈顶,清理将其移除。
证明
(由空栈到终态:检测标记)
对于从空栈到终结状态的构造,在 之上模拟 ,并增加一个全新的、唯一的接受状态 。从每个原状态出发,增加一条在栈顶为 时进入 的 转移,例如把 替换为其自身。若 在读完输入后清空了栈,则 看到标记并进入 。反过来,进入 意味着被模拟的原栈为空。由于到达 不消耗输入,而终结状态接受要求没有剩余输入,所以一次接受运行对应于 的一次有效的空栈接受运行。新机器可能过早地猜测进入 ,但这样的分支在仍有未读输入时无法接受。从 出发不需要任何转移。
证明透视
标记是一个不变量
在每个被模拟的格局中,新栈就是旧栈再附上全新的标记。因此,看到标记意味着旧栈为空;看到旧符号则意味着旧栈非空。标记是全新的,所以永远不会与原有符号混淆。
例题详解
例题 2.1.5
(终结状态下栈中仍有剩余)
设原机器读入 后到达终结状态 ,此时栈为 。在终结状态接受的约定下,它接受 ,尽管栈中还剩两个符号。所构造的空栈机器到达对应的栈 ,进入清理,依次弹出 、、。只有在输入已被读完且这三个符号都已消失之后,它才接受。
例题 2.1.6
(过早猜测清理会失败)
设对于输入 ,在读入第一个符号之后到达了同一个终结状态,此时 尚未读入。清理可以移除栈中所有符号,但它无法读入 。所得格局栈为空而输入未读完,因此不接受。原机器的另一个分支仍可能接受 ;仅凭这个失败的清理分支,无法对这种可能性作出任何判断。
例题 2.1.7
(检测最后一次弹出)
设某台原空栈机器在读入 之后到达 。模拟器则到达 。它通向全新终结状态的特殊转移证明了 被按终结状态接受。若标记出现时仍有剩余输入,同一条转移虽然可以执行,但所得分支无法通过输入读完的检验。
常见错误
反例模式
同一台机器可以给出不同的答案
断言:下推自动机按终态接受某个单词,当且仅当它按空栈接受该单词。取一台起始状态为终态、初始栈为 且没有任何转移的机器。空单词被按终态接受,因为 的未读入输入为空且状态是终态。它却被按空栈拒绝,因为栈 非空,而且没有任何转移能把它移除。定理构造的是另一台机器,并没有把这台机器上的两种接受检验等同起来。
常见错误
(把原有的栈符号当作标记)
取一个状态 、初始栈符号 ,以及唯一的转移 。栈永远不会变空,所以空栈语言为空。假设某个转换把“栈顶符号是 ”当作“原栈为空”,并在这项检验成立时进入终态 。那么新机器立刻接受 ,并且在压入一次之后也接受 ,但这两个单词都不在该语言中。标记必须是全新的,即任何原有转移都不会提及的符号,这样它就永远不可能在原栈底之上再次出现。此外,带着未读入的输入而到达终态或清空栈,并不满足本节所定义的任何一种约定。
常见错误
(清理阶段不得读入输入)
取一台起始状态为终态、初始栈为 且没有任何转移的机器,其按终态接受的语言为 。若允许清理状态在弹出的同时读入字母,则构造出的机器可以从终态的起始状态以 移动弹出 ,再一边读入 一边弹出 ,在输入耗尽时栈为空。它会接受 ,而 并不在该语言中。清理转移不读入输入,也不能回到模拟阶段;正是这一点防止了这种情形。
解读模拟不变量
模拟证明比较的是两个格局,而不仅仅是两张转移图。这里的关系是:旧机器处于状态 、未读输入为 、栈为 ,当且仅当模拟器可以处于同一个原状态 、同一个未读输入 、栈为 ,并且遵循相同的转移选择。初始化对 、完整输入和 建立了该关系。每条原有转移都保持该关系,因为它只移除并替换栈顶的原符号。保持不变的后缀包含标记。对原有转移的次数进行归纳,即可证明该关系对每个有限的模拟运行都成立。
反方向则需要排除新增的转移。在第一个构造中,进入清理之前,模拟器只用到被复制的转移,因此从该前缀中擦去标记便得到一个有效的原计算。进入清理之后,它无法回到任何原状态。在第二个构造中,进入全新终结状态之前,模拟器只用到被复制的转移,而对标记的检测证明了对应的旧栈为空。把两个方向都陈述清楚,就排除了意外引入旧机器所没有的接受运行的可能。
即使旧机器有无穷多个可用的移动,或者其有限转移图中含有环,这一论证仍然成立。接受是按存在一个有限接受计算来定义的。证明复制的是这一有限序列,再加上有限多个准备或清理步骤。它既不声称每个非确定性分支都会终止,也不声称可以通过等待所有分支来判定不接受。语言等价是关于存在接受分支的陈述。
例题 2.1.8
(一次压入后接两次弹出)
设 在输入 时把 替换为 ,然后一条在输入 时弹出 的转移,接着一条弹出 的 转移。沿这次特定运行,旧栈依次为 、、、空。模拟器的栈依次为 、、、。只有在最后一次原有弹出之后,才可能进行对标记的最终检测。若这些转移在读入 之后导致空栈接受,则新的终结状态构造同样接受 。
为什么非确定性选择很重要
在第一个构造中,原终结状态可能带有继续模拟的转移。新机器既要有继续模拟的选项,也要有进入清理的选项。即使还有可用的转移,一次原接受计算也可以在终结状态处停止;模拟器猜测此刻就是恰当的时机。其他的猜测可能失败,但非确定性接受只要求有一个分支成功。这是一个存在性的断言,而不是保证每个分支都能选对时机。
第二个构造同样是在其余位置保留被复制转移的同时,增加一条针对标记的转移。标记具有特殊含义,因为原转移关系无法提及它。这条额外转移是否可用,取决于模型的栈约定,这正是我们明确规定转移必须要有栈顶符号的原因。在允许转移不检查栈的表述中,这一构造需要相应的调整;证明不能简单地假定看到标记就会阻止所有原有转移。
有些表述允许转移压入一个字,并令其最右端符号位于栈顶。在这种约定下,所给出的初始化字必须反转,使原初始符号位于标记之上。这只是记号上的改变,而不是新的数学定理。重要的是关于栈中相对顺序的不变量,而不是某本教科书所选择的书写顺序。
检验一个转换
要验证一个给定的构造,首先检查新的起始状态是否只有预期的准备转移,且标记是否不同于任何原有栈符号。接着验证每条被复制的转移都不触及标记。然后准确找出哪些新状态与新转移可以导致接受,并分别证明两个方向:把任何旧的接受运行加以扩展,并把任何新的接受运行追溯回旧的接受运行。最后检查输入是否读完。这些步骤可以暴露常见的错误,例如允许清理读入输入、允许清理返回到模拟阶段,或者用旧的栈符号充当标记。
对于同一个字,转移系统可以有多条接受运行。这些转换保持的是成员关系,而不是运行的条数、运行的长度或栈的形态。特别地,旧的终结状态接受运行可能在多个时刻访问终结状态,新机器可以在每一个时刻尝试清理。即使原机器是无歧义的或确定性的,也不能断言所构造的机器具有这些性质。
总结
全新的栈底标记使模拟器能够识别原栈何时变空。非确定性地切换到清理,把终结状态转化为空栈接受;对标记的检测则把空栈转化为终结状态。两个方向的等价性都依赖于读完整个输入。
练习
快速检查
(一台机器从终结状态出发,栈为 ,且没有任何转移。它在两种约定下各接受什么?)
解答 · 答案
按终结状态,它恰好接受 。按空栈,它什么也不接受:其初始栈非空,且没有任何转移可以弹出它。
快速检查
(为什么在第一个构造中,带着未读输入进入的清理分支不能接受?)
解答 · 答案
清理只有 转移。它无法消耗剩余的输入,而空栈接受要求输入已被读完。
快速检查
(在第二个构造中,模拟期间 位于栈顶意味着什么?)
解答 · 答案
被模拟的原栈为空。原栈的每个符号都应位于全新标记之上,而模拟保持这一不变量。
快速检查
(若原机器按终结状态接受,且栈已经为空,说明第一个构造为何仍然接受。)
解答 · 答案
模拟计算结束后,新栈只含 。进入清理的转移弹出该标记,在整个输入被读完之后留下空栈。