context-free-grammar - 如何使用乔姆斯基范式的第一步

Question

我对何时使用 CNF 转换的第一步感到困惑。

第一步：ensure s does not appear on rhs, add new S0 if necessary and copy all rules of S

我不清楚上述声明的含义。我不知道何时创建 S0。有些 CFG 不以 S0 开头，有些则以 S0 开头。

兄弟们在这里有点帮助。

Answer 1

关键是要避免开始符号出现在 rhs 上，即作为产生式的结果。因此，您创建了一个独特的符号，它成为唯一的起始符号。

您认为 CFG 的哪些示例不正确？它们可能不是这样开头的，但它们开头的符号不应该作为生产的结果出现。