決定性有限オートマトンの動作と受理判定

遷移表で与えられた DFA について、入力文字列を 1 文字ずつ読んで状態をたどり、最後の状態 $δ^(q_{0}, w)$ が受理状態かどうかで $w$ が受理されるかを判定できる

前提

中学までに習ったことだけで始められます。

説明

決定性有限オートマトン（DFA）は、いつも状態を 1 つだけ持ち、文字を 1 つ読むたびに決まった規則で次の状態へ移る「機械」です。この技能を身につけると、遷移表で与えられた DFA に文字列を入力したとき、読み終えた時点でどの状態にいるかを求め、その文字列が受理されるかどうかを判定できます。パターン照合、字句解析、自動販売機のような制御の設計など、「入力を 1 文字ずつ見て判定する」処理を考えるときの基本になります。

なぜそうしてよいのか

DFA は 5 つの部品の組 $(Q, Σ, δ, q_{0}, F)$ で決まります。 $Q$ は状態の有限集合、 $Σ$ は使う文字の有限集合（アルファベット）です。 $δ$ は遷移関数で、状態 $q$ と文字 $a$ の組に、次の状態 $δ (q, a) \in Q$ をちょうど 1 つ対応させます。 $q_{0} \in Q$ は初期状態、 $F \subseteq Q$ は受理状態の集合です。遷移表では、行が「今の状態」、列が「読む文字」を表し、行と列が交わるマスに次の状態が書かれています。

「決定性」とは、どの状態でどの文字を読んでも、行き先がちょうど 1 つに決まるという意味です。そのため、初期状態から文字列 $w = a_{1} a_{2} \dots a_{n}$ を左から順に読むと、たどる状態の列 $q_{0} \to p_{1} \to p_{2} \to \dots \to p_{n}$ は迷うことなく 1 通りに決まります。この最後の状態 $p_{n}$ を $δ^(q_{0}, w)$ と書きます。きちんと式で書くと、空文字列 $ε$ （長さ 0 の文字列）に対しては $δ^(q, ε) = q$ とし、文字列 $w$ の後ろに文字 $a$ をつないだ $w a$ に対しては $δ^(q, w a) = δ (δ^(q, w), a)$ と定めます。「ここまで読んだ後の状態」に「次の文字」を当てはめて 1 歩進む、という操作を繰り返しているだけです。

終点がただ 1 つに決まるので、「 $δ^(q_{0}, w) \in F$ なら $w$ を受理し、そうでなければ受理しない（拒否する）」という判定は、どの $w$ に対してもあいまいさなく決まります。途中でどの状態を通ったかは判定に関係しません。見るのは、読み終えた時点の状態だけです。

手順

DFA の情報を確認する：状態の集合、アルファベット、遷移表、初期状態 $q_{0}$ 、受理状態の集合 $F$ を読み取る。
現在の状態を初期状態 $q_{0}$ に置く。
入力文字列を左から 1 文字ずつ読む。読むたびに、遷移表の「現在の状態 $q$ 」の行と「読んだ文字 $a$ 」の列が交わるマスを見て、現在の状態をそこに書かれた $δ (q, a)$ に置き換える。
すべての文字を読み終えたときの状態が $δ^(q_{0}, w)$ である（空文字列なら $δ^(q_{0}, ε) = q_{0}$ ）。
$δ^(q_{0}, w) \in F$ なら $w$ は受理される、 $δ^(q_{0}, w) \in / F$ なら受理されないと判定する。

例題

アルファベット ${0, 1}$ 、状態 $q_{0}, q_{1}, q_{2}$ の DFA を次の遷移表で定める。初期状態は $q_{0}$ 、受理状態は $q_{0}$ のみとする。

状態	0	1
$q_{0}$	$q_{0}$	$q_{1}$
$q_{1}$	$q_{2}$	$q_{0}$
$q_{2}$	$q_{1}$	$q_{2}$

入力 $w = 10110$ に対して $δ^(q_{0}, w) = q_{k}$ となる $k$ を求めよ（あわせて、 $w$ が受理されるかどうかも判定せよ）。

例題の解答

