資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究解釋上下文無關語言在並集運算下的閉包？
如果 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
更新於: 2021年6月16日
652 次檢視
廣告