解释上下文无关语言在连接运算下的封闭性？

这里 CFL 指的是上下文无关语言。现在，让我们了解一下在连接运算下的封闭性。

连接运算下的封闭性

如果 L1 和 L2 是 CFL，则 L1L2 是 CFL。

按照以下步骤操作：

L1 CFL 意味着 L1 有一个 CFG1 生成它。

  • 假设 CFG1 中的非终结符是 S、A、B、C……

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

  • 不要更改 CFG1 中的终结符。

L2 CFL 意味着 L2 有一个 CFG2 生成它。

  • 假设 CFG2 中的非终结符是 S、A、B、C……

  • 将 CFG2 中的非终结符更改为 S2、A2、B2、C2……

  • 不要更改 CFG2 中的终结符。

现在 CFG1 和 CFG2 具有不相交的非终结符集合。

然后我们为 L1L2 创建 CFG，如下所示：

  • 包含所有非终结符 S1、A1、B1、C1……和 S2、A2、B2、C2……

  • 包含 CFG1 和 CFG2 的所有产生式。

创建一个新的非终结符 S 和一个产生式

S → S1S2

示例

CFG1 for L1
S → SS | TaTb |FFF | ∧
T → SaS | bFb | abba
F → SSS | baab
CFG2 for L2
S → aS | aTba | FbF | ∧
T → aSa | abab
F → FabaF | bb

要为 L1L2 构造 CFG，请按照以下步骤操作：

  • 转换 CFG1

S1 → S1S1 | T1aT1b | F1F1F1 | ∧
T1 → S1aS1 | bF1b | abba
F1 → S1S1S1 | baab

  • 转换 CFG2

S2 → aS2 | aT2ba | F2bF2 | ∧
T2 → aS2a | abab
F2 → F2abaF2 | bb

  • 为 L1L2 构造 CFG：

S → S1S2
S1 → S1S1 | T1aT1b | F1F1F1 | ∧
T1 → S1aS1 | bF1b | abba
F1 → S1S1S1 | baab
S2 → aS2 | aT2ba | F2bF2 | ∧
T2 → aS2a | abab
F2 → F2abaF2 | bb

更新于：2021年6月16日

807 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告