資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學設計一個在CNF中生成E的無歧義CFG。
問題
定義語言E={aibj|i ≠ j且i ≠ 2j}，並設計一個在喬姆斯基正規化(CNF)中生成E的無歧義上下文無關文法(CFG)。
解答
給定語言的無歧義CFG如下：
S->AC|CB
A->aA|a
B->Bb|b
C->aCb|aaCb|ε
現在，將此CFG轉換為CNF。您可以按照以下步驟成功轉換。
步驟1
首先新增一個新的起始符號S0
S0->S
S->AC|CB
A->aA|a
B->Bb|b
C->aCb|aaCb|ε
步驟2
接下來，消除除起始符號之外產生式中的ε符號。
C->ε是一個空產生式
消除空產生式後，新的產生式如下：
S0->S
S->AC|CB
A->aA|a
B->Bb|b
C->aCb|aaCb|ab|aab
步驟3
現在移除單元產生式（如果存在）。
S0->S是一個單元產生式
用S的產生式替換S
S0->AC|CB
S->AC|CB
A->aA|a
B->Bb|b
C->aCb|aaCb|ab|aab
步驟4
沒有無用的產生式需要移除。
步驟5
現在檢查不符合CNF的產生式，如果不符合，則將其轉換為CNF。
如果產生式規則滿足以下條件之一，則上下文無關文法處於CNF中：
- 如果存在起始符號生成ε。例如：A->ε
- 如果一個非終結符生成兩個非終結符。例如：S->AB
- 如果一個非終結符生成一個終結符。例如：S->a
現在，我們的文法不遵循以下規則：
A->aA
B->Bb
C->aCb|aaCb
將此產生式轉換為CNF，如下所示：
A->XA
B->BY
C->XCY|XXCY
X->a
Y->b
仍然C->XCY|XXCY違反規則，因為右邊有超過兩個符號。因此，讓我們分解產生式
C->XCY
C->RY
R->XC
以及
C->XXCY
C->LM
L->XX
M->CY
生成E的CNF如下：
S0->AC|CB
S->AC|CB
A->XA|a
B->BY|b
C->RY
C->LM
X->a
Y->b
R->XC
L->XX
M->CY
現在，每個產生式要麼生成一個終結符，要麼生成兩個非終結符。
203 次瀏覽
