当我们要将语法转换为乔姆斯基范式时，为什么要添加新的起始状态 S0 -> S？如果我们不这样做，会出现什么问题？
起初我认为这是因为 epsilon 规则。但是我们不会从 start 变量中删除 epsilon 规则。那么，添加 S0 -> S 有什么好处呢？
谢谢
问问题
389 次
2 回答
1
根据空字符串是否使用语言，您可能具有规则 $S --> \epsilon$（或 $S_0 --> \epsilon$）。如果这些符号可能出现在规则的右侧，这可能会删除任意数量的符号 $S$。因为我们不希望开始符号再次出现，所以我们引入一个新符号。
这样，我们每次应用规则 A -> BC 都会得到一个符号。
于 2016-06-03T15:24:16.200 回答
0
我想我有一些解释。如果语法是这样的：
S --> S1
S1 --> S
S1 --> a
然后，在删除“单元规则”的步骤中，因为我们不考虑任何特定的顺序，我们可能会先删除 S --> S1 ，我们将有：
S1 --> S1
S1 --> a
并且 start 变量被完全删除。
于 2016-06-01T02:41:59.187 回答