如果 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