无上下文语言联盟 [英] Union in context-free languages

问题描述

无上下文语言集合的联合是否总是无上下文关系？证明您的答案是正确的....

Is the union of a collection of context-free languages always context-free ? Justify your answer .....

我知道答案是肯定的，但是我怎么证明呢？

I know that the answer is yes, but how can I prove it ?

推荐答案

要显示上下文无关语言的有限联合是上下文无关的，您只需要构建上下文无关的语法对于联合语言，就像您要证明两种无上下文语言的联合是无上下文的一样。

To show that the finite union of context-free languages is context-free you just have to build a context-free grammar for the union language, exactly as you would do to prove that the union of two context-free languages is context-free.

如果G1，...，GN是您拥有的N种无上下文语言的无上下文语法，请重命名每个语法中的所有符号（添加一个下标只是为了避免符号名称冲突），然后使用N个语法的所有乘积加上乘积来制作新的语法G：

If G1,...,GN are the context-free grammars for the N context-free languages you have, rename all the symbols in the each grammar (add a subscript just to avoid symbol name clashes) and then make a new grammar G with all the productions from the N grammars, plus the production:

S-> S1 | S2 | ... | SN

S -> S1 | S2 | ... | SN

此语法生成联合语言，并且没有上下文。

This grammar generates the union language, and it is context-free.

这篇关于无上下文语言联盟的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！