-1

上下文无关语言集合的联合总是上下文无关的吗？证明你的答案......

我知道答案是肯定的，但我该如何证明呢？

4

1 回答 1

1

为了证明上下文无关语言的有限联合是上下文无关的，你只需要为联合语言构建一个上下文无关语法，就像你证明两种上下文无关语言的联合是上下文无关的一样.

如果 G1,...,GN 是您拥有的 N 种上下文无关语言的上下文无关文法，请重命名每个文法中的所有符号（添加下标以避免符号名称冲突），然后创建一个新文法 G包含来自 N 个语法的所有产生式，加上产生式：

S -> S1 | S2 | ... | 序列号

该语法生成​​联合语言，并且它是上下文无关的。

于 2012-05-04T18:28:10.390 回答