计算理论：上下文无关文法的属性

course notes › theory of computation

Properties of Context-Free Grammar

The Pumping Lemma for CFL

考虑一个 CNF 文法 的 parse tree，且其 yield 为 ，若最长路径长度为 ，则有

Proof.

根据 归纳即可

Basis. ，最长路径长为 1 的 parse tree 只有一个 root 和一个标记为 terminal 的叶节点，故 ，而

Induction. 考虑最长路径为 ，则根节点一定使用了产生式 ，则任意子树中最长路径都不超过 ，根据 I.H. ，两颗子树的 yield 长度均不超过 ，则整棵树的 yield 长度不超过

Q.E.D.

Pumping Lemma: 令 为一个 CFL，则存在常数 ，对于任意属于 的 string ，若 ，则可以将 写作 ，并且满足

  • 对任意 ，有

Proof.

考虑 的 CNF 文法 ，满足 ，则假设 中有 个 variable，令 ，令 为 中长度至少为 的 string，根据上文的结论，任何最长路径为 的 parse tree 其 yield 长度不超过 ，则 yield 为 的 parse tree 最长路径至少为

考虑最长路径，设其长度为 ，则其路径上出现了 个 variable ，记为 ，而 中有 个不同的 variable，根据 PHP，路径上至少有两个 variable 是相同的，考虑路径上的最后 个 variable，即 到 ，设

则可以划分 parse tree 的 yield，令 为子树 的 yield，令 为子树 的 yield，令 为整棵树的 yield。由于 CNF 没有 unit production，故 不同时为

因此可以构造新的 parse tree，如使用 的子树代替 的子树，则 yield 为 ，对应 中 的情况。或是可以用 的子树代替 的子树，即 ，同理可以得到

同时由于选择的是最后 个 variable，即 ，则 的子树中最长路径不会超过 ，则其产生的 string

Q.E.D.

Pumping Lemma 可以用于证明某 language 不是 CFL

Closure Properties of CFL

Substitutions

考虑 alphabet ，为其中每个元素 选择一个语言 ，这个语言可以是定义在任意 alphabet 上的任意语言，则可以定义一个函数 。对于 string

即 是一系列 language 的 concatenation，则对一个语言

则有：若 是一个定义在 的 CFL ，且对于每个 ，有 为 CFL，则 是 CFL

Proof.

基本思路为根据 的 CFG，将其中每个 terminal 替换为 的 CFG 的开始符号

设 的 CFG 为 ，而 的 CFG 为 ，且为了便于讨论，设 以及任意 的元素不重名。

则可以为 构造一个新的 CFG ，其中

  • 是 与所有 的 union
  • 是所有 的 union
  • 包含
    • 所有 的产生式
    • 所有 的产生式，但将所有 terminal 用 代替

则只需证明

(): 考虑 ，则设 ，且 ，则有 ，则原本从 推导出的 在 中将推导出 。由于 包含所有 中的产生式，则 同样是 中的推导，故有 ，即

(): 若 ，则在推导过程中一定有 ，因为在推导的开始将只使用 中的产生式，直至推导出某个 ，而在 的子树中将只使用 中的产生式，因此根据该推导过程的 parse tree，可以得到一个字符串 ，且 ，满足

  • 在 parse tree 中删除某些子树，其 yield 为

由于 ，故易得

Q.E.D.

根据 substitution 的封闭性，可以得出 CFL 对于下列操作是封闭的

  • union
  • concatenation
  • closure () and positive closure ()
  • homomorphism

Proof.

只需构造特定的 substitution 即可

  • union：对于 CFL ，，其中
  • concatenation：对于 CFL ，，其中
  • closure and positive closure：考虑 CFL ，令 ，则 ，同理，若 ，则
  • homomorphism：考虑 是定义在 的 CFL，而 是定义在 的 homomorphism，则对于任意 ，定义 ，则

Q.E.D.

Other closure properties

Reversal: 如果 是 CFL，则 也是 CFL

