数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究Explain the Closure Under Kleene Star of CFL in TOC?
如果 L 是一种 CFL，则 L*是一种 CFL。这里的 CFL 指无上下文语言。
步骤
让 CFG 表示 L 有非终结符 S、A、B、C、. . .。
将非终结符从 S 更改为 S1。
我们为 L*创建了一个新的 CFG，如下所示 −
从 L 的 CFG 中包含所有非终结符 S1、A、B、C、. . .。
包含 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
更新于：16-6 月 2021
546 次浏览
广告