非決定性有限オートマトンと部分集合構成

NFA（ $ε$ 遷移なし）が文字列を受理するかを、到達しうる状態の集合をたどって判定でき、部分集合構成で得られる DFA の到達可能な状態（状態の部分集合）とその個数を求められる

前提

決定性有限オートマトンの動作と受理判定（大学数学オートマトン・形式言語）

説明

非決定性有限オートマトン（NFA）は、ある状態である文字を読んだときの行き先が 1 つとは限らない（0 個や 2 個以上もありうる）オートマトンです。この技能では、NFA が文字列を受理するかを「今いる可能性のある状態の集合」をたどって判定します。さらに部分集合構成という方法で、同じ言語を受理する DFA を作ります。その DFA の初期状態から到達できる状態（元の NFA の状態の部分集合）を列挙し、その個数を求められるようになります。

なぜそうしてよいのか

NFA は、状態の有限集合 $Q$ 、アルファベット $Σ$ 、遷移関数 $δ$ 、初期状態 $q_{0}$ 、受理状態の集合 $F \subseteq Q$ で与えられます。DFA と違うのは、 $δ (q, a)$ が 1 つの状態ではなく $Q$ の部分集合（空集合 $\emptyset$ でもよい）になる点です。NFA が文字列 $w$ を受理するとは、 $q_{0}$ から $w$ の文字に沿って遷移をたどる道筋のうち、少なくとも 1 つが受理状態で終わることをいいます。途中で行き先がなくなった道筋は、そこで消えます。

