如何实现epsilon过渡？

Question

我目前正在尝试使用epsilon transition进行implement CYK。提供的算法是如何处理epsilon转换的？如果没有，你将如何着手实现它？(我使用的是Java)

Answer 1

你正在寻找的答案是here，它说的是任何ε跃迁都可以表示为更少的简单跃迁。ε转换是模棱两可的。为了在计算上覆盖这种模糊性，您需要从给定的转换生成所有可能的结果。

示例1：

A -> aA | e

是

A-> a
A-> aA

示例2：

B->A b A
A->a | e

是

B -> z | A z | z A | A z A
A -> a

其中e代表ε(epsilon)转换

您可以看到，您必须从epsilon转换中生成所有可能的结果，以便覆盖模糊性。我认为如何通过计算来表达歧义是很有趣的。

示例2 here的源代码