1

Javaのオートマトンに対して次の操作を実装する必要があります。

  • 連結
  • クリーネ閉包
  • 連合
  • 交差点

オートマトンがNFAの場合、これらの操作は簡単です。次のリンクにある実装が気に入りました。このデータを介した有限決定性オートマトンのモデリングですが、キーの一意性の制限のため、NFAのモデリングには適していないと思います。NFAをモデル化するための回避策を教えてください。

4

2 に答える 2

2

（スキャナージェネレーターを構築するときに）これらの操作を実際に一度実装した人として、オートマトンをNFAとして構築し、サブセット構築やトンプソンのアルゴリズムなどのアルゴリズムを使用してDFAに変換することをお勧めします。これにより、一致するオートマトンの速度を犠牲にすることなく、オートマタをシンプルかつエレガントに組み合わせるためのロジックが維持されます。

お役に立てれば！

于 2012-06-05T15:26:27.590 に答える
0

DFAの使用をお勧めします。紙の上でNFAを形成する方が簡単かもしれませんが、イプシロンジャンプを考慮しているため、有効な文字列をNFAに対してチェックすることは、DFAに対して検証するよりも複雑になります。

それらをモデル化する限り、あなたはほんの少しのクラスであなた自身を書くことができるはずです。DFA / NFAが何で構成されているかを考えてみてください。-
開始状態
-一連の状態（一部は「受け入れ」状態）
-一連の遷移

于 2012-06-05T15:08:20.543 に答える