context-free-grammar - 上下文无关语法的推导

Question

最终，我想将以下 CFG 转换为乔姆斯基范式：

S→aSbS∣bSaS∣ε

但是，我不确定我是否正确地进行了推导——这就是我所拥有的：

用终端替换非终端

S→aabb

S→ε

有人可以告诉我这是否正确/在正确的轨道上吗？

谢谢你。

Answer 1

正如@Ashalynd 所写，您应该阅读更多关于乔姆斯基范式的内容：

乔姆斯基范式意味着没有 epsilon，也没有复杂的陈述。

您拥有的语法包含一个 ε，因此永远不能转换为 CNF，因为 ε 是由生成的语言中的有效句子S.