automata - NFA とイプシロン NFA の実用例

Question

NFAとイプシロンNFAのリアルタイムの例、つまりコンパイラの設計に使用される以外の実際の例は何ですか?

Answer 1

誰かが正規表現を使用するときはいつでも、有限オートマトンを使用しています。正規表現についてよく知らない場合は、正規表現が非常に一般的であることをお伝えしましょう。多くのエコシステムでは、文字列から構造化データを取得する際にほとんどの人が適用しようとする最初のツールです。オートマトンを理解することは、正規表現を理解する (そして推論する) ための 1 つの方法であり、数学に傾倒している場合には非常に有効な方法です。

実際、今日の正規表現エンジンは、これらの数学的概念を超えて成長し、FA が許可する以上のことを可能にする機能を追加しました。それにもかかわらず、多くの正規表現はこれらの機能を使用していないか、FA で実装できるように限られた方法で使用しています。

さて、以前は一般的な有限オートマトンについてしか話しませんでした。NFA は、DFA と同じように特定の FA であり、この 2 つを相互に変換できます (技術的には、DFA はすべて既に NFA です)。したがって、上記の「有限オートマトン」を「NFA」に置き換えることはできますが、内部で NFA である必要はないことに注意してください。

Answer 2

ややわかりにくいが効果的な例はaho-corasick アルゴリズムで、有限オートマトンを使用してテキスト内の複数の文字列を検索します。

Answer 3

@delnan で説明されているように、オートマトンは正規表現の形式でよく使用されます。ただし、それらはそれ以上に使用されます。オートマトンは、多くの場合、ハードウェアおよびソフトウェア システムをモデル化し、それらの特定のプロパティを検証するために使用されます。詳細については、モデル チェックを参照してください。非常に単純化された動機付けの例の 1 つは、 Introduction to Automata、Languages、および Computationの導入部で見つけることができます。

Answer 4

また、基本的に有限オートマトンに基づくマルコフ連鎖も忘れないでください。ベルピースが言及したハードウェアおよびソフトウェアのモデリングと組み合わせると、非常に強力なツールになります。

イプシロン NFA が NFA のバリエーションと見なされる理由が気になる場合は、正当な理由があるとは思いません。それらは同じように解釈されますが、すべてのステップがもはや単位時間ではない可能性がありますが、NFA は実際にはそうではありません。