01. オートマトンとは

小川の飛び石を渡るBobとAlice、岸辺のウサギ

非決定性有限オートマトン (NFA) から決定性有限オートマトン (DFA) への変換は、正規表現やコンパイラの字句解析に使われる基礎技術であり、実装も容易である。

この章では、そもそも有限オートマトンとは何かを押さえ、以降の章でずっと使う例を 1 つ用意する。

有限オートマトン

有限オートマトンは、状態と遷移だけでできた機械である。入力を 1 文字ずつ読み、読んだ文字に応じて今いる状態から次の状態へ移る。入力を読み終えたときに最終状態にいれば「受理」、そうでなければ「不受理」。

「有限」は、状態の数が有限個という意味である。この機械が覚えていられるのは「今どの状態にいるか」だけで、何文字目まで読んだかも、途中に何が来たかも、状態の区別に畳み込まれた分しか残らない。

覚えられることが限られている代わりに、機械そのものが有限の大きさに収まる。状態が 4 つ、記号が 2 種類なら、「どの状態でどの文字を読んだらどこへ行くか」は 8 通りしかない。全部書き出せるし、その通りに動かせる。

逆に言えば、数を数えるようなことはできない。 ( と ) が同じ数だけ並んでいるか——といった判定は、有限オートマトンの手に負えない。状態が有限である以上、いくらでも大きくなり得る数は覚えておけないからである。

図の読み方は次の通り。

以降ずっと使う例として、正規表現

a(a|b)*bb

を取り上げる。a で始まり、a と b が何個か続き、bb で終わる文字列の集まりである。これに対応する有限オートマトンは、たとえば次のようになる。

正規表現 a(a|b)*bb に対応する NFA

オレンジが ε 遷移である。状態 1 からは ε 遷移が 2 本出ていて、 2 へ行くか 4 へ行くかが入力では決まらない。このように行き先が 1 つに決まらない有限オートマトンを、 非決定性有限オートマトン (NFA) という。

行き先が決まらないと何が困るのか、そしてどう直すのかは、この先の章で扱う。