有限オートマトン
有限オートマトン(Finite Automaton)は、入力された文字列に基づいて状態を遷移する計算モデルです。これは、特定の状態を持ち、入力に応じて次の状態に移行する仕組みを持っています。有限オートマトンは、形式言語やコンピュータ科学の基礎的な概念として広く利用されています。
有限オートマトンには、決定性有限オートマトン(DFA)と非決定性有限オートマトン(NFA)の2種類があります。DFAは、各状態に対して入力が一意に決まるのに対し、NFAは複数の遷移が可能です。これにより、NFAはより柔軟ですが、DFAは実行が簡単です。