微客导航 » 文章资讯 » 解释联合操作下的上下文无关语言闭包？

解释联合操作下的上下文无关语言闭包？

2023-06-07 15:53:03 371

如果L1和L2是CFL，则它们的联合L1+L2是CFL。这里CFL指的是上下文无关语言。

L1CFL意味着L1有一个CFG，让它是生成它的CFG1。

假设CFG1中的非终结符是S、A、B、C、...。...

将CFG1中的非终结符更改为S1、A1、B1、C1、......

请勿更改CFG1中的端子。

L2CFL意味着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