特定語言的語境語法

Question

我無法理解簡單的問題。我已經表明語法以下 詞語

一個）(ab)^2i c, i>=1

對於i = 1 ababc對於i = 2 ababababc

S -> abA 
    A -> ab | abc | c 

b）中a^(m-1) b^(m+1) a^n b^n, m>=1 n>=1

對於i = 1 bbab對於i = 2 abbbaabb

S -> AbbAaAb 
    A -> ba | ab | a 

有人可以檢查這些練習並給我反饋。我究竟做錯了什麼？

Answer 1

第一個將產生(ab)^i，只是想和你的ab雙文字偶數，所以你必須把它定義爲

S -> ababA 
A -> ababA | c 

您也可以在右側使用A，在第二個規則，因爲你的規則將創造最大長度的5

第二個

S -> AbbB 
A -> aAb | epsilon (empty string) 
B -> aAb 

一個詞來形容的第一部分字，你總是需要bb在右側。您從中產生a^n b^n。

對於這個詞的第二部分，我們重用非終結A，但我們要確保有至少一個ab在字的一部分 - 這就是爲什麼B。