決定性有限オートマトンと非決定性有限オートマトンの等価性: 形式言語理論入門 7

この章では、決定性有限オートマトンと非決定性有限オートマトンの等価性が認識できる言語の集合が同じであることを示します。つまり、非決定性有限オートマトンは正規言語を認識し、逆に認識できる言語は正規言語のみということです。非決定性有限オートマトンはできることが決定性オートマトンよりも格段に多いことを考えるとこれは驚くべきことです。

二段階の証明でこれを示します。一段階目で、決定性有限オートマトンで認識できる言語が非決定性有限オートマトンで認識できることを示し、二段階目で、非決定性有限オートマトンで認識できる言語が決定性有限オートマトンで認識できることを示します。

一段階目

補題

言語 $A$ を認識する決定性有限オートマトンが存在するならば、言語 $A$ を認識する非決定性有限オートマトンが存在する。

こちらの方向は簡単です。直感的には、決定性有限オートマトンはほとんどそのままの形で非決定性有限オートマトンでもあるので、それをそのまま使えばよいです。これを数学的な議論で証明します。（初読の際は上記の直感的な意味を理解できれば証明は読み飛ばしても大丈夫です。）

証明

言語 $A$ を認識する決定性有限オートマトンを $M = (Q, \Sigma, \delta, q_0, F)$ とする。$Q’ = Q, \Sigma’ = \Sigma, q’_0 = q_0, F’ = F, \delta'(q, c) = \{\delta(q, c)\} \forall q \in Q, c \in \Sigma, \delta'(q, \varepsilon) = \emptyset$ とおく。このとき、非決定性有限オートマトン $M’ = (Q’, \Sigma’, \delta’, q’_0, F’)$ は明らかに $M$ と同じ言語を認識する。

実際、$w = w_1 w_2 \cdots, w_n$ が $q_0, q_1, \cdots, q_n$ と状態遷移して $M$ に受理されるのであれば、$y = w$, $r_i = q_i$ と取れば $r_i \in \delta'(r_{i-1}, y_i)$ となり $r_n \in F’$ なので $M’$ にも受理される。

逆に、$w = w_1 w_2 \cdots, w_n$ が $q_0, q_1, \cdots, q_n$ と状態遷移して $M’$ に受理されるのであれば、$q_i = \delta(r_{i-1}, w_i)$ となり $r_n \in F$ なので $M$ にも受理される。

二段階目

補題

言語 $A$ を認識する非決定性有限オートマトンが存在するならば、言語 $A$ を認識する決定性有限オートマトンが存在する。

こちらは「より強力」な非決定性有限オートマトンを「より単純」な決定性有限オートマトンでシミュレーションしなければならないので難しいです。この証明にはサブセット構成というテクニックを使います。非決定性有限オートマトンでは文字を読む際に様々な遷移の可能性があり、そのうちどれか一つでも受理状態にたどりつくのであれば受理されるのでした。ここで、毎回選択肢をどれか選択するのではなく、文字を読むたびに今たどり着いている可能性のある状態の集合を考えるのがサブセット構成です。非決定性有限オートマトンの状態の部分集合（サブセット）が一つの状態に対応することが名前の由来です。こうして、最後まで文字を読み取り、今たどり着いている可能性のある集合の中に一つでも受理状態があれば入力文字列を受理することにします。こうすると、状態の数は爆発的に増えますが、次に移るべき状態（サブセット）は一意（決定的）に決まるので、決定性有限オートマトンでシミュレーションすることができます。（初読の際は上記の直感的な意味を理解できれば証明は読み飛ばしても大丈夫です。）

証明

言語 $A$ を認識する非決定性有限オートマトンを $M = (Q, \Sigma, \delta, q_0, F)$ とする。第一段階と同様に、この非決定性有限オートマトンと同じ言語を認識する決定性有限オートマトンを構築する。

新しい決定性有限オートマトンの状態集合と文字集合を $Q’ = 2^Q, \Sigma’ = \Sigma$ とする。ここで $2^Q$ は $Q$ のべき集合。新しいオートマトンの状態は $Q’ = 2^Q$ の要素なので $Q$ の部分集合になる。

$M$ において状態 $q \in Q$ から $\varepsilon$ の矢印だけを辿ってたどり着ける状態の集合を $R(q) \subset Q$ とする。形式的には、$R(q) = \{r_n \in Q \mid \exists r_0, r_1, r_2, \cdots, r_n \in Q, \text{ s.t. } r_0 = q, r_i \in \delta(r_i, \varepsilon)$ である。

初期状態: $q’_0 = R(q_0)$ とする。これは一文字目を読む前にたどり着く可能性のある状態集合に対応する。

受理状態: $F’ \in Q’$ を $F$ の要素を含む $Q’$ の全ての要素と定義する。これは形式的には $F’ = \{G \subset Q \mid G \cap F \neq \emptyset\}$ である。

遷移関数: $q’ \in Q’$ と $c \in \Sigma$ について $\delta'(q’, c)$ を、$q’$ に含まれるいずれかの要素から $c$ を読んでたどり着ける状態の和集合とする。これは形式的には $\delta'(q’, c) = \cup_{q \in q’} \cup_{r \in \delta(q, c)} R(r)$ である。$c$ を読んだあと $\varepsilon$ の矢印を使って移動するかもしれないので単に $\cup_{q \in q’} \delta(q, c)$ とするのではいけないことに注意。

以上で定義される決定性有限オートマトン $M’ = (Q’, \Sigma’, \delta’, q’_0, F’)$ は $M$ と同じ言語を受理する。

実際、文字列 $w = w_1 w_2 \cdots w_n$ が $r_0, r_1, \cdots, r_m$ と状態遷移して $M$ に受理されたとし、$w_i$ により遷移する直前の状態を $r’_i$ とする。$w$ を $M’$ に入力したときの状態の列を $q_0, q_1, \cdots, q_n$ とする。初期状態の定義より $r’_1 \in q_0$ となり、遷移関数の定義より $r’_{i+1} \in q_i, (i = 1, 2, \cdots, n-1)$ となり、$r_m \in q_n$ となる。$r_m \in F$ なので $q_n \cap F \neq \emptyset$ となり、$q_n \in F’$ より $w$ は $M’$ に受理される。

逆に、$w = w_1 w_2 \cdots, w_n$ が $q_0, q_1, \cdots, q_n$ と状態遷移して $M’$ に受理されたとする。受理状態の定義から $r \in F \cap q_n$ となる $r \in Q$ が存在する。$w$ を $M$ に入力する。オートマトンの構成の仕方から、$w$ の1文字目を読む前に$\varepsilon$ の挿入の仕方とたどり方次第での $q_0$ の任意の状態にたどり着ける。帰納的に、$w$ の $i$ 文字目を読む前に $q_{i-1}$ の任意の状態にたどり着け、全ての文字を読み終わった後に $q_n$ の任意の状態にたどり着ける。つまり、ある $\varepsilon$ の選び方と遷移の選び方が存在し $r$ にたどり着ける。よって $M$ は $w$ を受理する。