java - Java で有限状態マシンを作成する方法

Question

FSM の一連の状態を読み取るプログラムの作成方法。入力データは、(状態入力次の状態) 形式のテキスト ファイルから取得され、最後の行は最終状態です。例えば ​​：

    s0   a   s1
    s1   a   s2 
    s2   a   s2 
    s1 

プログラムの出力は次のようになります。

a) FSM によって生成された文字列のリスト。

b) プログラムは、FSM が DFA か NDFA かを判断し、結果を出力できます。

Answer 1

コード化されたソリューションを提供するつもりはありませんが、いくつかの方向性があります。

まず第一に、FSM には開始状態と終了状態が必要なので、重要な情報が欠落しています。

文字列のリストを生成している場合、有限数の文字列を受け入れる非常に限られた FSM のサブセットを扱っている可能性があります。したがって、あらゆる可能性を試すのが妥当です。グラフのすべてのパスをたどり、終了状態に達するたびに出力します。

DFSM と NDFSM の違いを考えてみてください。入力に複数の方法がある場合、非決定論的です。したがって、グラフを作成しているときに、異なる状態への 2 つの同一の遷移を持つノードがある場合、それは非決定論的です。非決定論はシステム全体を非決定論的にするので、決定論は非決定論の完全な欠如です。

したがって、実際に表現を作成することから始めたいと思うでしょう。2つの簡単な方法が思い浮かびます。より視覚的に、グラフを作成できます。これを行う最も簡単な方法は、ノード クラスを作成してから、遷移と宛先のペアを含む各ノードのオブジェクトを作成することです。

私が FSM を表現するのに好んで使う方法は、ハッシュ マップ/辞書を使用することです。ノードとトランジションをキーとして使用し、宛先を値として使用します。これにより、ナビゲーションがかなり簡単になります。

幸運を！

編集:非決定論を決定する際に、イプシロン遷移について考えるのを忘れないでください(私がちょっとしたように.:))