context-free-grammar - 为什么常规语言不应该有单元规则变量 -> 变量？

Question

我正在阅读有关常规语言的信息。我不明白一件事。

为什么

变量 -> 变量是不允许的？

其背后的原因是什么？

如果有这样的规则会发生什么？它变成什么样的语法？

Answer 1

什么都不会发生：任何其他规则语法，如果您添加了 A := B 形式的规则，则将继续成为常规语言的语法——当然，尽管可能不是相同的常规语言。

这些规则引入的内容类似于 NFA 中使用的 lambda/epsilon/empty 转换。这样的规则说“你可以从对应于非终结符 A 的状态转到对应于非终结符 B 的状态，而无需消耗任何新的输入符号”。像“A := xB”和“C := Dy”这样的规则分别表示“当你消耗一个 x 时你可以从 A 到 B”和“你可以通过消耗一个 C 从 D 到 C”。

形式上，我们可以证明这些产生式总是可以从其他常规语法中删除，方法是在所有 C, x 的 "C := xB" 时替换 "A := B" 使得 "C := xA" 是你的产生式语法。并且总是可以删除“A := A”。