问上下文无关语法-其中1的数量比0的数量多1的字符串的集合

EN

基于模板定义的答案，你可以在https://math.stackexchange.com/questions/2207708/context-free-grammar-for-language-a-b-where-the-number-of-as-the-number上找到这样的语法

所以基本上最终的语法应该是：

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

作为提示，如果你有一个字符串恰好比0多1，那么有一种方法可以将它写成w1x，其中w和x的0和1的数量完全相同。如果您可以找到一个CFG，它生成具有相同数量的0和1的字符串，并且开始符号为X，那么您可以添加一个开始符号S和生产符号S→X1X，您就应该可以开始了。

考虑一下：

S → T1T

T → 10T | 01T | 0T1 | 1T0 | ε

然后从单个1 (S → T1T)开始，并始终为每个T应用程序添加相同数量的0's和1's (以任何可能的排列方式)。