我有一种语言，语言中的每个字符串的偶数为0，如1（例如，0101,1010,1100,1211,10都在语言中） . 我希望定义一个描述这种语言的无上下文语法 . 在定义了无上下文语法之后，我想正式证明这种无上下文语法描述了这种语言 .
我想出了无上下文语法生成规则：
S->0S1S S->1S0S S->ε
这是正确的上下文无关语法来定义这种语言吗？
我有点难过证明部分 . 我猜我需要某种感应？
这个语法对我来说是正确的 .
我会通过显示两个方向来证明它（即如果字符串由语法产生，则字符串在语言中） .
证明语法产生的所有字符串都在语言中很简单：只需考虑语法的所有产生输出相同数量的1和0 . 因此，任何产品组合都必须在语言中产生一个字符串 .
要证明语法中的所有字符串都可以通过语法生成，这似乎更棘手 . 我认为归纳可以解决这个问题，但没有任何明显的想法 .
祝好运
1 回答
这个语法对我来说是正确的 .
我会通过显示两个方向来证明它（即如果字符串由语法产生，则字符串在语言中） .
证明语法产生的所有字符串都在语言中很简单：只需考虑语法的所有产生输出相同数量的1和0 . 因此，任何产品组合都必须在语言中产生一个字符串 .
要证明语法中的所有字符串都可以通过语法生成，这似乎更棘手 . 我认为归纳可以解决这个问题，但没有任何明显的想法 .
祝好运