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

Question

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

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

Answer 1

如果您使用常规算法将语法转换为Chomsky范式，则会清楚地知道语法的起始符号是否能够派生空字符串。这是因为您将迭代地删除所有生成空字符串的生成，直到找到（或找不到）必要的生成为止。