动机
上下文无关规则只改写一个变元,而不顾其周围环境,这就是栈已经够用、同时 又无法企及的原因。要生成这样的语言,文法必须能够移动符号,并同时比较三个块的个数。这里研究的文法允许规则的左部是更长的串,同时加一个限制来控制推导:规则不得缩短句型。这一条限制有两个重大后果。它使一个固定终结符字的推导中每个中间句型的长度都有上界,并且说明所生成的语言可以由一台永不离开输入所占带区的机器识别。
我们证明一个完整的例子、长度引理、有界带上接受问题的可判定性,以及从文法到有界带机器的方向。反方向——从有界带机器到文法——延后处理:这里不予证明,下面也没有任何陈述依赖它。我们同样不对确定型与非确定型有界带机器是否接受相同的语言作任何断言。
定义
定义 4.1.1
(非收缩文法)
非收缩文法是 ,其中每条规则形如 ,, 至少含一个变元,且 。允许一个例外:可以有规则 ,条件是 不出现在任何右部。推导 、 与 的定义同上下文无关文法,一步是把 的某个出现替换为 。
若一个语言由某个非收缩文法生成,我们称它为上下文有关语言。另有一种更严格的规则形状 (),它给出同一类语言;这个等价性是标准定理,这里不予证明,所以下面所有陈述都只涉及非收缩文法。
定义 4.1.2
(线性有界自动机)
线性有界自动机(LBA)是一台非确定型图灵(Turing)机 ,其带字母表 含两个端点标记 。输入为 时带上是 ,读写头从 出发。读到 的转移必须写回 并右移;读到 的转移必须写回 并左移;其他转移都不得写入端点标记。因此机器恰好使用存放输入的 个单元,外加两个端点标记。如果某条计算到达 ,则机器接受 。
输入长度为 时,格局是一个三元组(状态, 个内部单元的内容,读写头在 个单元中的位置)。端点标记所在的单元永不改变,因此不需记录。
定义 4.1.3
(长度不减的推导)
对非收缩文法,若推导 满足 ,则称它是单调的。
定理
定理 4.1.4
(长度引理与成员问题的可判定性)
设 是非收缩文法, 且 。若 ,则该推导从不使用 ,是单调的,且其中每个句型的长度至多为 。因此,通过探索长度至多为 的有限多个 上的串,可以判定 是否属于 。
定理 4.1.5
( 的文法)
起始变元为 、规则为 ,,,,, 的文法是非收缩的,且恰好生成 。
定理 4.1.6
(有界带机器的接受问题是可判定的)
设 是 LBA, 是长度为 的输入。格局数至多为 ,并且 接受 当且仅当它有一条步数少于 的接受计算。因此存在一个算法,对作为数据给出的 LBA,判定 是否接受 。
定理 4.1.7
(从非收缩文法到 LBA)
对每个非收缩文法 ,存在 LBA 使 。
定理 4.1.8
(确定型标记算法)
存在一台确定型 LBA,它只使用 中的单元内容和端点标记,在 步内恰好接受 的字 。
证明思路
证明
(长度引理与可判定的成员问题)
长度引理。 推导中所用的规则把 替换为 ,且 ,唯一的例外是 。该例外需要有一个 的出现可供改写;因为 从不出现在右部, 只出现在初始句型 中,所以这个例外只能是第一步,并产生 。对 ,例外从未使用,所以每一步都不缩短,推导是单调的,最后的句型 最长。关于可判定性:长度至多为 的 上的串的集合 是有限的。计算 中从 出发、通过应用结果仍在 内的规则所能到达的串的集合,反复迭代直到不再有新的串加入;由前一部分, 当且仅当 在该集合中。
证明
(三块文法的可靠性与完备性)
的文法。 每条规则都有 ,且每个左部都含变元,所以 是非收缩的; 出现在右部,但没有规则 。对 的 :恰好应用 次 ,再应用 ,得到 。反复使用 ,把每个 向左移过所有 ,得到 。然后 把第一个 变成 ,每个 变换下一个,类似地 之后用 自左至右把各个 转换。
反向我们证明一个不变量。定义两族串。第一族:,其中 含 个 与 个 。第二族:,其中 ,, 且 。我们断言从 可达的每个句型都属于这两族之一。起始句型 属于 的第一族。对 应用 得 ,属于 的第一族;应用 得 ,属于 、 的第二族。现在考虑对第二族句型 应用各条规则。规则 需要一对相邻的大写字母;大写字母只出现在 中,所以它在 内起作用并保持各个个数。规则 需要小写 紧跟 。 是开头的一块,其后的符号:若 是 的第一个符号,若 则是 的第一个符号。所以该规则只在 且 以 开头时适用,产生 (),属于 的第二族。规则 需要 紧接 之前:这只发生在 、 且 以 开头时,给出 。规则 类似地需要 、 且 以 开头,给出 。规则 需要 且 以 开头,给出 。每种情形下个数条件都得以保持,因为一个大写字母变成了对应的小写字母。对第一族句型 起作用的规则只有两条 -规则以及 内的 ;含 或 的规则不能适用,因为 把 与 隔开了。所以断言成立。终结符字不含 、、,所以它属于 的第二族,因而 ,该字为 的 。
证明透视
$a^n b^n c^n$ 文法的不变量在做什么
两件事被一起保持:一个计数事实( 的个数、 或 的个数、 或 的个数相等)和一个次序事实(所有 在 之前, 在 之前,尚未确定的大写字母拖在后面)。计数被保持,因为每条规则要么每种字母类型各加一个,要么只是给字母改标记。次序才是微妙之处:小写字母只能紧接在已有的小写字母之后生成( 接在 或 之后, 接在 或 之后),所以小写字母从左到右增长。该不变量也解释了那些死路—— 被困在小写 之后:这样的句型满足计数事实,但永远不可能变成终结符串。
证明
(以最短路径判定有界带上的接受)
有界带上的接受问题。 格局由状态( 种选择)、 个内部单元( 种选择)和读写头位置( 种选择)决定,由此得界 。把格局看作一个有限有向图的顶点,每个可能的一步对应一条边。接受意味着从初始顶点可以到达某个状态为 的顶点。最短路径经过的顶点互不相同,所以其边数少于 。确定型算法探索该图,例如作广度优先搜索,直到不再出现新顶点,若到达过接受状态的顶点就回答“是”。重复格局之间的一段是可从接受路径中删去的环。非确定机器再次到达同一格局后仍可能选择另一条出路;排除重复所依据的是最短路径论证,而非所有未来选择都必循环。
证明
(在填充带上做反向推导)
从文法到 LBA。 固定 与输入 ,。若 ,则恰好在 是规则时接受。设 ,以下所有逆规则选择均排除例外 ,因为它不可能出现在非空串的推导中。使用一个额外的带符号 ,即不在 中的填充符号。不变量是:带的内部始终具有形式 ,其中 是长度至多为 的句型。起初 。机器重复如下过程。首先检查带是否为 ;若是则接受。否则它猜测 的一条规则 和一个位置,并通过扫描验证该处的单元含有 ( 的长度被 的某个常数所限制,所以这一检查只需有限的记忆)。它把 替换为 ,把带的其余部分逐个符号地向左移动 个单元,并在右端写下 个 。新的带是 ,其中 是所选步骤的逆。所有操作都停留在 个内部单元之内。
正确性:若机器接受,则各轮之间带内容给出句型 ,且 ,所以 。反之,若 且 ,由长度引理,存在一个所有句型长度至多为 的推导,所以机器可以逆向跟随它,每轮选择合适的规则和位置,最后在 处接受。该机器是非确定型的;这个证明并未产生确定型机器。
证明
(标记轮次的正确性与代价)
标记算法。 阶段零用固定的有限个控制状态扫描输入一遍,除非输入属于 就拒绝;设三个个数为 。一轮从 开始。它跳过符号 ,若下一个符号是 就把它换成 ;然后向右越过各个 与 ,把第一个 换成 ;再越过各个 与 ,把第一个 换成 ;然后回到 。若期望的符号没有找到(寻找 时扫描遇到 、 或 ,或寻找 时遇到 ),就拒绝。若第一个非 符号是 ,说明已没有未标记的 :此时向右扫描,恰好在 之前只出现 与 时接受。经过 轮成功之后,未标记的个数分别是 、、。若 或 ,第 轮找不到所需符号而拒绝。若 轮都成功,则不再有 ,机器当且仅当不再有 和 时接受,即当且仅当 。每轮花费 步,至多有 轮。
反例模式
空串例外不能随意取消
断言(错误):文法 是非收缩的,所以长度引理用字的长度来限制它的推导。事实上 是不允许的,因为 出现在右部。推导 的长度为 ,最后一步缩短了,所以长度引理对它不成立;对 ,若通过检查长度至多为 的句型来判定成员问题,就会错过长度为 的中间句型 。修正:引入新的起始变元 ,规则为 ,并令 。这样 不出现在任何右部,每条规则都是非收缩的,语言不变。
概念视角算法
有界空间上的逆向推导即搜索
该模拟并不生成字;它从输入出发,逆向搜索一个推导。每个带内容是有限图(有限字母表上长度为 的串)的一个节点,每次逆向应用规则是一条边。长度引理保证图是有限的,填充技巧使每个节点都放得进 个单元。接受就是从节点 到达唯一的节点 。
例题
例题 4.1.9
(推导 aabbcc)
取 :。各步依次使用 ,,对中间一对用 ,,, 与 。长度依次为 ,正如引理所要求的那样不减。最后的句型每种字母各有两个,与计数不变量相符。
例题 4.1.10
(一个无法完成的推导)
如前开始:。在第二个 处应用 得 ,再应用 得 。此时 之前是小写 。没有任何规则的左部以 结尾,而 要求 的左边是大写 ,所以没有规则能作用于这个 。这个句型满足计数不变量,但大写字母出现在小写 之后;它永远不可能变成终结符串,这与证明中第二族要求小写字母必须自左向右生成是一致的。
例题 4.1.11
(在六个单元的带上逆向推导 aabbcc)
用填充符号 书写带。开始:。逆向 :。逆向 :。逆向 :。逆向 :。对中间一对逆向 :。对从第二个位置开始的块 逆向 :块 被换成 ,其余部分左移两个单元:。逆向 :四个单元 变成 ,带为 。这就是 时的接受带内容,所以机器接受。所有句型长度至多为 ,与长度引理的保证一致。
例题 4.1.12
(aabbcc 上的标记算法)
阶段零确认形状 之后,第一轮标记第一个 、第一个 与第一个 :。第二轮标记其余的:。第三轮开始时,跳过 之后读写头遇到 ,所以不再有 ;向右扫描直到 只发现 与 ,机器接受。对 ,第一轮得 ,第二轮标记 与 得 ,但随后找不到未标记的 ,机器拒绝。
常见错误
常见错误
(空串只能借助受保护的开始规则进入)
一个常见错误是说非收缩规则禁止语言含 。对 的例外(要求 不出现在右部)恰恰就是允许空串的办法。
常见错误
(CB 换成 BC 并非无关紧要的重排)
规则 是唯一移动大写字母的规则,正是它使计数比较成为可能。它必须在 被转换之前,把每个 都移到每个 之前;否则某个 可能被搁在小写 的后面,如第二个例题所示。
常见错误
(不要把 LBA 的结果读出超过已证明的内容)
说 LBA 可以“想用多少带就用多少”是错误的。按这里的定义,它恰好使用输入单元与两个端点标记,定义中没有其他空间界。最后,不要从“文法到 LBA”的定理推出每个 LBA 语言都有文法,也不要推出已经比较了确定型与非确定型机器。这些陈述都在已证明的范围之外。
总结
非收缩文法不能缩短句型,因而非空串的每个推导都以该字的长度为界,成员问题随之可判定。 的文法用一个明确的不变量来验证。有界带机器只有有限多个格局,所以其接受问题可判定。每个非收缩文法都可以由一台在填充过的带上逆向运行推导的 LBA 来模拟。反方向延后处理,也不对确定性作任何断言。
练习
快速检查
(在第二个定理的文法中推导 ,并数出步数。)
解答 · 答案
(三步)。三次交换 得 (例如 )。然后 、、 得 (三步),再用 、、 得 (三步)。总计 步。
快速检查
(在 上跟踪标记算法,并解释它为什么拒绝。)
解答 · 答案
阶段零接受形状 。第一轮得 。第二轮标记剩下的 与 ,得 ,然后寻找未标记的 :跳过 后到达 ,于是拒绝。个数 不相等。
快速检查
(一台 LBA 有 个状态,带字母表 的大小为 。对长度为 的输入,用第三个定理中的公式给出格局数的界。)
解答 · 答案
界为 。任何接受计算都可取为少于 步。
快速检查
(设 是变元集不相交、且没有规则 的非收缩文法。构造 的非收缩文法并证明其正确性。)
解答 · 答案
取两个文法的全部规则,再加一个新的起始变元 与规则 。这两条新规则是非收缩的(长度相等,左部是变元),且 不出现在任何右部。由 推出的句型要么是 ,要么是由某个 推出的句型。由 推出的句型只含 的变元与终结符,而 ()的每条规则的左部含 的变元,所以不能适用。因此从 出发的推导恰是 或 的推导前面加一步,所得语言就是并集。