找到每种语言的短语结构语法。G)包含不相等数目的0和1的所有字符串的集合。
首先，我们可以通过认识到0和1的不相等数量意味着有更多的0或更多的1来解决这个问题。这表明一种语法可以用两种方式:
S := R | T
R := (more 0s than 1s)
T := (more 1s than 0s)
R和T的表达式应该非常相似，只是符号颠倒了。
我们如何保证0多于1，反之亦然?我们可以插入至少一个或者多个0或1然后填充0和1的数目相同的字符串:
R := E0R | E0E
T := E1R | E1E
这些将产生中间形式，如E0E0E0E, E1E等。这里的想法是，任何0多于1(或1多于0)的字符串都可以写成k个0(或1)，由相等数量的0和1的子字符串分隔。这似乎是合理的，但确实需要证明(留作练习)。
剩下的就是给出具有相同数量的0和1的字符串的结果:
E := EE | 0E1 | 1E0 | e
可以使用归纳。基本情况可以包括最短的字符串e, 01和10，我们可以看到这很容易工作。对于归纳步骤，只需注意必须有一个最长的前缀，其中0和1的数字相等，并且它的第一个和最后一个符号必须不同;如果它是整个字符串，那么它可以通过产生0E1或1E0从长度小于2的字符串中得到，否则，它可以通过在两个较短的字符串上产生EE得到(前缀和后缀较短，由归纳假设覆盖)。
整个语法看起来像:
S := R | T
R := E0R | E0E
T := E1R | E1E
E := EE | 0E1 | 1E0 | e
这是该语言的最短、最有效、最明确等语法吗?谁知道呢，但应该管用!