grammar - 乔姆斯基范式正确性

Question

我有这些作品：

S->aSb
S-> eps      (eps=empty string)

我应该应用乔姆斯基范式

我的推理：

1）消除eps规则给定：

S->aSb
S-> eps

我得到：

S->ab

S->aSb

2）消除单位规则

没有了

3) 删除无用符号

我得到：

S->ab

因此，应用 CNF（乔姆斯基范式）后的给定语法变为：

S->ab

我对吗？

Answer 1

你在这里所拥有的并不完全相同。请注意，空字符串不再是您的语言的一部分，字符串 aabb、aaabbb 等也不再是您的语言的一部分。

检查消除无用规则的步骤。第二条规则真的没用吗？

另外，您确定可以消除 epsilon 生产吗？