手順 1：状態は $q_{0}, q_{1}, q_{2}$ 、アルファベットは ${0, 1}$ 、初期状態は $q_{0}$ 、受理状態の集合は $F = {q_{0}}$ である。
手順 2：現在の状態を $q_{0}$ とする。
手順 3： $w = 10110$ を左から読む。
・1 文字目 $1$ ： $q_{0}$ の行・ $1$ の列を見て $δ (q_{0}, 1) = q_{1}$ 。
・2 文字目 $0$ ： $δ (q_{1}, 0) = q_{2}$ 。
・3 文字目 $1$ ： $δ (q_{2}, 1) = q_{2}$ 。
・4 文字目 $1$ ： $δ (q_{2}, 1) = q_{2}$ 。
・5 文字目 $0$ ： $δ (q_{2}, 0) = q_{1}$ 。
たどった状態の列は $q_{0} \to q_{1} \to q_{2} \to q_{2} \to q_{2} \to q_{1}$ である。
手順 4：読み終えた時点の状態は $δ^(q_{0}, 10110) = q_{1}$ なので、 $k = 1$ 。
手順 5： $q_{1} \in / F = {q_{0}}$ なので、 $w = 10110$ は受理されない。
（参考：この DFA は、ここまで読んだ文字列を 2 進数とみたときの値を 3 で割った余りが $r$ のとき、状態 $q_{r}$ にいるように作られている。 $10110$ は 10 進数で $22$ で、 $22 = 3 \cdot 7 + 1$ より余りは 1 となり、結果と一致する。）

答え: $1$

よくある誤り

途中で受理状態を通ったから受理と判定してしまう誤り。正しくは読み終えた最後の状態だけで判定する。例：上の DFA で $w = 1101$ を読むと $q_{0} 1 q_{1} 1 q_{0} 0 q_{0} 1 q_{1}$ となる。途中（2 文字目・3 文字目の後）で受理状態 $q_{0}$ を通っているが、最後の状態は $δ^(q_{0}, 1101) = q_{1} \in / F$ なので、 $1101$ は受理されない（拒否）。
文字列を右から読んでしまう誤り。正しくは左端の文字から順に読む。例：上の DFA で $w = 10$ を右から読むと $q_{0} 0 q_{0} 1 q_{1}$ となってしまうが、正しくは $q_{0} 1 q_{1} 0 q_{2}$ で、 $δ^(q_{0}, 10) = q_{2}$ 。
遷移表の行と列を取り違える誤り（読んだ文字の行や、状態の列を見てしまうなど）。正しくは「今の状態」の行と「読んだ文字」の列の交点を見る。例： $δ (q_{1}, 0)$ は $q_{1}$ の行・ $0$ の列のマスで $q_{2}$ である。 $q_{0}$ の行・ $1$ の列のマス（ $δ (q_{0}, 1) = q_{1}$ ）と混同しない。
空文字列 $ε$ の扱いを忘れる誤り。正しくは 1 文字も読まないので $δ^(q_{0}, ε) = q_{0}$ であり、初期状態が受理状態のときは $ε$ は受理される。上の DFA では $q_{0} \in F$ なので $ε$ は受理される。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（教科書の例題レベル）
アルファベット $Σ = {0, 1}$ 上の決定性有限オートマトン $M$ を考える。状態の集合は ${q_{0}, q_{1}, q_{2}}$ 、初期状態は $q_{0}$ 、受理状態は $q_{2}$ のみであり、遷移関数 $δ$ は次の表で与えられる（行が現在の状態、列が読む文字、表の中身が次の状態）。
状態 $0$ $1$
$q_{0}$ $q_{0}$ $q_{1}$
$q_{1}$ $q_{2}$ $q_{0}$
$q_{2}$ $q_{1}$ $q_{2}$
次の $5$ つの文字列のうち、 $M$ が受理するものの番号の集合を求めよ。
$(1) 10 (2) 110 (3) 101 (4) 0111 (5) 1011$

この技能を使う問題

状態	$a$	$b$	$c$
$p$	$q$	$r$	$p$
$q$	$r$	$s$	$q$
$r$	$s$	$p$	$r$
$s$	$p$	$q$	$s$

この技能の次に学べること

状態ごとの文字列数の漸化式（大学数学オートマトン・形式言語）
非決定性有限オートマトンと部分集合構成（大学数学オートマトン・形式言語）
言語の条件から DFA を作る（余り・接尾辞・積構成）（大学数学オートマトン・形式言語）
DFA の最小化（区別可能な状態の対）（大学数学オートマトン・形式言語）
チューリング機械の動作の追跡（大学数学オートマトン・形式言語）