删除第一个无用的制作，然后删除单位制作？
当将无上下文的语法转换为乔姆斯基正常形式时，我们首先要删除无效的产生，然后以这种精确的顺序进行单位产生，然后删除无用的生产。 我知道去除无效的产生可能会增加单位产生的升高，这就是为什么在无效产生后卸下单位的原因。 但是，我不明白，如果我们首先删除无用的生产，然后是单位会出现什么问题？
When transforming a Context-free grammar into Chomsky Normal Form, we first remove null-productions, then unit-productions and then useless productions in this exact order.
I understand that removing null-productions could give raise to unit-productions, that’s why unit is removed after null-productions.
I do however not understand what could go wrong if we first removed useless-productions and then unit?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果您删除了单位生产
a→b，那是引用b的唯一位置，则b将变得无法实现消除单位生产的结果，需要及其生产。该条件要求
b是非回报的（因为递归非末端是指自身，并且大概不是单位生产），并且在b的生产中引用的任何非末端仍将被引用，因为a被吸收到了生产中。如果语法没有允许
a→* a的单元制作周期新的单位生产。这使得在您消除单位生产时可以去除新的非终端。但是我认为，该教科书算法可能不这样做，这大概是为什么您的教科书希望您在语法转换为CNF后删除无用的作品的原因。 （当然，没有什么可以阻止语法的单位制作周期。这种语法是模棱两可的，因此很难在解析器中使用，但是这种练习并不要求语法在解析器中有用。同样，这可以以不需要推迟可及性分析的方式来处理，但是教科书算法可能没有。
If you remove the unit production
A → Band that was the only place in the grammar whereBwas referenced, thenBwill become unreachable as a result of unit-production elimination, and will need to be removed along with its productions.That condition requires
Bto be non-recursive (since a recursive non-terminal refers to itself, and presumably not with a unit production), and any non-terminals referenced in the productions ofBwill still be referenced, having been absorbed into productions forA.If the grammar does not have a cycle of unit productions allowing
A →* A, then unit productions can be topologically sorted and removed in reverse topological order, which guarantees that the unit production elimination doesn't create a new unit production. That makes it possible to remove newly-unreachable non-terminals as you do the unit-production elimination. But I think that textbook algorithms probably don't do that, which is presumably why your textbook wants you to remove useless productions after the grammar has been converted to CNF. (And, of course, there's nothing stopping a grammar from having a cycle of unit productions. Such a grammar would be ambiguous, making it difficult to use in a parser, but this exercise doesn't require that the grammar be useful in a parser.)Similarly, if the only production for a non-terminal is an ε-production, then that non-terminal will end up with no productions after null-productions are removed (and it will also be unreachable). Again, that could be handled in a way which doesn't require deferring reachability analysis, but the textbook algorithm probably doesn't do that.