道筋を 1 本ずつ調べると枝分かれで数が増えてしまいます。そこで、「ここまで読んだ時点でいる可能性のある状態」を集合 $S$ にまとめます。次の文字 $a$ を読んだ後の集合は、 $S$ の各状態からの行き先をすべて合わせた $S^{'} = ⋃_{q \in S} δ (q, a)$ です。どの道筋でどの状態にいるかの区別は、その後の動きに影響しません。影響するのは、どの状態にいるかだけです。そのため、集合だけ覚えておけば情報は失われません。読み終えたときの集合に受理状態が 1 つでも含まれれば、受理状態で終わる道筋があるので受理となります。

ここで、集合 $S$ と文字 $a$ から $S^{'}$ がただ 1 つに決まることに注目します。つまり「状態の集合」を 1 つの状態とみなせば、前提の技能で扱った DFA そのものになります。これが部分集合構成です。DFA の状態は $Q$ の部分集合、初期状態は ${q_{0}}$ 、受理状態は $F$ と共通部分をもつ部分集合です。部分集合は全部で $2^{∣ Q ∣}$ 個ありますが、実際に ${q_{0}}$ からたどり着けるものだけを作れば十分です。

手順

初期の集合を $S_{0} = {q_{0}}$ とする。
文字 $a$ を読むたびに、集合を $S^{'} = ⋃_{q \in S} δ (q, a)$ に更新する。 $S$ の各状態の行き先をすべて合わせる。 $S = \emptyset$ なら $S^{'} = \emptyset$ である。
受理判定：文字列を読み終えた集合 $S$ が $S \cap F \neq = \emptyset$ を満たせば受理、満たさなければ不受理とする。
部分集合構成： ${q_{0}}$ から始める。新しく現れた集合それぞれについて、すべての文字 $a \in Σ$ での行き先の集合を手順 2 の式で計算する。まだ現れていない集合が出たらリストに加える。
新しい集合が出なくなったら終了する。現れた集合が到達可能な DFA の状態であり、その個数を数える（ $\emptyset$ が現れた場合はそれも 1 個に数える）。 $F$ と共通部分をもつ集合が DFA の受理状態になる。

例題

アルファベット ${a, b}$ 上の NFA を考える。状態は $q_{0}, q_{1}, q_{2}$ で、初期状態は $q_{0}$ 、受理状態は $q_{2}$ のみとする。遷移は次の表のとおりである（ $\emptyset$ は行き先がないことを表す）。

状態	$a$	$b$
$q_{0}$	${q_{0}, q_{1}}$	${q_{0}}$
$q_{1}$	${q_{2}}$	${q_{2}}$
$q_{2}$	$\emptyset$	$\emptyset$

この NFA に部分集合構成を行って得られる DFA について、初期状態 ${q_{0}}$ から到達可能な状態の個数を求めよ。

例題の解答

手順 1：初期状態は $A = {q_{0}}$ である。

手順 4（ $A$ の遷移）： $a$ では $δ (q_{0}, a) = {q_{0}, q_{1}}$ である。これは新しい集合なので $B = {q_{0}, q_{1}}$ とおく。 $b$ では ${q_{0}} = A$ となる。

手順 4（ $B$ の遷移）： $a$ では ${q_{0}, q_{1}} \cup {q_{2}} = {q_{0}, q_{1}, q_{2}}$ となり、これを新しい状態 $C$ とする。 $b$ では ${q_{0}} \cup {q_{2}} = {q_{0}, q_{2}}$ となり、これを新しい状態 $D$ とする。

手順 4（ $C$ の遷移）： $a$ では ${q_{0}, q_{1}} \cup {q_{2}} \cup \emptyset = C$ となる。 $b$ では ${q_{0}} \cup {q_{2}} \cup \emptyset = D$ となる。

手順 4（ $D$ の遷移）： $a$ では ${q_{0}, q_{1}} \cup \emptyset = B$ となる。 $b$ では ${q_{0}} \cup \emptyset = A$ となる。

手順 5：新しい集合はもう現れないので終了する。到達可能な状態は ${q_{0}}, {q_{0}, q_{1}}, {q_{0}, q_{1}, q_{2}}, {q_{0}, q_{2}}$ の 4 個である。 $\emptyset$ は現れない。部分集合は全部で $2^{3} = 8$ 個あるが、到達できるのはこの 4 個だけである。なお、受理状態は $q_{2}$ を含む $C, D$ である。たとえば $ab$ を読むと $A \to B \to D$ と進み、 $D$ が受理状態なので受理される。

答え: $4$

よくある誤り

状態数を $2^{∣ Q ∣}$ （上の例なら $2^{3} = 8$ ）と答えてしまう誤り。正しくは、 ${q_{0}}$ から実際にたどり着けた部分集合だけを数える（上の例では 4 個）。
行き先の集合を作るとき、集合の中の 1 つの状態からの行き先だけを使ってしまう誤り。例えば ${q_{0}, q_{1}}$ で $b$ を読んだ結果を ${q_{0}}$ とするのは誤りである。正しくはすべての状態の行き先を合わせて $δ (q_{0}, b) \cup δ (q_{1}, b) = {q_{0}, q_{2}}$ とする。
受理の条件を「最後の集合 $S$ がすべて受理状態（ $S \subseteq F$ ）」としてしまう誤り。正しくは、受理状態が 1 つでも含まれる（ $S \cap F \neq = \emptyset$ ）なら受理である。例えば ${q_{0}, q_{2}}$ は $q_{0} \in / F$ を含むが、受理状態である。
行き先が $\emptyset$ になったとき、それを状態として数えない、または「その時点で受理」と扱ってしまう誤り。正しくは、 $\emptyset$ が現れたらそれも DFA の状態の 1 つとして数える。 $\emptyset$ から先はどの文字でも $\emptyset$ にとどまり、 $\emptyset \cap F = \emptyset$ なので受理されない。

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

状態	$a$	$b$
$1$	${1}$	${1, 2}$
$2$	${3}$	${3}$
$3$	$\emptyset$	$\emptyset$

状態 \\ 入力	$a$	$b$
$p$	${p, q}$	${p}$
$q$	${r}$	${s}$
$r$	$\emptyset$	${s}$
$s$	${s}$	$\emptyset$

状態	$a$	$b$
$0$	${0, 1}$	${0}$
$1$	${2}$	${2, 3}$
$2$	${3}$	$\emptyset$
$3$	$\emptyset$	$\emptyset$

非決定性有限オートマトンと部分集合構成

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題