資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學解釋上下文無關語言在連線運算下的封閉性？
這裡 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 次瀏覽
廣告