喬姆斯基規範格式轉換算法

當我們想要將語法轉換爲喬姆斯基規範形式時，爲什麼我們要添加一個新的起始狀態S0 - > S？如果我們不這樣做會出什麼問題？喬姆斯基規範格式轉換算法

起初我以爲這是因爲epsilon規則。但是我們不會從啓動變量中刪除一個epsilon規則。那麼，添加S0 - > S的好處是什麼？

謝謝

根據空字符串是否在語言中，您可能有規則$ S - > \ epsilon $（或$ S_0 - > \ epsilon $）。這可以刪除任意數量的符號$ S $，如果這些符號出現在規則的右側。因爲我們不想讓開始符號再次出現，所以我們引入一個新符號。

通過這種方式，我們可以在規則A - > BC的每個應用程序中再多使用一個符號。

2016-06-03 15:24:16

我不認爲這會造成問題，因爲即使您有規則S ---> \ epsilon，也不會刪除它，因爲只有在其變量不是開始符號時才刪除epsilon規則。 –

問題是，使用CNF，你知道長度爲n的字符串的派生具有n-1個規則A-> BC，而n個形式爲A-> a。語法S-> A，A-> AS，A-> a，S-> eps可以以任意多種方式推導出字符串a。這不是你想要的**正常形式**。 –

我想我有一些解釋。

： - 如果語法是這樣的第一> S1，我們將有

S --> S1 
S1 --> S 
S1 --> a

然後，在去除「單元規則」，因爲我們不考慮任何特定順序的步驟，我們可能會移除小號

S1 --> S1 
S1 --> a

並且啓動變量被完全刪除。

2016-06-01 02:41:59

回答