喬姆斯基正常形式消除epsilon轉換

Question

我正在將CFG轉換爲喬姆斯基正常形式，但我有一些困難。

我有這樣的CFG

A-> BAB|B|epsilon B -> 00|epsilon

好，我添加一個新的開始狀態

S -> A A-> BAB|B|epsilon B -> 00|epsilon

然後，我不得不刪除小量的轉變，所以我開始爲B

S -> A A-> BAB|B|AB|BA|A|epsilon B -> 00

然後我如何從A中刪除epsilon？開始時可以有一個epsilon？我該如何轉換A-> A？

Answer 1

您不能將此語法轉換爲沒有ε的語法，因此它不能用喬姆斯基標準形式書寫。這是因爲所有的產品都可以減少到ε，因此ε是語言中的有效句子。