如果 L1 和 L2 是 CFL，则它们的联合 L1 + L2 是 CFL。这里 CFL 指的是上下文无关语言。
L1 CFL 意味着 L1 有一个 CFG，让它是生成它的 CFG1。
假设 CFG1 中的非终结符是 S、A、B、C、...。. ..
将 CFG1 中的非终结符更改为 S1、A1、B1、C1、... . ..
请勿更改 CFG1 中的端子。
L2 CFL 意味着 L2 有一个 CFG，让它是生成它的 CFG2。
假设 CFG2 中的非终结符是 S、A、B、C、...。. ..
将 CFG2 中的非终结符更改为 S2、A2、B2、C2、... . ..
请勿更改 CFG2 中的端子。
现在 CFG1 和 CFG2 有不相交的非终结符集。
我们为 L1 + L2 创建一个 CFG，如下所示 -
包括所有非终结符 S1, A1, B1, C1, . . . 和 S2、A2、B2、C2、... . ..
包括CFG1和CFG2的所有作品。
创建一个新的非终结符 S 和一个产生式。
S → S1 | S2
例子
CFG1 for L1 S → S | Aa | Bb | ∧ A → Sa | bB | ab B → S | a CFG2 for L2 S → aS | aA | Bb | ∧ A → aS |bB| ab B → Ba | b
要为 L1 + L2 构建 CFG，请按照以下步骤操作 -
转换 CFG1 如下 -
S1 → S1| A1a | B1b | ∧ A1 → S1a | bB1 | ab B1 → S1 | a
如下变换CFG2
S2 → aS2 | aA2 | B2b | ∧ A2 → aS2 |bB2| ab B2 → B2a | b
为 L1 + L2 构建 CFG，如下所示 -
S → S1 | S2 S1 → S1| A1a | B1b | ∧ A1 → S1a | bB1 | ab B1 → S1 | a S2 → aS2 | aA2 | B2b | ∧ A2 → aS2 |bB2| ab B2 → B2a | b