context-free-grammar - 为最多两个 0 的偶数长度字构造 CFG

Question

我正在努力为 L={xE{0,1}* | 构建一个良好的 CFG，该 CFG 的长度为偶数且最多有两个 0}

所以像L={11, 10, 0011...}这样的词

我正在尝试以下尝试。

S -> E | E0A | A0E | E0E0E | 00EA | EA00

E-> 1A | e

A -> 1E

我正在运行不同的推导，它们似乎有意义，但我仍然不确定我的语法是否正确，或者是否有更好的方法来改进它？ 非常感谢，我一直在与 CFG 作斗争，我正在尝试更多练习来帮助我理解。

Answer 1

您的 CFG 似乎不正确，因为我没有看到 1001 的推导。可能还有其他问题。

我们可以从 0 和 1 偶数长度字符串的语言的 CFG 开始:

S -> 0S0 | 0S1 | 1S0 | 1S1 | e

这个语法的唯一问题是它可以产生两个很多 0。我们可以通过在每次加零的产生式之后引入新的非终结符来避免这种情况。然后，那些其他非终结符可以“记住”我们已经看到了 0，并且有效的产生式较少。所以...

S -> 0A0 | 0B1 | 1B0 | 1S1 | e
A -> 1A1 | e
B -> 0A1 | 1A0 | 1B1 | e

在此语法中，S 表示到目前为止尚未引入零； A 引入了两个允许的零； B 只介绍了一个。