上下文無關文法不等數目的符號

Question

我知道如何構建一個上下文無關語法，具有相同數量的兩個給定元素，即。如果我們使用{0,1}

S->SS 
S->0S1 
S->1S0 
S->ε 

不過，我在努力尋找一種方法來構建有一個元素比另一個更一定量的語法。即。始終是兩個比1更多的0。 有沒有人有任何想法如何構建這樣的語法？

Answer 1

我制定了一個很好的回答這個：

S->P0P0P 
P->PP 
P->0P1 
P->1P0 
P->ε 

它應該出現一個比0多一個0的字符串，並且可以很容易地擴展到更大的數字。

Answer 2

編輯：（校正），如下面的力量的東西至少有一個0比1的更多：

S->T0S | T0T 
T->0T1T | 1T0T | ε 

所以現在，應該不會太難，重複同樣的模式多加一個0 ...

這樣做以下語法回答問題：

S->T0S | T0T 
T->0T1T | 1T0T 
T->U0T | U0U 
U->0U1U | 1U0U | ε