有限オートマトン

言語Lの認識装置---文を与えると、それがLに属しているかどうか判定する。

• 状態の集合$K$
• 入力アルファベット$\Sigma$
• 遷移関数$\delta :K\times \Sigma \to K$
• 初期状態$q_0\in K$
• 最終状態$F\subseteq K$

初期状態から、文字を読み取るごとに次の状態へ遷移していき、文を全部読んだときに最終状態のどれかになれば「その文を受理する」(図3.1[偶数個の0と偶数個の1から成る列を受理するオートマトン])。状態の数が有限個しかないので、有限状態機械とも言う。

有限オートマトンのシミュレータがダウンロードできる。