資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究為給定的上下文無關文法生成喬姆斯基正規化 (CNF)
問題
為以下上下文無關文法 (CFG) 生成喬姆斯基正規化 (CNF)。
S->aAa|bBb|e
A->C|a
B->C|b
C->CDE|e
D->A|B|ab
解答
按照以下步驟生成給定 CFG 的 CNF
步驟 1 - 消除空產生式 (∧-productions)
我們可以刪除或消除空產生式，並處理重複。
S --> aAa | bBb | ∧
A --> a | ∧
B --> b | ∧
D --> A | B | ab
步驟 2 - 消除上述文法中的單元產生式
消除右部只有一個符號的產生式
S --> aDa | bDb
D --> a | b | ab
步驟 3 - 消除無用符號
E 是給定文法中的無用符號，因為它在右部沒有匯出。
S --> aDa | bDb
D --> a | b | ab
步驟 4 - 喬姆斯基正規化 (CNF)
獲取其體是終結符和變數的混合，或由多個終結符組成的產生式
將產生式分解成如下所示的簡短形式
S --> XYX | ZYZ
S --> XP | ZQ
P --> YX
Q --> YZ
X --> a
Y --> a | b | ab
Z --> b
更新於：2021年6月12日
946 次瀏覽
廣告