最近、私は有限状態マシン（FSM）と、それらをソフトウェアに実装する方法について考えています（プログラミング言語は関係ありません）。
私の理解では、決定論的ステートマシンが広く使用されています（解析/レクサー、コンパイラーなど）が、非決定論的ステートマシンの問題は何ですか？
すべての非決定論的ステートマシンを決定論的ステートマシンに（プログラムでさえ）変換することが可能であることを私は知っています。それは私のポイントではありません。また、非決定論的ステートマシンの実装ははるかに複雑だと思います。
とにかく、非決定論的ステートマシンを実装することは意味がありますか？知らない特別なアプリケーションはありますか？それをする理由は何でしょうか？おそらく、最適化され、特殊化された非決定論的ステートマシンの方が高速ですか？
ほとんどの正規表現エンジンは、はるかに高い柔軟性を提供するため、非決定性オートマトンを使用します。DFAははるかに制限されています。いくつかの実装を見てください、そしてあなたはこれを見るでしょう。Microsoftは、.NETRegexクラスのドキュメントでこの事実を強調しています。
.NET Framework正規表現エンジンは、Perl、Python、Emacs、Tclで使用されているような従来の非決定性有限オートマトン（NFA）エンジンを組み込んだバックトラック正規表現マッチャーです。
マッチング動作（最初の段落）–この記事は、より効率的なDFAではなくNFAを採用する理由も提供します。
ご存知のように、NFA と DFA は計算上同等です。これは、オートマトン理論の最初の定理の 1 つです。あるものを別のものに変換するアルゴリズムがあります (プッシュダウンやチューリング マシンとは異なります)。
そう。なぜ一方が他方よりも優れているのですか？NFA を使用した特定の問題の表現は、同等の DFA よりもはるかに簡単だからです。
編集:実際にマシンを計算するという点では、バックトラックする必要がないため、DFA は高速になります。ただし、表現するにはより多くのメモリが必要になります。(メモリと CPU のトレードオフ)
私のアドバイス = Adrian Thurstons Ragelのマニュアルを見てください。
DFA を直接生成する簡単な方法がありますが、それらは限られた範囲の演算子 (基本的には EBNF の通常の容疑者) しかサポートしていないと思います。Ragel は、非決定論的手法を使用して単純なオートマトンから複雑なオートマトンを構成し、イプシロン消去と最小化を使用して効率的な決定論的オートマトンを作成します。必要な奇妙な演算子の数に関係なく、最小限の決定論的オートマトンへの変換は常に同じであり、各演算子の実装は非決定論的な方法を使用して単純に保たれます。
Cayugaは、複雑なイベント処理のために内部で非決定論的有限状態マシンを利用します。ええと、彼らはそれを「イベント監視のためのステートフルパブリッシュ/サブスクライブ」と呼んでいるように見えますが、それはCEPだと思います。
彼らの論文のいくつかは、なぜオートマトンモデルを使用しているのかについてさえ論じていると思います。あなたは彼らのサイトをいじくり回したいかもしれません。
...標準の非決定性有限オートマトンから拡張されたカユガオートマトン。
非決定論的な有限オートマトンを選択する主な理由は、選択した一致を実際に戻すためだと思います。決定論的なバージョンでそれを行うのはおそらくはるかに困難です。
あなたが知りたいのは、それらが一致するかどうかだけで、他の詳細がない場合は、有限オートマトンにコンパイルする方が良いと思います。
ビタビ アルゴリズムは、隠れマルコフ モデルを NFA のように扱うことによって、それらを操作します。完全に同一ではありませんが、確かに類似しています。
これらは、音声認識やテキスト認識などのアプリケーションで役立ちます。
間違っている場合は訂正してください。ただし、私のコンパイラ クラスから、状態の「爆発」につながるため、DFA を使用できない場合があることを覚えています。