如何实现epsilon转换？

Question

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

Answer 1

你正在寻找的答案是here 它说的是，任何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转换中生成所有可能的结果以涵盖模糊性。我认为如何以计算的方式表达歧义，这是非常有趣的。

来源例如2 here