將正確的遞歸語法翻譯成喬姆斯基正常形式

Question

我正在嘗試做一個練習，我將語法翻譯成喬姆斯基正常形式。我明白在正常情況下如何做到這一點，但這次我正在使用的語法是正確的遞歸。 （從技術上講，語法是上一個問題的答案，所以我可能只是錯了伽馬。）

我想我可以通過使用固定的規則序列代替ε規則來做到這一點，但我想確保我不是走錯了方向。用一個例子來解釋更容易：

對於產生n'a's的語法，其中n大於0和3的倍數:(不要擔心，這與我實際練習的語法完全不同）

S-> Aaaa 
A-> Aaaa 
A-> ε 

會正確的翻譯是：

S0-> S 
S-> A'B 
A'-> AA' 
A-> A'B 
B-> B'C 
A'-> a 
B'-> a 
C-> a 

Answer 1

雖然你的語法是正確的遞歸，您可以執行喬姆斯基範式轉變，就像任何其他（非遞歸右）文法。只需按照你的書，這可能包括兩個步驟概述的算法：（1）更換終端所有出現的一個通過規則A - >一個，其中一個不規則集中出現; （2）通過包含新變量的長度爲2的規則來變換所有規則，其中len（w）> 2。

爲了您一個規則，那麼，構建獲得終端的規則，說的K - >一個，並更換終端所有出現一個：

A -> AKKK 

然後把語法進入CNF

A -> AA' 
A' -> KA'' 
A'' -> KK