如何實現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