如何找到這個語法CNF

Question

我需要幫助解決語法CNF：S->SS|(S)|e

我看着步驟就前往CNF但我的問題是如何解決它與（語法）怎麼把語法變得非法

任何人。

Answer 1

這應該是在CNF的等效語法：

S -> SS|CB|e 
A -> (
B ->) 
C -> AS 

編輯：爲語法S -> SS|(S)|ε在CNF 第一個步驟是去除ε（簡化以除去多餘的規則）

S -> SS|S|(S)|() 

下一步是刪除單位生產。在這種情況下，您只有一條生產規則，因此我們可以放棄UP，因爲它只會添加冗餘規則。

S -> SS|(S)|() 

最後一步是添加產生式規則遵守CNF（單個終端或正好2變量）：

S -> SS|CB|AB 
A -> (
B ->) 
C -> AS 

記住CNF去除「ε」從由語法產生的語言。否則語法相當於原文。