上下文无关文法不等数目的符号

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 | ε