資料結構
網路
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 次瀏覽
廣告