java - NFA の状態遷移表を作成するには?

Question

2 次元配列を使用して、DFA の遷移テーブルを作成しました。たとえば、10 個の状態と 2 つの遷移を保存するには、次のようにします。

transition = new int[10][2]; 

ただし、NFA については、移行の可能性がたくさんあります。以下の例では、値 0 が来ているときに S2 または S3 に移動できます。したがって、Java のどの構造を使用すればよいかわかりません。

私は 1 日の NFA のテーブルを作成しようとしていますが、私が行ったすべての方法は非常に複雑です。たとえば、Hashtable、Set などを使用します。

コードの例やアイデアを教えてください。

Answer 1

状態ごとにビットセットを使用し、|遷移ごとにビット単位の or を使用します。たとえば、S1 = 001、S2 = 010、S3 = 100 です。S3 = 110 であるため、{S2, S3} 遷移は 110 です。これにより、int で表される場合は最大 32 の状態、long で表される場合は 64 の状態が可能になります。より多くの状態 (または使いやすいビット操作) については、BitSetを使用します。

ちなみに、どの NFA も DFA に変換できます。ここで何をしようとしているかに応じて、別のオプションになります。