parsing - 为特定语言定义上下文无关文法

Question

我有一种语言，其中语言中的每个字符串都有偶数的 0 和 1（例如，0101、1010、1100、0011、10 都在语言中）。我希望定义一个描述这种语言的上下文无关语法。在定义了上下文无关文法之后，我想正式证明这个上下文无关文法描述了这种语言。

我想出了上下文无关的语法产生规则：

    S->0S1S
    S->1S0S
    S->ε

这是定义这种语言的正确上下文无关语法吗？

我有点难过证明部分。我猜我需要某种感应？

Answer 1

这个语法对我来说是正确的。

我将通过显示两个方向来证明这一点（即，如果字符串是由语法产生的，则该字符串在语言中）。

证明文法产生的所有字符串都在该语言中很容易：只需考虑文法的所有产生式输出相同数量的 1 和 0。因此，产生式的任何组合都必须产生该语言中的字符串。

要证明该语言中的所有字符串都可以由文法产生似乎比较棘手。我认为归纳可以解​​决这个问题，但没有什么明显的想法。

祝你好运