有限自动机可以用状态记住有没有见过分隔符,但有限个状态不能单独记住任意多个开启符号。下推自动机(PDA)增加了一个栈。重要的不只是“要压入什么”,而是每一步之后,栈证明了什么事实?不变量让我们由几次看似合理的操作,进一步证明对任意长度的输入都成立。
我们先识别两个等长区块;由 a 转到 b 会显示何时开始匹配。然后考虑没有分隔符的偶长度回文:机器可能要猜测何处停止压入。我们会区分一次猜测失败,与整个输入被拒绝。
约定:构型与接受
定义 9.1.1
(构型记录什么)
构型写成 ,依次记录当前状态、尚未读入的输入及栈。我们把栈顶写在左边。底符 起初已在栈中;下列机器都不会把它弹出。
一次转移可以读入一个输入符号,也可以读 (不消耗输入);它查看栈顶,再用有限字符串替换该栈顶符号。例如以 替换 是压入 ;以 替换 是弹出 。
我们使用最终态且输入读尽的接受方式:只要存在至少一条有限运行,到达最终态且没有未读输入,便接受该字符串。到达最终态但仍有未读输入,并不构成接受。没有适用转移时,该运行便停止;对非确定性机器,只有在不存在任何接受运行时才拒绝字符串。
这只是本节的约定;其他教材可能把栈顶写在另一边,或采用不同的接受方式。栈没有预先固定的长度上限,但每条有限运行只使用有限个格子。
等长区块:栈记录未匹配的前缀
令
使用压入状态 、匹配状态 和最终态 ;起始构型是 。下表列出全部转移,其余情况没有转移。表中 代表 或 。
| 状态 | 读入输入 | 栈顶 | 新状态 | 用什么替换栈顶 | 作用 |
|---|---|---|---|---|---|
记下一个未匹配的 a | |||||
| 开始匹配并弹出 | |||||
再匹配一个 b | |||||
| 或 | 结束,保留底符 |
特别地, 没有后续转移。即使 中的 非空,仍可提前取 转移;但这样有输入未读,不能接受。空串则可直接被接受。
命题 9.1.2
(区块机器恰好接受等长区块)
上表的机器由 开始,当且仅当对某个 有 时,接受 。
证明
(栈不变量,再证两个包含方向)
开始匹配之前,读入 个 a 后的栈是 。一旦读入 b,机器便进入 ,不能再读 a。一条运行读入 后,栈是 ;运行存在时必有 。
证明不会多接受:接受运行若从 进入最终态,尚未读入字母,只得到 ;否则它在读入 后到达 ,其中 。要进入 ,栈顶必须是 ,所以 。接受又要求输入全部读尽,因此没有被忽略的后缀。所接受的字符串必是 。
证明不会漏接受:给定 ,每读一个 a 压入一次,每读一个 b 弹出一次,最后取 转移。 时直接取最后的转移。故 的每个字符串都有接受运行;两个方向合起来得到语言相等。
证明透视
机器每一部分的作用
证明依靠一个不变量:在状态 读入 后栈是 ,在 读入 后栈是 。控制状态与栈分工合作。由 到 的转换发生在第一个 b,并且没有回头的路,所以控制状态负责限制次序 ;栈负责计数,因为只有 时 才在栈顶。 永远不会被弹出,所以“栈顶是 ”可靠地表示没有未匹配的 a,结束转移正是以此作为条件。结束转移不读入符号,所以接受还要求输入读尽,这就排除了在非空串上提前结束。
每个部分都不可少。若结束转移不看栈顶符号,aab 就会被接受:运行到达 后便可结束。若把 并入 ,让 既可压入又可弹出,abab 就会被接受:栈依次是 。
常见错误
(最终态不等于接受)
到达 并不够,输入还必须读尽。由 取 转移得到 ,这是最终态,但符号 b 仍未读。若把它当作接受,就会接受不属于 的 b。只有结束于 且输入全部读尽的运行才算数。
例题 9.1.3
(一条完整运行和三种失败原因)
对 aabb,连同状态及未读后缀一起记录:
aab 读完后在 ,栈仍是 ,有一个 a 未匹配。abb 的第二个 b 到达时栈顶是 ,没有读取它的规则。aba 读过 ab 后已在 ,没有规则读最后的 a。提前进入 也不能挽救这些输入,因为仍有未读符号。
反例模式
总数相等仍不足够
断言:每个 a 与 b 数目相等的字符串都属于 。abab 有两个 a 和两个 b,但不是 的形式。机器拒绝它:,之后在 无法读入 a;提前转入 则留下未读的 ab。栈核对数目,次序 则由 转入 的状态变化保证;单凭数目不能决定字符串是否属于语言。
没有分隔符:猜一个切分,再核对
定义 9.1.4
(倒序与偶数回文)
对字符串 ,其倒序 是把 倒过来写所得的字符串。 上的偶数回文语言为
例如 0110 属于 ,取 ;010 不属于 ,因为 的所有字符串长度皆为偶数。空串也在 中。
使用压入状态 、匹配状态 和最终态 ,起初栈为 。 可读取 0 或 1,并把相同符号压入;也可随时以不改变栈的 转移切换到 。在 ,只有栈顶是 0 才可读 0,只有栈顶是 1 才可读 1;匹配后弹出栈顶。最后,仅当栈顶是 时,才可用 由 进入 ,并保留 。没有转移返回 ,没有转移消耗 , 也没有后续转移。
对固定有限输入,可能猜的位置只有有限个:最多切换一次,可在字符串符号之间选择位置。本机器没有 循环。定义要求的是一条接受的有限运行,不是假设机器能预知未来。
例题 9.1.5
(同一字符串的成功与失败猜测)
对 0110,先压入头两个符号;栈成为 ,栈顶是 1,未读输入为 10。切到 ,匹配并弹出 1,再匹配并弹出 0。输入已空而栈是 ,进入 ,此运行接受。
如果在第一个 0 之后便切换,栈顶是 0,下一个未读符号却是 1,该运行没有匹配转移而失败。字符串仍被接受,因为读完两个符号后切换有成功运行。
命题 9.1.6
(猜测机器恰好接受偶数回文)
上文所述、含状态 、、 的机器,当且仅当字符串属于 时接受该字符串。
证明
(栈保存倒序的前缀)
假设一条运行在读过前缀 后切换。压入规则使栈成为 。匹配阶段每读一个符号,都要与当前栈顶相同并弹出它。进入 前, 上面的符号必须全部移除;接受又要求输入全部读尽。因此剩余输入恰好是 ,每个被接受的字符串都有 的形式。
反过来,对任意 ,在读完 时选择切换。此时栈是 ,第二半依序匹配并移除栈符号;输入读尽并只剩 后,最后的转移便接受。 也适用。因此机器识别的正是 。
证明透视
为何一次成功的猜测就足够
这个证明是不对称的,而这种不对称正是非确定性的含义。证明不会多接受时必须涵盖每一条运行,所以从任意切换位置 出发,证明字符串是 。证明不会漏接受时只需一条运行,所以给出读完 后的那一次切换即可。只要有某个切分成功,字符串就被接受;失败的切分无关紧要。
不变量是:压入 后,由栈顶往下读,栈是 。栈以相反次序交还符号,这正是后半部必须被读取的次序。转入 时“栈顶是 ”的条件保证每个被压入的符号都已匹配。若没有它,运行 便会接受 0,一个长度为奇数的字符串。切换只会发生一次,因为没有转移回到 。
例题 9.1.7
(两台机器所接受的最短字符串)
对等长区块机器,空串只用结束转移:;ab 的运行是 。对回文机器,空串需要两次 转移:;00 在读入一个符号后切换,运行是 。每种情况下,栈最后都是 而输入读尽。空串是边界情形:从未压入任何符号。
反例模式
一条失败运行并非拒绝的证明
对 0110,在第一个符号后猜中点会失败,但在第二个之后猜则成功。要证明拒绝,必须涵盖所有切分。对 010,若一条运行成功,压入与稍后弹出的输入符号数必须相等,因此总长必须是偶数。它的长度是三,所以所有切分都失败;不能只凭一条失败轨迹作此结论。
常见错误
(栈会倒序,所以 不等于 )
这台机器识别的是 ,不是 。字符串 0101 等于 (),却被拒绝:唯一前后等长的切分在两个符号之后,此时栈是 、栈顶为 1,而下一个输入符号是 0;其他切分都因长度或不匹配而失败。后半部必须是前半部的倒序。
若输入改为含有单一分隔符的语言 ,阶段边界便可见:在 # 之前压入、读到 # 时切换,然后匹配后缀。例如 0#0 被接受。分隔符必须恰好出现一次,且后缀仍须完全匹配。这个比较解释了猜测的用途,本身并不证明其他语言的一般确定性或非确定性定理。
检查理解
快速检查
(追踪等长区块机器处理 aabb。第一个 b 之前及之后的栈分别是什么?)
解答 · 答案
第一个 b 前,状态是 ,栈是 。读取它时弹出一个 并进入 ,留下 。第二个 b 后剩下 ;此时输入也已读尽,最后的转移才可接受。
快速检查
(等长区块机器接受 abba 吗?用未读输入解释。)
解答 · 答案
不接受。读过 ab 后,机器在 、栈为 ,未读输入是 ba,它不能读下一个 b。虽然可用 进入 ,但 ba 仍未读,而 没有后续转移,因此不存在接受运行。
快速检查
(对 1001,给出回文机器的一个成功切分,以及切分时的栈。)
解答 · 答案
取 。先后压入 1 和 0 后,栈是 ,栈顶为 0。余下 01 依次匹配并弹出这两个符号;输入读尽、栈为 ,转入 后接受。
快速检查
(回文机器在 0011 的 00 之后切换会接受吗?其他切分有帮助吗?)
解答 · 答案
读过 00 后栈顶是 0,下一符号是 1,所以该切分失败。每个压入的符号都必须由一个后来的符号匹配并弹出,因此任何接受切分都必须把四个符号分成等长两半。唯一可能成功的是两个符号后切换;它失败了,所以 0011 被拒绝。
两个例子以相同的栈原则处理不同的问题:等长区块利用可见的输入变化开始匹配;偶数回文则非确定性地选择切分。每次证明都指出不变量,证明接受的字符串必有指定形式,再为语言中的每个字符串构造成功运行。