上下文無關語法

Question

我有這個問題，我需要將以下CFG轉換爲CNF中的CFG。

S-> ABa 
A-> aab 
B-> Ac 

我知道的步驟如下。

1. 刪除小量的過渡 - 完成
2. 刪除單元製作
3. 轉換到CNF由：
   1. 引入一個新的非終端每個術語
   2. 與新的替換生產規則端子非終端
   3. 引入新的非終端來減少每個產品右側的長度

我有點困惑，我會如何處理上述問題。大多數情況下，我對第2步和單元製作感到困惑。如果我能得到一些幫助，或者鏈接到一個很有幫助的好教程。

Answer 1

自從我做了那些事以來，已經有好幾年了。這paper [PDF]幫了我很多。

Answer 2

我知道的步驟如下。

1. 刪除小量的過渡 - 完成
2. 刪除單元製作
3. 轉換爲CNF由： 1.introduce一個新的非終端每個術語
   1. 替換與作品規則端子新的非終端
   2. 引入新的非終端來減少每個生產的右側的長度

步驟1和2是已經完成。所以我們只需要擔心步驟3

開始語法：

S-> ABa 
A-> aab 
B-> Ac 

1. 引入新的非終端每個術語。

   S -> ABa 
   A -> aab 
   B -> Ac 
   C -> a 
   D -> b 
   E -> c 
   

2. 用新的非終結符替換生產規則中的終端。

   S -> ABC 
   A -> CCD 
   B -> AE 
   C -> a 
   D -> b 
   E -> c 
   

3. 引進新的非終結點，以減少每個生產的右側的長度。

   S -> AF 
   A -> CG 
   B -> AE 
   C -> a 
   D -> b 
   E -> c 
   F -> BC 
   G -> CD 
   

Answer 3

S->ABa 
C.N.F. is : 
M->AB 
Z->a 
S->MZ 

A->aab 
C.N.F. is : 
X->aa 
Y->b 
A->XY 

B->Ac 
C.N.F. is: 
K->a 
B->AK