決定性有限オートマトンとは
決定性有限オートマトン (DFA) は有限状態機械で、それぞれの文字列によって一意に決まるシーケンスを通してパースすることによって文字列を受け入れたり拒否したりします。
「決定論的」という用語は、各文字列、したがって各状態シーケンスが一意であるという事実を指します。 DFAでは、記号の文字列はDFAオートマトンを通してパースされ、各入力記号は決定できる次の状態に移動することになる。
到達可能な状態が限られているため、これらの機械は有限と呼ばれます。 有限オートマトンは、両方の条件を満たすことができる場合にのみ、決定論的と呼ばれます。 DFAが非決定論的オートマトンと異なるのは、後者が一度に複数の状態に遷移でき、一度に複数の状態で活動できる点です。
実際には、DFAは5つの要素から構成されています（そして、それらはしばしば5タプルと呼ばれる5つの記号の集合で示されます）。 これらの構成要素は以下の通りです。
- 有限個の状態
- アルファベットとして知られる記号のセット、これも有限
- 各記号の状態間の移行を操作する関数
- 最初の入力が与えられるか処理される最初の開始状態
- 最終状態または状態、受け入れ状態として知られる。
Sisense の動作を見る:
Explore Dashboard
How Can I Use Deterministic Finite Automata?
元々は抽象的な数学モデルとして作成されましたが、今日の DFA はコンピュータとデータ科学の両方で広く普及しています。 有限オートマトンは、ほとんどのコンピュータ言語のコンパイラによって、解析と実際の使用のためのコードの準備を支援するために使用されています。 また、自然言語処理などの言語処理システムにも広く利用され、ユニークで多様な入力にどのように対応するかをプログラムが理解するのに役立っている。
DFAは、複数の状態を同時にアクティブに保持することができないため、パスワード認識アルゴリズム (ユーザーの入力が正しいか正しくないかを判断する) からフィルタリング アルゴリズム、さらにはテキスト処理アプリケーションまで、あらゆるものに不可欠なものです。 データサイエンスでは、基本的な決定論的有限オートマトンは、データウェアハウスやその他のストレージシステムを構築する際のソートツールとして利用することができる。
到着したデータを解析し、適切な場所を決定することにより、DFA はソートの大部分を自動化し、タスクを手動で実行するよりも大幅に高速に行うことができます。 非決定論的有限オートマトン (NFA) と組み合わせると、データ ウェアハウスは、データが複数の場所に属するかどうかを確認することもできます。 DFAとNFAを別々に使用することで、より広範で効果的なソリューションを構築することができます。
Sisenseの活用事例を見る用語集に戻る