乔姆斯基范式转换算法

Question

为什么我们要将文法转换为乔姆斯基范式时要添加一个新的起始状态S0 -> S？如果我们不这样做会出什么问题？

起初我以为是因为epsilon规则。但是我们不会从 start 变量中删除 epsilon 规则。那么，添加 S0 -> S 有什么好处？

谢谢

Answer 1

我想我有一些解释。如果语法是这样的：

S --> S1
S1 --> S
S1 --> a

然后，在删除 "unit rules" 的步骤中，由于我们不考虑任何特定顺序，我们可能会先删除 S --> S1 ，我们将有：

S1 --> S1
S1 --> a

并且开始变量被完全删除。

Answer 2

根据空字符串是否使用您可能具有规则 $S --> \epsilon$（或 $S_0 --> \epsilon$）的语言。这可以删除任意数量的符号 $S$ 如果这些符号可以出现在规则的右侧。因为我们不希望开始符号再次出现，所以我们引入一个新的。

这样，每次应用规则 A -> BC 时，我们都会多获得一个符号。