計算理論学習ノート - 非決定性
この記事は「計算理論の基礎(共立出版)」の読書ノートです
前回は有限オートマトンの認識する言語、正規言語と正規演算について紹介した。また和集合演算に対しては正規言語で閉じていることを示した。
順当には連結演算に対して正規言語で閉じていることを示したいが、実はこの証明をするためには非決定性の有限オートマトンを導入したほうがわかりやすい。よってここで非決定性の有限オートマトンを導入することにする。
これまでの有限オートマトンはある何らかの入力が与えられる前提で、次に遷移する状態はただ一つ必ず定まっていた。このような有限オートマトンを特に決定性有限オートマトン(DFA - Deterministic Finite Automaton)という。一方で次に遷移する状態が0以上の自然数をとるオートマトンを考えることができる。このような有限オートマトンは、次に遷移する状態が一意に決定しない、という意味において非決定性有限オートマトン(NFA - Non-Deterministic Finite Automaton)という。厳密には次のように定義される有限オートマトン$${M \equiv (Q, \Sigma, \delta, q, F)}$$のことを言う。
$${Q}$$は有限な状態集合
$${\Sigma}$$は空文字$${\varepsilon}$$を含む、アルファベット
$${\delta: Q\times\Sigma \to 2^{Q}}$$は遷移関数
遷移先が複数の状態をとるので、遷移先としては状態の集合を採用する
$${q}$$は初期状態
$${F \subset Q}$$は受理状態の集合
非決定性有限オートマトンでは入力として空文字$${\varepsilon}$$も採用される点に注意しよう。
非決定性有限オートマトンではどのように計算が行われるだろうか。決定性有限オートマトンとは違い、遷移先が複数ある場合があるのでその際に遷移先を迷うことにはならないのか。
実際には非決定性有限オートマトンにおいて遷移先が複数あった場合、取りうるすべての可能性において並列にその後の計算を続ける、という方法をとる。また、遷移先がない場合はその可能性の計算をその時点で終了するようにする。最後にすべての入力が終わったとき、あらゆる可能性の計算において一つでも受理状態にある計算が存在すれば、非決定性有限オートマトンはその文字列を受理する。
こう考えると非決定性有限オートマトンは決定性有限オートマトンの計算の並列処理バージョンとみなすことができる。実際、非決定性有限オートマトンは決定性有限オートマトンの拡張でありつつ、受理可能な言語には差異がない。また非決定性有限オートマトンは決定性有限オートマトンに変換することが可能である。まとめると次のような定理になる。
・すべてのNFAは等価な（つまり同じ言語を認識する）DFAをもつ
このことを証明しよう。$${\varepsilon}$$からの遷移がない、適当なNFAを$${N = \{Q, \Sigma, \delta, q_0, F\}}$$と置くことにする。これに対し、DFA$${M = \{Q', \Sigma', \delta', q_0', F'\}}$$を次のように構成する。
$${Q' \equiv 2^Q}$$
$${\delta'(R, a) \equiv \cup_{r \in R} \delta(r, a)}$$
つまり、$${R}$$内の状態から、そのNFAにおいて遷移する状態すべてをかき集めてきた集合となる
$${q_0' \equiv \{q_0\}}$$
$${F' \equiv \{R \in Q' : \exist r \in R, r \in F\}}$$
つまり、$${N}$$の受理状態を含む、あらゆる$${R}$$を受理状態として扱う
このように構成したDFA$${M}$$がNFA$${N}$$と同等の動作をするか考えてみよう。入力$${a_0}$$が与えられ$${N}$$において初期状態$${q_0}$$にあったときは、$${\delta'(q_0', a_0) = \delta(q_0, a_0)}$$となる。この状態を$${R_1}$$とおこう。その次のステップにおいては入力$${a_1}$$が与えられて、NFAにおける遷移先状態候補は$${\cup_{r \in R_1}\delta(r, a_1)}$$となる。これはDFAにおける遷移先状態$${\delta'(R_1, a_1)}$$と一致する。あとは数学的帰納法によって遷移先状態を決めればいい。$${k}$$ステップ目において$${\delta'(R_k, a_k) = \cup_{r \in R_k} \delta(r, a_k)}$$が正しいと仮定したときに、$${k+1}$$ステップ目でも$${\delta'(R_{k+1}, a_{k+1}) = \cup_{r \in R_{k+1}} \delta(r, a_{k+1})}$$は正しいだろうか？ $${R_{k+1}}$$は$${\cup_{r \in R_k} \delta(r, a_k)}$$によって定義されるから、NFAにおいて次の遷移先状態候補は集合$${\cup_{r \in R_{k+1}} \delta(r, a_{k+1})}$$によって定義される。$${\delta'}$$の定義から明らかにこれは$${\delta'(R_{k+1}, a_{k+1})}$$と一致する。NFAにおいて最後の状態候補は集合で定まり、$${R_{n} \equiv \cup_{r \in R_{n-1}} \delta(r, a_{n-1})}$$と定義され、$${\exist r \in R_n, r \in F}$$が成立するとき、文字列は受理される。$${F'}$$の定義から、NFA$${N}$$で受理される文字列はDFA$${M}$$でも明らかに受理され、$${N}$$で受理されないものは$${M}$$では受理されない。
ここまでの証明は$${\varepsilon}$$に遷移先がない場合のみしか考えてなかったので、これに遷移先が存在する場合に証明を拡張する。$${M}$$の任意の状態$${R \in Q'}$$に対して、$${E(R)}$$を次のように定義する。
$$
E(R) \equiv \{q : qはr \in Rから0個以上の\varepsilonによって遷移する\}
$$
この定義により、常に$${R \subset E(R)}$$であることに注意しよう。この$${E(R)}$$によって$${M}$$の遷移関数$${\delta'}$$を次のように修正する。
$$
\delta'(R, a) \equiv \cup_{r\in R} E(\delta(r, a))
$$
つまり、遷移した後、空文字$${\varepsilon}$$で遷移できる状態も含むようにした、ということだ。
さらに初期状態も修正する必要がある。これは単純に$${q'_0 \equiv \{q_0\}}$$から
$$
q'_0 \equiv E(\{q_0\})
$$
とするだけでいい。
以上がNFAと等価なDFAを構成する方法である。$${M \equiv (Q', \Sigma, \delta', q_0', F')}$$の定義をまとめよう。
$${Q' \equiv 2^{Q}}$$
$${\delta'(R, a) \equiv \cup_{r\in R} E(\delta(r, a))}$$
$${q'_0 \equiv E(\{q_0\})}$$
$${F' \equiv \{R \in Q' : \exist r \in R, r \in F\}}$$
この記事が気に入ったらサポートをしてみませんか？