java - 如何实现 epsilon 转换？

Question

我目前正在尝试使用 epsilon 转换实现 CYK 。提供的算法如何处理 epsilon 转换？如果不是，您将如何实施它？（我正在使用 Java）

Answer 1

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

示例 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这里