algorithm - 创建一个算法来确定上下文无关语法是否可以生成空词（ε）

Question

我正在尝试创建一个算法来决定以下可判定问题：给定 CFG H，H ⇒*ε。也就是说，H 可以在任意数量的步骤中生成空词。该算法必须是可判定的，这意味着它总是正确地停止所有输入。

我已经研究这个问题很长一段时间了，甚至不知道如何开始或创建这个算法的步骤。我不是在寻找完整的答案，我只需要朝着正确的方向前进

标签： algorithmcontext-free-grammar

Answer 1

如果您使用正常算法将此语法转换为乔姆斯基范式，那么您的语法的开始符号是否能够导出空字符串将会变得很清楚。这是因为您将迭代地删除所有生成空字符串的产生式，直到找到（或未能找到）必要的产生式。