構建一個上下文無關文法喬姆斯基範式語言

Question

我試圖構造一個CFG喬姆斯基範式以儘可能少的生產儘可能接受含有唯一的字符串^ 21的語言。

我明白，我可以轉換

的S - > AAAAAAAAAAAAAAAAAAAAA A - >一個

但沒有任何其他的方式來縮短該語言然後將其轉換成Chomsky範式？

Answer 1

我們可以很容易地表明，我們至少需要六個符號承認我們可以在最好的雙生成的字符串與每個生產長度希望產生CNF一個CFG此語言，我們必須用2^0開始：

A_21 := ... 
A_16 := A_16 A_16 
A_8 := A_4 A_4 
A_4 := A_2 A_2 
A_2 := A_1 A_1 
A_1 := a 

然後我們可以顯示CNF中沒有語法，其中有六個生成我們目標語言的作品。我們從底層開始構建語法來開始論證。

1. 我們必須有A_1 := a才能得到任何字符串。
2. 我們必須A_2 := A_1 A_1得到任何字符串，長度大於1
3. 我們現在可以產生兩種A_3或跳過這一點，產生A_4，或兩者兼而有之。我們在下面分別考慮這些情況。

案例1：A_3

1. 我們增加A_3 := A_2 A_1。
2. 我們已經有3個生產，並且知道我們需要的形式A_21 := X Y之一。所以我們最多可以添加兩個。即使我們添加了現在可能的最大作品 - A_6和A_12 - 我們無法根據需要生產A_21（我們最多可以生產A_18 := A_6 A_12。因此，添加A_3無法讓我們在六種作品中生成我們的語言。

案例2：。A_4

1. 我們增加A_4 := A_2 A_2
2. 我們已經有3個生產，並且知道我們需要的形式A_21 := X Y之一，所以我們最多可以添加兩個我們OPTIO ns目前是A_5,A_6和A_8。 A_5和A_6將因爲我們針對上述案例1陳述的相同原因而失敗。然而，A_8並不因此失敗，因此我們添加A_8 := A_4 A_4。
3. 我們現在只有一個生產需要它要麼A_20, A_19, A_17或A_13。我們無法使用我們現有的作品製作任何這些作品。

我們就此排除了語法與6所製作。如果您嘗試使用上述推理來查找7個作品的語法，您會發現幾個。由於我們知道CNF中有7種語法的文法，而6種都沒有，所以你就完成了。以下是7種生產語法中的一些：

S := A_18 A_3 
A_18 := A_9 A_9 
A_9 := A_6 A_3 
A_6 := A_3 A_3 
A_3 := A_2 A_1 
A_2 := A_1 A_1 
A_1 := a 

S := A_17 A_4 
A_17 := A_9 A_8 
A_9 := A_8 A_1 
A_8 := A_4 A_4 
A_4 := A_2 A_2 
A_2 := A_1 A_1 
A_1 := a 

S := A_16 A_5 
A_16 := A_8 A_8 
A_8 := A_4 A_4 
A_5 := A_4 A_1 
A_4 := A_2 A_2 
A_2 := A_1 A_1 
A_1 := a 

S := A_15 A_6 
A_15 := A_9 A_6 
A_9 := A_6 A_3 
A_6 := A_3 A_3 
A_3 := A_2 A_1 
A_2 := A_1 A_1 
A_1 := a 

S := A_14 A_7 
A_14 := A_7 A_7 
A_7 := A_4 A_3 
A_4 := A_3 A_1 
A_3 := A_2 A_1 
A_2 := A_1 A_1 
A_1 := a 

S := A_13 A_8 
A_13 := A_8 A_5 
A_8 := A_5 A_3 
A_5 := A_3 A_2 
A_3 := A_2 A_1 
A_2 := A_1 A_1 
A_1 := a 

S := A_12 A_9 
A_12 := A_9 A_3 
A_9 := A_6 A_3 
A_6 := A_3 A_3 
A_3 := A_2 A_1 
A_2 := A_1 A_1 
A_1 := a 

S := A_11 A_10 
A_11 := A_10 A_1 
A_10 := A_8 A_2 
A_8 := A_4 A_4 
A_4 := A_2 A_2 
A_2 := A_1 A_1 
A_1 := a 

還有很多。最難的部分是顯示沒有任何6個作品。