有限オートマトン | 計算理論 | 天游ヶ丘数理学院

1 形式言語と決定性有限オートマトン

最初に、機械が入力として受け取る語と言語を定める。

定義 1.1. アルファベット (alphabet) $\Sigma$ は空でない有限集合である。 $\Sigma$ の元を文字 (symbol) という。有限個の文字を順に並べたものを $\Sigma$ 上の語 (word) といい、語全体の集合を $\Sigma^*$ と書く。長さ $0$ の唯一の語を空語 (empty word) といい、 $\varepsilon$ と書く。

二つの語 $u,v$ を順に並べて得られる語を連接 $uv$ という。空語は連接の単位元であり、

\varepsilon w=w\varepsilon=w

が成り立つ。 $\Sigma^*$ の部分集合を $\Sigma$ 上の形式言語 (formal language) という。

決定性有限オートマトンでは、現在の状態と次の入力文字から遷移先が一意に定まる。

定義 1.2. 決定性有限オートマトン (deterministic finite automaton)（DFA）は、五項組

A=(Q,\Sigma,\delta,q_0,F)

である。ここで、 $Q$ は空でない有限状態集合、 $\Sigma$ は有限アルファベット、

\delta:Q\times\Sigma\longrightarrow Q

は全域的な遷移関数、 $q_0\in Q$ は初期状態、 $F\subseteq Q$ は受理状態集合である。

一文字の遷移を語へ拡張した拡張遷移関数 (extended transition function)

\widehat{\delta}:Q\times\Sigma^*\longrightarrow Q

を

\widehat{\delta}(q,\varepsilon)=q,\qquad \widehat{\delta}(q,wa)=\delta(\widehat{\delta}(q,w),a)

によって再帰的に定める。第二式では $w\in\Sigma^*$ 、 $a\in\Sigma$ である。

拡張遷移関数は、語を二つに切って順に読んでも同じ状態に至る。以後の記事でも用いるため、補題として分けておく。

補題 1.3. DFA $A=(Q,\Sigma,\delta,q_0,F)$ 、 $q\in Q$ 、 $u,v\in\Sigma^*$ に対して

\widehat{\delta}(q,uv)=\widehat{\delta}\bigl(\widehat{\delta}(q,u),v\bigr)

が成り立つ。とくに $a\in\Sigma$ に対して $\widehat{\delta}(q,av)=\widehat{\delta}(\delta(q,a),v)$ である。

証明. $v$ の長さに関する帰納法を用いる。 $v=\varepsilon$ では両辺とも $\widehat{\delta}(q,u)$ である。 $v=v'a$ では

