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

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 的字符串，并且可以很容易地扩展到更大的数字。