动机
下推自动机可以利用栈记住无界的信息。非确定性还允许它猜测应使用哪一条转移,或在何处停机。确定性下推自动机取消了这种选择,但其定义必须同时处理静默转移与读入输入的转移:若在同一格局下两者都可用,机器仍然面临选择。
对非确定性机器等价的各种接受约定,在这里需要更加谨慎。在下面这种没有结束标记的模型中,空栈接受会带来前缀限制,而终态接受则不会。这一观察是关于一个精确陈述的模型的定理;加入可见的结束标记会改变机器所能观察到的内容,因而也会改变论证。
定义
格局是 ,其中 是状态, 是尚未读入的输入, 是栈内容,书写时栈顶在左。转移 读入 ,将栈顶符号 替换为 ,并把状态改为 。每条转移都要求存在栈顶符号;空栈不启用任何转移。初始栈只含一个符号 。
确定性下推自动机(DPDA)对每个三元组 至多有一条转移;并且只要对 存在 转移,则对同一个 就不存在对任何符号读入输入的转移。转移可以缺失。有限的运行可以停在任何格局。终态接受要求未读入的输入为空且当前状态为终态;空栈接受要求未读入的输入为空且栈为空。输入末尾不会自动附加任何特殊的结束标记。
若语言 中不存在两个不同的词 满足 (其中 为非空串),则称 是无前缀的(prefix-free)。特别地,含有 的无前缀语言不能再含有任何其他词。
定理
定理 2.9.1
(空栈接受的前缀限制)
在上述模型中,每个被 DPDA 以空栈方式接受的语言都是无前缀的。
定理 2.9.2
(一个确定性的匹配语言)
语言 在此模型中可被某个 DPDA 以终态方式接受。语言 可被某个 DPDA 以终态方式接受,但在此模型中不能被任何 DPDA 以空栈方式接受。
证明思路或证明
证明
(前缀限制、匹配机器与双词机器)
假设某个 DPDA 以空栈方式接受 ,并设 是另一个输入,其中 非空。比较对 的接受性有限运行与对 的运行。当该运行读入 的各个符号时,两次运行的下一个输入符号是相同的。若它走一条 转移,确定性规则禁止在该状态与栈顶符号下存在与之竞争的读入输入的转移。因此较长的输入会沿着 的接受性运行经过完全相同的转移,当栈变空时 仍未被读入。空栈下没有任何转移可用,所以较长的输入无法被消耗完,也就不会被接受。这就证明了前缀限制。
对于 ,使用状态 和栈符号 。终态为 。仅有的转移是
转移是 上唯一的转移,所以该机器满足所陈述的确定性条件。起始状态接受空串。对于 ,每个 压入一个 ,其后每个 弹出一个。恰好在读入了相匹配数目的 之后,标记 露出,静默转移到达 。 太少则停在非终态, 太多则在 留下未读入的输入,而在 阶段之后再出现 则没有转移可用。因此所接受的语言恰好就是所述语言。
的 DPDA 如下:起始状态为终态,第二个状态也是终态,初始栈为 ,唯一的转移是从第一个状态读入 到第二个状态,同时保持 不变。它恰好接受这两个词。该语言不是无前缀的,所以由第一个定理可知,此模型中的任何 DPDA 都不可能以空栈方式接受它。
证明透视
为什么确定性把两次运行耦合在一起
证明恰好各用一次下列四项事实。确定性使每个输入上的运行唯一,所以 上的运行逐步被决定。静默移动的无冲突规则意味着:在 的接受运行的每个格局上,较长的输入都只有同一个可用的移动,无论它是静默的,还是读入 的某个字母。接受运行是有限的,所以比较在有限步之后停止,停在 已全部读入的格局。最后一项事实是空栈接受所特有的:栈为空时没有任何转移被启用,所以尚未读入的 永远无法被消耗。去掉第二项事实,较长的运行就可能分叉;去掉第四项(改用终态接受),机器就可以继续读入,这正是下面的反例得以成立的原因。
例题详解
例题 2.9.3
(一次成功的栈追踪)
对于输入 ,匹配机器依次经过
最后一个格局的输入为空且处于终态。它的栈并不为空,而在所选定的接受约定下这是允许的。
例题 2.9.4
(右括号符号过多)
对于 ,机器压入一次、弹出一次。露出的 迫使静默转移到 ,此时仍有一个 未读入。由于 没有任何转移,该词被拒绝。当仍有输入剩余时,仅仅到达终态并不构成接受。
例题 2.9.5
(在这里,无前缀只是必要条件)
语言 不满足空栈准则,因为 是 的真前缀。仅凭该准则并不能为每个无前缀语言给出空栈 DPDA:无前缀语言的数量远多于可以有限描述的机器。该定理是必要条件,而不是针对任意语言的构造。
常见错误
反例模式
前缀限制对终态接受不成立
断言:每个被 DPDA 以终态接受的语言都是无前缀的。取状态 ,两者皆为终态,起始状态为 ,初始栈为 ,只有一条转移 。这台机器是确定性的。在空输入上它已处于终态且未读入的输入为空,所以 被接受。在 上它走 ,这是终态且没有未读入的输入,所以 被接受。因此被接受的语言是 ,其中 是 的真前缀。前缀定理的证明恰好在最后一步失效:终态不会禁止后续的移动,而空栈会。正确的说法是针对空栈接受的那一条。
常见错误
(只检查每组(状态、字母、栈顶符号)至多一条转移)
若某个状态与栈顶符号既允许 转移又允许 转移,则在以 开头的输入上两种移动都可用。例如 与 各占一个不同的三元组,但格局 既可以走到 ,也可以走到 。即使每个单独的转移条目只含一个目标,该机器仍然是非确定性的。
常见错误
(在附加结束标记之后仍套用前缀定理)
设每个输入后面附加一个标记 ,并以空栈接受。取状态 ,初始栈 ,转移 、、。没有任何状态有 转移,而且 的两条转移读入不同的字母,所以机器是确定性的。它接受 (读入 后栈被清空)和 (在 读入 后栈被清空),所以去掉标记后所接受的词集 不是无前缀的。该定理针对的是本单元的无标记模型,不能原样搬到有标记的模型。
前缀论证依赖于没有结束标记。若在输入之后附加一个不同的标记,机器就能分辨 的结尾与 的下一个符号之间的差别;该证明不能原样套用。非确定性的接受方式转换构造可能在清理与继续模拟之间引入一个选择,因此它不会自动保持确定性。
确定性作为对格局的条件
定义中的第一个条件排除了对同一状态、栈顶符号与输入标签出现两个不同目标的情形。第二个条件排除了静默移动与输入移动之间较为隐蔽的冲突。若两条输入转移的标签不同,则至多一条与下一个输入符号匹配,因此它们不冲突。若输入为空,则没有读入输入的移动可用,但静默移动仍可能可用。该规则是针对每个状态与栈顶符号整体规定的,所以机器在较长输入上的行为不会仅仅因为那个输入还有下一个字母而出现分歧。
确定性并不意味着每个格局都有可用的转移,也不意味着每次计算都会停机。缺失的转移可以拒绝某个输入。机器也可能有无限的静默移动序列,例如在同一状态下把 替换为 的转移。按照接受的定义,只有存在有限的接受性运行时,词才被接受。对于某个输入上具有无限静默循环的确定性机器,它在该输入上不一定给出会终止的是或否的回答。关于算法判定某语言的论断必须另行证明停机。
第一个定理并不假设机器在所有输入上都停机。它从对 的一次有限接受性运行出发,证明较长的输入被迫沿着这段有限的转移前缀运行。随后在此模型中,空栈使所有后续移动停止。即便其他输入会导致无限的静默循环,它们也不影响这个论证。
例题 2.9.6
(静默转移与输入转移的冲突)
假设 与 同时存在。在格局 下,机器既可以静默地移到 ,也可以读入 并移到 。因此按定义它不是确定性的。去掉其中一条转移可以消除这一特定冲突,不过其余每一个状态与栈顶符号的组合仍须逐一检查。
验证匹配机器
用状态不变量来检查这个构造,比起非正式地说“栈在计数”要容易得多。在 中,读入了 个连续的 且没有 之后,栈为 。在 中,读入了开头的 个 与其后的 个 (其中 )之后,栈为 。所列出的每条转移都保持相应的不变量:压入使指数加一,弹出使指数减一。
进入 的唯一途径要求在 中栈顶符号为 。此时不变量迫使 。由于 没有任何出转移,而接受要求输入耗尽,所以在接受性运行中不可能再跟随任何额外的符号。反过来,对每个 ,这些转移恰好读入 然后进入 。起始状态单独处理 。这就证明了两个方向的包含关系;仅检查成功的例子并不能排除多余的被接受词。
当栈顶为 时,机器在 上读入 没有转移,但在第一次压入之后该格局是不可达的。在这种部分机器模型中,要证明语言,形式的转移表不必填满不可达的条目。随意添加转移可能改变语言,或引入静默与输入的冲突,所以任何补全都必须明确规定并加以检查,而不能想当然地认为无害。
无前缀性说明了什么、没有说明什么
一个语言可以是无前缀的,却没有有限的机器描述。举一个具体的族:词 ()两两互不为前缀:对 ,较短的词在某个位置是 ,而较长的词在该位置仍是 。这个族的每个子集都是无前缀的。由对角线论证,这样的子集有不可数多个,但在固定的有限编码下,有限的 DPDA 描述只有可数多个。因此有些无前缀语言根本没有 DPDA。这个计数论证证明的是存在性;它并未指出某个具体的自然语言,也没有对确定性上下文无关语言这一类进行分类。
这一结论还依赖于栈的约定。在这里,空栈使所有转移都不可用,所以在以空栈方式接受了某个前缀之后,机器无法再读入非空的后续部分。如果别的形式体系允许在没有栈符号时进行转移,则证明的最后一步必须重新考虑。定义不仅仅是记号:证明恰好用到了模型所允许的那些操作。
终态并不具有同样的吸收性质。对于 的机器,允许在作为终态的起始状态上、输入为空时停机并接受,但在输入为 时它可以读入该符号并到达另一个终态。未读入输入必须为空的要求阻止了起始终态立即接受 。这个例子说明,确定性的终态机器可以既接受一个词又接受它的扩展,而不产生任何矛盾。
结束标记与转换论断
假设在每个输入之后附加一个新的符号 ,它不属于原字母表。此时 与 的编码在紧接 之后的位置出现差异:一个是 ,另一个是 的第一个符号。因此机器可以在此处作出不同的确定性决定。先前的前缀证明所比较的两次运行,在较短词的接受性运行的全程中看到相同的下一个输入符号;当较短的运行还必须消耗一个标记时,这种比较就不能以同样方式适用。
这一观察并不是关于一般结束标记等价性定理的证明。要证明这样的结果,必须规定标记何时被读入、它是否属于被识别的输入,以及静默转移与栈操作如何运作。类似地,从终态接受到空栈接受的非确定性构造在终态处加入了一个清理选择。若一条复制的输入转移同时可用,那么这条额外的静默移动就违反了 DPDA 的条件。对 NPDA 保持语言不变的转换,不一定保持这里所要求的语法上的确定性。
这一区分在阅读其他教材时很有用。有些教材用终态与结束标记来定义确定性上下文无关语言;有些则采用不同的栈约定。在移植某个论断之前,应当先翻译定义并检查其假设。上面证明的具体分离结果适用于本单元所规定的、无结束标记且采用空栈接受的模型,并不断言所有约定下的确定性表达能力都相同。
总结
DPDA 必须像处理输入移动那样处理静默移动。没有结束标记时,空栈接受迫使语言无前缀,而终态接受可以识别非无前缀的语言。当从压入到弹出的转换由输入来标示时,栈仍然支持确定性的匹配。
练习
快速检查
(在 上跟踪匹配机器,并写出它最终的栈。)
沿着证明中列出的转移走。
解答 · 答案
把 压入栈, 把它弹出,静默转移随即进入 ,此时栈为 ,没有未读入的输入。
快速检查
(匹配机器接受 吗?请说明。)
数一数 之后还剩下多少个 。
解答 · 答案
不接受。唯一的 之后还剩一个 ,机器停在非终态 ,而在该栈顶符号上没有可用的静默转移。
快速检查
(为什么在本模型中没有任何空栈 DPDA 能同时接受 和 ?)
把两个词当作字符串比较。
解答 · 答案
词 是 的真前缀,而这类 DPDA 以空栈接受的语言都是无前缀的。
快速检查
(为什么无前缀定理并不排除接受 的终态 DPDA?)
定理说的是哪一种接受方式?
解答 · 答案
该定理针对的是空栈接受。上面给出的两状态终态构造明确地接受这个语言。