解释 TOC 中 CFL 的 Kleene Star 下的关闭？
如果L是CFL，则L*是CFL。这里CFL指的是上下文无关语言。
脚步
设L的CFG有非终结符S,A,B,C,。...
将非终结符从S更改为S1。
我们为L*创建一个新的CFG，如下所示-
包括所有非终结符S1,A,B,C,。..来自L的CFG。
包括L的CFG的所有作品。
添加新的非终结符S和新产生式
S→S1S|∧
我们可以重复上次生产
S→S1S→S1S1S→S1S1S1S→S1S1S1S1S→S1S1S1S1∧→S1S1S1S1
请注意，L*中的任何单词都可以由新的CFG生成。
我们必须证明新CFG生成的任何单词都在L*中，
此外，请确保不同S1之间没有交互作用。
例子
L的CFG如下-
S → PaQ | QQ | ∧ P → SaS | bQb | ab Q → SS | ba Convert CFG for L: S1 → PaQ | QQ | ∧ P → S1aS1 | bQb | ab Q → S1S1 | ba
L*的新CFG如下-
S → S1S | ∧ S1 → PaQ | QQ | ∧ P → S1aS1 | bQb | ab Q → S1S1 | ba