嵌套结构与有限状态限制
上下文无关文法可表达递归嵌套结构,有限自动机则可用有限个状态实施条件。两者的交集可同时实施这两项要求。这个封闭结果有其特殊性:两个任意上下文无关语言的交集未必上下文无关。我们会构造文法,包括空串的规则,并双向证明它的含义。
令 为有限上下文无关文法。每条产生式左边是一个变元,右边是有限的变元与终结符序列;右边也可以为空。有限分析树在每个变元节点应用一条产生式,其终结符叶子由左至右读出所得的字符串称为产出。令 为确定有限自动机,状态集 有限,转移函数 处处有定义。以 表示从状态 读入字符串 后到达的状态,且 。
目标是构造 的文法:其字符串必须由文法推导,并使自动机由 到达 中的状态。此构造不要求文法具有特定范式,也不依赖现成的文法到栈的转换。
记录进入与离开状态的变元
定义 7.1.1
(进出变元)
对每个 及 ,引入变元 。它的预期语言恰由那些能从 的 推导、并使自动机由 到达 的终结符串 组成。加入新的起始变元 ,并对每个 加入规则 。若 为空, 没有这类规则,所构造语言便为空。
定义 7.1.2
(相容状态序列与乘积规则)
对每条原产生式 ,其中每个 是变元或终结符,考虑每个状态序列 。若每当终结符 时,DFA 转移都满足 ,便称此序列相容。对每个相容序列加入
其中若 是变元,则 ;若它是终结符,则 。对空产生式 ,为每个 加入 ,不加入进出状态不同的空规则。由于 和 有限、每条右边长度有限,所得规则数有限,但可能随该长度及 迅速增长。
构造为何正确
引理 7.1.3
(进出变元的含义)
对每个 、所有 及每个终结符串 ,变元 在所构造的文法中能推导 ,当且仅当 在 中能推导 且 。
证明
(对分析树高度作归纳)
先设 以一棵有限树推导出 。对树的高度作归纳:其首条规则要么来自空产生式,此时 且 ;要么来自原产生式 与相容序列 。把 写成 ,其中 是第 个子节点的产出。若 是终结符,则 ,由相容性得 。若 是变元,子节点 的树更矮,由归纳假设, 在 中推导 ,且 。因此在 中有 ,并且把 步合起来得 。在空的情形, 是原产生式,而 。
反过来,设根为 的原分析树产出 ,且 。把 分成根规则右侧各符号 的产出 ,其中终结符本身是一个符号的片段。令 、;这是每个片段前后唯一的 DFA 状态,且 。对终结符 ,有 ,所以序列相容,根规则 存在。对变元 ,其子树较矮,且其产出把 带到 ,由归纳假设, 能推导 。把这些推导接到根规则上,便得 。若 ,则 且 ,可用明列的空规则。
证明透视
DFA 的各项假设用在哪里
关键的一步,是让文法选择中间状态,而让字符串去核对它们。构造为每条产生式列出每个状态序列,等于一次猜遍所有可能的中间状态;引理的两个方向表明,只有 DFA 实际经过的序列才能得出完整的推导。
用到三项假设。 有限使规则表有限。 的确定性与全定义性使每个字符串恰有一个状态序列,所以反方向可以毫不含糊地选定根规则;若是 NFA,相容性应改为 ,引理则改为 。空规则要求 ,是 DFA 对空串的行为进入证明之处:读入 不会使它移动。
这个论证不能推广到两个文法。在边界处,关于 DFA 的信息是有限集合中的一对状态;关于第二个文法的对应信息,却会是大小没有上界、类似栈的对象。
定理 7.1.4
(对正则语言交集的封闭性)
设 为上下文无关文法, 为同一字母表上的 DFA。以 为起始变元的所构造文法,恰好产生 。特别地,上下文无关语言与正则语言的交集是上下文无关的。
证明
(选取接受的离开状态)
仅有的规则是 (),所以 能推导 ,恰好当某个 使 能推导 。由引理,这恰好当 在 中推导 ,且对某个 有 ,即 且 。若 ,两边都是空集。证明使用的是有限推导树。
概念视角结构
标注了自动机状态的分析树
所构造文法的分析树,就是 的原分析树,其中每个变元节点 带有两个标签:DFA 在读入该节点产出之前的状态 ,以及读完之后的状态 。由左至右读各叶子时,标签首尾相接:一个片段的离开状态就是下一个片段的进入状态,而终结符叶子 把 带到 。所以交集文法并不是让两台机器并排运行,而是把 DFA 的轨迹记录为分析树上的标注。
例题:偶数层嵌套
例题 7.1.5
(含偶数个 a 的嵌套区块)
取字母表 上的文法 ,它产生 ,其中非空规则嵌套应用 次。令双状态 DFA 从 开始并接受 ;每读一个 便切换 ,读 则保持状态。它恰接受含偶数个 的字符串。
对 ,以 表示另一状态,非空产生式给出
空产生式给出 和 ;新起点只有规则 。例如,
依照引理,该文法恰产生 。空串被包含:原文法和 DFA 都接受它,且 。
例题 7.1.6
(为何 ab 不被产生)
字符串 属于 ,因为 ,但 DFA 拒绝它。 的规则是 与 。要得到 ,必须用第一条,然后 。 仅有的规则是 ,而且不存在进入状态为 、离开状态为 的空规则。因此 不能推导 。
例题 7.1.7
(终结符在最后的位置,以及一个边界情形)
设 有 ,产生 。令 DFA 每读一个 便切换 ,读 则保持不变,从 开始,只接受 。由相容性得,对所有 有 ;又因为 必须满足 ,只有规则 与 。起始规则是 。于是
并且 。字符串 不能被推导:它需要 ,但这不是规则,因为 使 DFA 停留在 。字符串 也不能被推导:读完 后变元又是 ,其唯一规则以 开头。所产生的语言是 。
常见错误
(空规则的进入与离开状态必须相同)
加入 的 看似无害,其实是错的。在偶数层嵌套例子中,若加入 ,便会有 ,文法就会产生 ;它只有一个 ,被 DFA 拒绝。读入空串永远不会使 DFA 移动,所以只有 是正确的。
限制与练习
构造假设 DFA 使用相同字母表;若输入是 NFA,可先将它确定化。定理不证明两个任意上下文无关语言的交集仍封闭,也不意味只凭有限规则构造就能有效解决所有涉及两个文法的问题:它描述的是对指定输入所作的有限转换。
反例模式
同一想法不能用来交两个上下文无关语言
断言:若 与 都是上下文无关的,则 也是,方法是同一个三元组构造。取 ,由 、、 产生;又取 ,由 、、 产生。字符串 属于 恰好当 ,属于 恰好当 ,所以 。依上下文无关语言的泵引理,这个语言不是上下文无关的;此标准结论在此不予证明。构造在这里失效,是因为三元组以有限集合中的两个状态概括 DFA 的轨迹,而要概括第二个文法的栈,则需要没有上界的信息。定理要求两个语言之一是正则的。
快速检查
(在偶数层嵌套例题中,追踪 DFA 读取 的状态,并解释为何所构造起点能推导该字符串。)
先追踪 DFA 读入四个 的状态。
解答 · 答案
DFA 读四个 时依次是 ,读每个 时停留在 ,所以最后在接受状态 。起点可推导该字符串:,最后一步用 。
快速检查
(若原文法有 ,为何只可在 时加入 ?)
读入空串时,DFA 的状态会怎样?
解答 · 答案
读入 不会改变 DFA 的状态,。若加入 的 , 就会推导出 ,而 ,与引理矛盾。在偶数层嵌套例子中,这会使 推导出 。
快速检查
(若 ,新起点能推导什么?解释为何这与交集一致。)
看看有哪些以 为左边的规则。
解答 · 答案
不存在规则 ,所以 推导不出任何字符串,所构造的语言为空。没有接受状态时 ,所以 ,两者一致。