context-free-grammar - 不等数量符号的上下文无关语法

Question

我知道如何构造一个具有相同数量的两个给定元素的上下文无关语法，即。如果我们使用 {0,1}

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

然而，我正在努力寻找一种方法来构建一种语法，该语法具有给定数量的一个元素而不是另一个元素。IE。始终比 1 多两个 0。有人对如何构建这样的语法有任何想法吗？

Answer 1

编辑：（更正）类似以下的力量至少有一个 0 比 1 多：

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

所以现在，通过重复相同的模式再添加一个 0 应该不会太难......

这样做下面的语法回答了这个问题：

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

Answer 2

我想出了一个很好的答案：

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

它应该提供一个比 1 多两个 0 的字符串，并且可以很容易地扩展到更大的数字。