Proof.

构造 的文法 使得 ，则对于 其 CFG 为 ，其中 为每个产生式的 reversal，即若 ，则

对推导长度归纳即可得出

Q.E.D.

Intersection: CFL 对 intersection 是不封闭的，考虑

上述两个语言都是 CFL，可以为其构造出对应的文法，但是其 intersection

不是 CFL（pumping lemma 即可证明）

但是 CFL 和 正则语言的 intersection 仍是 CFL，即

对于 CFL 和正则语言 ， 仍是 CFL

Proof.

只需要平行地运行 PDA 和 DFA 即可

令 PDA 满足 ，令 DFA 满足

则可构造 PDA

定义

注意当 PDA 在 上转换时，DFA 不改变状态

根据推导步数的归纳可以得出

且 为接收状态 ，故

可以得出

Q.E.D.

同样可以得出对于 CFL 和正则语言 满足

  • 是 CFL
  • 不一定是 CFL
  • 不一定是 CFL

Proof.

  • ，而 是正则
  • 若 总是 CFL，则考虑 ，这与上述结论矛盾
  • 若 总是 CFL，则 也是 CFL，这与上述结论矛盾

Q.E.D.

Inverse Homomorphism: 证明思路类似证明正则语言对 inverse homomorphism 是封闭的。构造一个 PDA，每当读入一个输入 ，则将 放入一个 buffer 中，每次读取其中一个符号，用于模拟 PDA 的运行，直至读入结束，再读入下一个符号

考虑 CFL 和 homomorphism ，则 也是 CFL

Proof.

假设 定义在 上，且输出的 string 属于 ，且假设 是定义在 上的语言，则有 PDA 满足 ，则构造一个新的 PDA

其中

中的元素 满足 且 是某个 的后缀，即用 来模拟 buffer

由于 是有限的，故 也是有限的，则 中的状态也是有限的

对于 ，其定义分为两种情况

  • buffer 为空，即 ，此处的 。即当 buffer 为空， 读入下一个输入 并将 放入 buffer

  • buffer 不为空，则若 ，则

    即 用 buffer 中第一个 symbol 模拟 的运行

则有

证明基于对推导步数的归纳即可。需要注意的是 在 buffer 非空时一定模拟 的运行，但是当 buffer 为空时仍有可能继续模拟 的运行

故 ，即

Q.E.D.

Decision Properties of CFL

对于 CFL 的 decision properties，有一些是有确定的算法可以解决的

  • 判断 是否在 CFL 中
  • 判断 CFL 是否为空
  • 判断 CFL 是否无限

而有一些没有算法可以解决，换言之这些问题是 undecidable 的

  • 判断两个 CFL 是否相等
  • 判断两个 CFL 是否 disjoint

Emptiness: 测试 CFL 是否为空只需要测试其开始符号 是否为 generating 即可

CFL 非空 其开始符号 为 generating

Membership: 有一种算法利用 DP 的思想，若 string 的长度为 ，可以在 的时间内确定这个 string 是否在给定的 CFL 中，即 CYK 算法。

考虑 CFL 及其 CNF 形式的文法 ，设 ，算法构造一个三角矩阵形如

其中

则

从底向上，第 行的条目都代表了一系列 variable，可以推导出长为 的 substring

计算表中条目是一个从底向上的归纳的过程

Basis. 即最底下一行，

Induction. 假设需要计算 ，位于第 行，且其下的条目都已计算，则任意推导过程

都从 开始，则对某个 有

则需要找到所有满足

的 ，这样的 即为 的成员

CYK 算法的正确性从其归纳的计算过程中即可得出。

算法计算每个条目需要 的时间，因为其要检查每个 对，而表中一共有 个条目。故其运行时间为

Infiniteness: Infiniteness 的测试思想与正则语言相同，对于 pumping lemma 的常数 ，只需测试长度在 的 string 是否都在 中即可

存在一个满足条件的 string 则 为无穷