java - イプシロン遷移を実装するには?

Question

現在、イプシロン遷移でCYK を実装しようとしています。提供されたアルゴリズムはイプシロン遷移をどのように処理しますか? そうでない場合、どのように実装しますか？(私は Java を使用しています)

Answer 1

あなたが探している答えはここにあります 。それは、任意のイプシロン遷移をより少ない単純な遷移で表すことができるということです。イプシロン遷移はあいまいです。このあいまいさを計算でカバーするには、特定の遷移からすべての可能な結果を​​生成する必要があります。

例 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 は ε (イプシロン) 遷移を表します

あいまいさをカバーするために、イプシロン遷移からすべての可能な結果を​​生成する必要があることがわかります。曖昧さを計算で表現できるところが面白いと思います。

例 2 のソースはこちら