3

タイトルが示すように、NFAからDFAへの変換のコーディングを誰かに手伝ってもらいたいです。擬似コードのみが必要です。Googleを使用して検索してみましたが、ソースコード全体も見つかりましたが、変換のための形式手法（画像ではなく、書面による）を提供するのに役立つリソースはほとんどありませんでした。これは宿題の問題で、私はすでに期日を過ぎているので、ここで利他主義が本当に必要です。

ありがとう。

4

1 に答える 1

8

私はこのテーマに関する記事を書きました。

サブセット構築によるNFAからDFAへの変換

変換の実行方法に関する擬似コードも含まれています。

基本的に、アルゴリズムは、NFAの開始状態から始まります。

Perform closure on the current state set
For each input symbol do the GOTO operation on the closure set.
   If the state set you get from the GOTO is not empty
      Do a closure of the state set.
      If it is a new set of states:
         add a transition between the state sets on the input 
         repeat the entire operation on this new set
      Else
         add a transition between the state sets on the input

セットまたはトランジションが追加されなくなるまでこれを行います。CLOSURE説明するのは難しいアルゴリズムですが、2つの基本的な操作があり、実行されている場合はそれほど難しくありませんGOTO。

于 2012-08-14T14:55:12.837 に答える