\widehat{\delta}(q,uv'a) =\delta\bigl(\widehat{\delta}(q,uv'),a\bigr) =\delta\bigl(\widehat{\delta}(\widehat{\delta}(q,u),v'),a\bigr) =\widehat{\delta}\bigl(\widehat{\delta}(q,u),v'a\bigr)

である。後半は $u=a$ の場合であり、 $\widehat{\delta}(q,a)=\delta(\widehat{\delta}(q,\varepsilon),a)=\delta(q,a)$ による。▨

定義 1.4. DFA $A=(Q,\Sigma,\delta,q_0,F)$ が語 $w\in\Sigma^*$ を受理する (accept) とは、

\widehat{\delta}(q_0,w)\in F

が成り立つことをいう。 $A$ の受理言語 (accepted language) を

L(A)=\{w\in\Sigma^*:\widehat{\delta}(q_0,w)\in F\}

と定める。

空語を入力した場合には遷移を一度も行わない。したがって、DFA が空語を受理することと $q_0\in F$ は同値である。

例 1.5 (1の個数が偶数である語). $\Sigma=\{0,1\}$ とし、 $Q=\{E,O\}$ 、 $q_0=E$ 、 $F=\{E\}$ とする。遷移を

\delta(E,0)=E,\quad \delta(O,0)=O,\quad \delta(E,1)=O,\quad \delta(O,1)=E

と定める。

長さに関する帰納法により、語 $w$ を読み終えた状態が $E$ であることと、 $w$ に現れる $1$ の個数が偶数であることが同値になる。したがって、この DFA は $1$ の個数が偶数である語をちょうど受理する。初期状態 $E$ が受理状態であるため、空語も受理する。

2 非決定性と到達可能状態集合

非決定性有限オートマトンでは、一つの状態と入力文字に対して、遷移先が複数存在しても、存在しなくてもよい。

定義 2.1. 非決定性有限オートマトン (nondeterministic finite automaton)（NFA）は、五項組

N=(Q,\Sigma,\Delta,q_0,F)

である。ここで $Q,\Sigma,q_0,F$ は DFA と同じ種類のデータであり、遷移関数は

\Delta:Q\times\Sigma\longrightarrow\mathcal{P}(Q)

である。

状態集合 $S\subseteq Q$ から語を読んだ後に到達することができる状態集合

\widehat{\Delta}(S,w)\subseteq Q

を

\widehat{\Delta}(S,\varepsilon)=S,\qquad \widehat{\Delta}(S,wa) =\bigcup_{q\in\widehat{\Delta}(S,w)}\Delta(q,a)

によって定める。NFA $N$ が $w$ を受理するとは、

\widehat{\Delta}(\{q_0\},w)\cap F\ne\varnothing

が成り立つことをいう。

受理条件は「すべての計算経路が受理する」ではなく、「入力全体を消費して受理状態へ至る計算経路が少なくとも一つ存在する」である。途中で受理状態を通っても、残りの入力を消費する経路がなければ、その経路は受理を与えない。

DFA は遷移先が常に一元集合である NFA とみなすことができる。

命題 2.2. DFA $A=(Q,\Sigma,\delta,q_0,F)$ に対して

\Delta(q,a)=\{\delta(q,a)\}

と定めた NFA $N$ は、 $L(N)=L(A)$ を満たす。

証明. すべての $q\in Q$ と $w\in\Sigma^*$ について

\widehat{\Delta}(\{q\},w)=\{\widehat{\delta}(q,w)\}

を語の長さに関する帰納法で示す。

$w=\varepsilon$ では両辺が $\{q\}$ である。 $w=ua$ とし、 $u$ について主張が成り立つと仮定する。このとき

\begin{aligned} \widehat{\Delta}(\{q\},ua) &=\bigcup_{p\in\widehat{\Delta}(\{q\},u)}\Delta(p,a)\\ &=\Delta(\widehat{\delta}(q,u),a)\\ &=\{\delta(\widehat{\delta}(q,u),a)\}\\ &=\{\widehat{\delta}(q,ua)\}. \end{aligned}

したがって帰納法が完了する。 $q=q_0$ とすれば、NFA の到達可能状態集合が $F$ と交わることと、DFA の最終状態が $F$ に属することは同値である。よって $L(N)=L(A)$ である。▨

3 空語遷移とその除去

空語遷移は、入力文字を消費せずに状態だけを変える遷移である。空語遷移を有限回たどる可能性を、空語閉包としてまとめる。

定義 3.1. 空語遷移付き非決定性有限オートマトン (nondeterministic finite automaton with epsilon transitions)（ $\varepsilon$ -NFA）は、五項組

M=(Q,\Sigma,\Delta,q_0,F)

であり、遷移関数は

\Delta:Q\times(\Sigma\cup\{\varepsilon\}) \longrightarrow\mathcal{P}(Q)

である。

$S\subseteq Q$ の空語閉包 (epsilon closure) $E(S)$ は、 $S$ を含み、空語遷移について閉じた最小の状態集合である。すなわち、 $E(S)$ は次の二条件を満たす最小の集合である。

$S\subseteq E(S)$ 。
$q\in E(S)$ かつ $p\in\Delta(q,\varepsilon)$ ならば $p\in E(S)$ 。

入力語を読んだ後の到達可能状態集合 $R_M(S,w)$ を

R_M(S,\varepsilon)=E(S),

R_M(S,wa) =E\left( \bigcup_{q\in R_M(S,w)}\Delta(q,a) \right)

によって定める。 $M$ が $w$ を受理するとは、

R_M(\{q_0\},w)\cap F\ne\varnothing

が成り立つことをいう。

$Q$ が有限であるため、空語閉包は有限回の追加で確定する。定義は、最初の入力文字を読む前、隣り合う二文字の間、最後の入力文字を読んだ後のいずれにも、空語遷移を有限回挿入することを許している。空語自身の受理条件は $E(\{q_0\})\cap F\ne\varnothing$ である。

空語遷移は表記上便利であるが、認識することができる言語を増やさない。

定理 3.2. 任意の $\varepsilon$ -NFA $M$ に対して、 $L(N)=L(M)$ を満たす NFA $N$ を構成することができる。

証明. $M=(Q,\Sigma,\Delta,q_0,F)$ とする。同じ状態集合、アルファベット、初期状態をもつ NFA

N=(Q,\Sigma,\Delta_N,q_0,F_N)

を次のように定める。

\Delta_N(q,a) =E\left( \bigcup_{p\in E(\{q\})}\Delta(p,a) \right),

F_N=\{q\in Q:E(\{q\})\cap F\ne\varnothing\}.

遷移 $\Delta_N(q,a)$ は、 $q$ から空語遷移を任意回たどり、 $a$ を一文字読み、さらに空語遷移を任意回たどって到達することができる状態をすべて集めている。 $F_N$ の定義は、入力を読み終えた後の空語遷移による受理を保存する。

$N$ の拡張遷移を $\widehat{\Delta}_N$ と書く。任意の $S\subseteq Q$ と $w\in\Sigma^*$ について

E(\widehat{\Delta}_N(S,w))=R_M(S,w)

という不変量を、語の長さに関する帰納法で示す。

帰納法で用いる空語閉包の二つの恒等式を、閉包の最小性から確認する。部分集合族 $(S_i)_{i\in I}$ に対し、 $E(\bigcup_iS_i)$ は各 $S_i$ を含む空語遷移について閉じた集合なので、最小性から

E(S_i)\subseteq E\left(\bigcup_iS_i\right)

が各 $i$ について成り立つ。従って、

\bigcup_iE(S_i)\subseteq E\left(\bigcup_iS_i\right)

である。逆に、 $\bigcup_iE(S_i)$ は $\bigcup_iS_i$ を含む。さらに、 $q\in\bigcup_iE(S_i)$ なら、ある $i$ について $q\in E(S_i)$ であり、 $q$ からの全ての空語遷移先も同じ $E(S_i)$ に属する。従って、 $\bigcup_iE(S_i)$ は空語遷移について閉じている。 $E(\bigcup_iS_i)$ の最小性から逆向きの包含も得るので、

E\left(\bigcup_iS_i\right)=\bigcup_iE(S_i)

である。

また、 $E(S)$ 自身が空語遷移について閉じているため、 $E(E(S))$ の最小性から $E(E(S))\subseteq E(S)$ である。一方、空語閉包の定義から $E(S)\subseteq E(E(S))$ である。従って、

E(E(S))=E(S)

が成り立つ。

$w=\varepsilon$ のとき、左辺は $E(S)$ 、右辺は定義により $E(S)$ である。 $w=ua$ とし、 $u$ について不変量が成り立つと仮定する。上で示した二つの恒等式を用いると、

\begin{aligned} E(\widehat{\Delta}_N(S,ua)) &=E\left( \bigcup_{q\in\widehat{\Delta}_N(S,u)} \Delta_N(q,a) \right)\\ &=E\left( \bigcup_{q\in\widehat{\Delta}_N(S,u)} \bigcup_{p\in E(\{q\})}\Delta(p,a) \right)\\ &=E\left( \bigcup_{p\in E(\widehat{\Delta}_N(S,u))} \Delta(p,a) \right)\\ &=E\left( \bigcup_{p\in R_M(S,u)}\Delta(p,a) \right)\\ &=R_M(S,ua). \end{aligned}

したがって不変量がすべての語について成り立つ。

語 $w$ を $N$ が受理することは、ある

q\in\widehat{\Delta}_N(\{q_0\},w)

について $E(\{q\})\cap F\ne\varnothing$ であることと同値である。この受理条件は

E(\widehat{\Delta}_N(\{q_0\},w))\cap F\ne\varnothing

と同値であり、上の不変量によって

R_M(\{q_0\},w)\cap F\ne\varnothing

と同値である。よって $L(N)=L(M)$ である。▨

4 部分集合構成

NFA の一回の実行経路を選ぶ代わりに、同じ入力を読んだ後に到達することができる状態をすべて同時に記録する。有限集合 $Q$ の部分集合は有限個しかないため、この記録自体を DFA の状態にすることができる。

定理 4.1 (部分集合構成). 任意の NFA $N$ に対して、 $L(D)=L(N)$ を満たす DFA $D$ を構成することができる。

証明. $N=(Q,\Sigma,\Delta,q_0,F)$ とする。DFA

D=(\mathcal{P}(Q),\Sigma,\delta_D,\{q_0\},F_D)

を

\delta_D(S,a)=\bigcup_{q\in S}\Delta(q,a),

F_D=\{S\subseteq Q:S\cap F\ne\varnothing\}

によって定める。 $\Delta(q,a)$ が空集合でもよいため、空集合も DFA の状態として含める。空集合からの遷移は常に空集合である。

DFA の拡張遷移を $\widehat{\delta}_D$ 、NFA の拡張遷移を $\widehat{\Delta}$ と書く。任意の $S\subseteq Q$ と $w\in\Sigma^*$ について

\widehat{\delta}_D(S,w)=\widehat{\Delta}(S,w)

という不変量を、語の長さに関する帰納法で示す。

$w=\varepsilon$ の場合、両辺は $S$ である。 $w=ua$ とし、 $u$ について不変量が成り立つと仮定する。このとき

\begin{aligned} \widehat{\delta}_D(S,ua) &=\delta_D(\widehat{\delta}_D(S,u),a)\\ &=\delta_D(\widehat{\Delta}(S,u),a)\\ &=\bigcup_{q\in\widehat{\Delta}(S,u)}\Delta(q,a)\\ &=\widehat{\Delta}(S,ua). \end{aligned}

よって $ua$ についても不変量が成り立つ。

特に、

\widehat{\delta}_D(\{q_0\},w)\in F_D

であることと

\widehat{\Delta}(\{q_0\},w)\cap F\ne\varnothing

であることは同値である。したがって $L(D)=L(N)$ である。▨

到達不可能な部分集合を $\mathcal{P}(Q)$ から除いても受理言語は変わらない。ただし、同値性の証明では全冪集合を状態集合として採用すると構成が明確になる。状態数は高々 $2^{|Q|}$ である。

三つのモデルの関係をまとめる。

系 4.2. 有限アルファベット $\Sigma$ 上の言語 $L\subseteq\Sigma^*$ について、次の三条件は同値である。

ある DFA が $L$ を受理する。
ある NFA が $L$ を受理する。
ある $\varepsilon$ -NFA が $L$ を受理する。

証明.(1) $\Rightarrow$ (2)を示す。DFA は各遷移先を一元集合に置き換えることにより NFA とみなすことができる。(2) $\Rightarrow$ (3)を示す。NFA はすべての空語遷移先を空集合とすることにより $\varepsilon$ -NFA とみなすことができる。逆に、任意の $\varepsilon$ -NFA から定理 3.2によって同じ言語を受理する NFA を構成し、さらに定理 4.1 (部分集合構成)によって同じ言語を受理する DFA を構成することができる。▨

5 積構成

部分集合構成と同様に、有限個の状態を組にして同時に追跡することができる。既存の二つの DFA の判定を同時に行う積構成を示す。

定理 5.1. $L_1,L_2\subseteq\Sigma^*$ がそれぞれ DFA の受理言語ならば、 $L_1\cap L_2$ も DFA の受理言語である。

証明. $L_i=L(A_i)$ 、

A_i=(Q_i,\Sigma,\delta_i,q_i,F_i) \qquad (i=1,2)

とする。積 DFA

A=(Q_1\times Q_2,\Sigma,\delta,(q_1,q_2),F_1\times F_2)

を

\delta((p,r),a)=(\delta_1(p,a),\delta_2(r,a))

で定める。

任意の $w\in\Sigma^*$ について

\widehat{\delta}((q_1,q_2),w) = (\widehat{\delta}_1(q_1,w),\widehat{\delta}_2(q_2,w))

が成り立つことを、語の長さに関する帰納法で示す。空語の場合は拡張遷移の定義から従う。 $w=ua$ の場合は、 $u$ に関する帰納法の仮定と積遷移の定義を順に適用すればよい。したがって $A$ が $w$ を受理することは、 $A_1$ と $A_2$ がともに $w$ を受理することと同値である。よって $L(A)=L_1\cap L_2$ である。▨

積構成は、一方の DFA の受理状態集合を取り替えることによって差集合にも適用することができる。

系 5.2. $L_1,L_2\subseteq\Sigma^*$ がそれぞれ DFA の受理言語ならば、 $L_1\setminus L_2$ も DFA の受理言語である。

証明. $L_i=L(A_i)$ 、

A_i=(Q_i,\Sigma,\delta_i,q_i,F_i) \qquad (i=1,2)

とする。

最初に $\Sigma^*\setminus L_2$ を受理する DFA を構成する。 $A_2$ の受理状態集合だけを取り替えた

A_2'=(Q_2,\Sigma,\delta_2,q_2,Q_2\setminus F_2)

を考える。定義 1.2により $\delta_2$ は $Q_2\times\Sigma$ の全体で定義されているので、拡張遷移関数の再帰的な定義から、任意の $w\in\Sigma^*$ に対して状態 $\widehat{\delta}_2(q_2,w)$ が定まる。実際、語の長さに関する帰納法により、 $w=\varepsilon$ では $\widehat{\delta}_2(q_2,\varepsilon)=q_2$ であり、 $w=ua$ では帰納法の仮定で定まる状態 $\widehat{\delta}_2(q_2,u)$ と文字 $a$ に対して $\delta_2$ の値が定義されている。この状態は $F_2$ と $Q_2\setminus F_2$ のちょうど一方に属するから、

w\in L(A_2') \iff \widehat{\delta}_2(q_2,w)\notin F_2 \iff w\notin L(A_2)

が成り立つ。よって $L(A_2')=\Sigma^*\setminus L_2$ である。

この議論は遷移関数の全域性に依存する。ある状態と文字の組で遷移が定義されていない機械を許すと、その組に到達して計算を続けることができない語 $w$ が生じることがある。 $w$ は $A_2$ にも $A_2'$ にも受理されないので、そのような $w$ が存在する場合には $L(A_2')$ は $\Sigma^*\setminus L_2$ の真部分集合になり、補集合を与えない。

集合の等式

L_1\setminus L_2=L_1\cap(\Sigma^*\setminus L_2)=L(A_1)\cap L(A_2')

と定理 5.1により、 $L_1\setminus L_2$ は DFA の受理言語である。同定理の積構成を $A_1$ と $A_2'$ へ適用すると、 $L_1\setminus L_2$ を受理する DFA

(Q_1\times Q_2,\Sigma,\delta,(q_1,q_2),F_1\times(Q_2\setminus F_2))

を明示的に得る。ここで $\delta((p,r),a)=(\delta_1(p,a),\delta_2(r,a))$ である。▨

7 演習

問題 7.1.

空語遷移の除去で受理状態を $F$ のままにすると、空語の受理を保存することができない例を構成せよ。
定理 4.1 (部分集合構成)の帰納不変量を、初期集合 $S=\varnothing$ の場合について確認せよ。
系 5.2を用いて、DFA の受理言語が和集合について閉じていることを証明せよ。 $\Sigma^*$ を受理する DFA を構成してよい。

解答 (演習の要点).

状態集合を $\{q_0,q_1\}$ 、初期状態を $q_0$ 、受理状態集合を $F=\{q_1\}$ とし、遷移を空語遷移 $q_0\xrightarrow{\varepsilon}q_1$ 一本だけとする $\varepsilon$ -NFA を考える。 $E(\{q_0\})=\{q_0,q_1\}$ が $F$ と交わるため、この機械は空語を受理する。除去後の NFA には文字遷移が一つもないため、受理状態集合を $F$ のままにすると、空語の受理は $q_0\in F$ と同値になり、成り立たない。定理 3.2の $F_N=\{q:E(\{q\})\cap F\ne\varnothing\}$ は $q_0$ を受理状態に含めるため、空語の受理を保存する。
すべての $w$ について $\widehat{\delta}_D(\varnothing,w)=\varnothing=\widehat{\Delta}(\varnothing,w)$ である。実際、 $w=\varepsilon$ では両辺とも $\varnothing$ であり、 $w=ua$ では、空集合上の合併が空集合であることから、両辺とも $\varnothing$ のままである。空集合は $F$ と交わらないため、どちらの機械もこの状態からは受理しない。
状態集合を $\{s\}$ 、初期状態を $s$ 、受理状態集合を $\{s\}$ 、遷移をすべての $a\in\Sigma$ について $\delta(s,a)=s$ とする DFA は、任意の語を読み終えた状態が $s$ であるため $\Sigma^*$ を受理する。よって $\Sigma^*$ は DFA の受理言語である。任意の $L_1,L_2\subseteq\Sigma^*$ について $(\Sigma^*\setminus L_1)\setminus L_2=(\Sigma^*\setminus L_1)\cap(\Sigma^*\setminus L_2)$ であり、この集合の $\Sigma^*$ における補集合は De Morgan の法則により $L_1\cup L_2$ である。したがって $L_1,L_2$ が DFA の受理言語であれば、系 5.2を三回適用して、 $\Sigma^*\setminus L_1$ 、 $(\Sigma^*\setminus L_1)\setminus L_2$ 、 $L_1\cup L_2$ が順に DFA の受理言語であることが従う。定理 5.1の積構成において受理状態集合を $(F_1\times Q_2)\cup(Q_1\times F_2)$ へ取り替え、和集合を受理する DFA を直接構成することもできる。

▨

§E15.1有限オートマトン

1 形式言語と決定性有限オートマトン

2 非決定性と到達可能状態集合

3 空語遷移とその除去

4 部分集合構成

5 積構成

7 演習

参考文献

前提記事