JavaのNFAシミュレーション

JavaでNFAをシミュレートする割り当てが与えられました。今、私がNFAをシミュレートする必要がある次の正規表現は、JavaのNFAシミュレーション

ab*((b|d)|c*)

私はあまりにも多くの電子シンボルがあると思います。私はちょうど次のイメージが正しいかどうか疑問に思っていた。

NFA

2011-11-29 unleashed

ノード10,11,12,13はおそらく2つのノードに集約されますか？ –

それは私が当初は何だったのですか？しかし、講師は、上記のスタイルを繰り返し使用し、Thompsonの構造を使ってNFAを作成するスタイルを望んでいます。私はちょうど2から3 eへの移行、3から4 eへの移行、4から5または4から7 eへの移行に疑念を抱いています。 – unleashed

さて、2-3を減らすことができました。 'b *'の場合は 'b'がなくなり、' e'の遷移は1-2になります。それ以外の部分は適切だと思います。最終的に最終結果は同じで、ノードは1つ少なくなります。 –

あなたのNFAのグラフが正しいです。これは正規表現ab*((b|d)|c*)と一致します。しかし、それははるかに簡単である可能性があります。

enter image description here

2011-11-30 07:55:05

これはまったく正しいとは思わないが、分岐部分 '（（b | d）| c *）'は3つではなく2つの枝である。（b | d）かc *ノードは、完全に別個の経路として表現してから、「b」または「d」に分岐する方が正確ではないでしょうか？ –

上記のものがThompsonの構造を使用していないと確信しています。それは短くても、私は講師がそれをやる方法のスタイルを与えられました。 – unleashed

@unleashedトンプソンは、NFAを作成するアルゴリズムではなく、NFAを作成するアルゴリズム（手順）です。あなたは私のNFAをThompsonで作成して最適化したものとして見ることができます。あなたのNFAがあなたの正規表現と同等であるかどうかという質問でした。 –

答えて