計算理論の基礎(正規言語) part3

[計算理論]正規言語

決定性・非決定性

・決定性(deterministic)：次の入力文字を読み出すと、次の状態が何であるか決まる
・非決定性(nondeterministic)：どの時点においても次の状態としての複数の選択肢が存在する

決定性有限オートマトン(DFA)

・すべての状態において、出て行く遷移を表す矢印が、アルファベットの各文字に対して１つ。
・矢印のラベルはアルファベット

非決定性有限オートマトン(NFA)

・一つの状態においてアルファベット各文字に対する矢印の本数は0, 1またはそれ以上。
・矢印のラベルはアルファベットもしくはε(空文字)

NFAは複数の遷移があるとき、コピーを作成し、以後並列に処理する。
最終的に機械のコピーのどれか一つでも受理状態であれば、NFAは状態を受理する。
すべてのNFAはDFAに置き換えられる。

一進アルファベット(unary alphabet)：ただ一文字だけで構成されるアルファベット

非決定性オートマトンの正式な定義

\[ P(Q)：Qのすべての部分集合の集まり(Qのべき集合) \]
\[ Σ_ε ：Σ \cup \{ ε \} \]

非決定性オートマトンは5個組(Q, Σ,　δ0, q0, F)
\[ 1. Qは状態(state)と呼ばれる有限集合 \]
\[ 2. Σ はアルファベット(alphabet)と呼ばれる有限集合 \]
\[ 3. δ: Q \times Σ_ε \rightarrow P(Q) は遷移関数 \]
\[ 4. q_0 \in Q は開始状態 \]
\[ 5. F \subseteq Qは受理状態の集合 \]

NFAの計算の正式定義

N=(Q, Σ, δ, q0, F)を有限オートマトンとし、
各yiはΣεの要素であって、yiを用いて、ωがω = y1 y2 ...ym と表され
以下の三条件を満たす状態の列、r0,r1,...,rn が存在するならばNはωを受理する。
\[1. r_0 = q_0 (機械が開始状態から始動する) \]
\[2. i = 0, ..., mー1 のとき、r_{i+1} \in q( r_i , y_{i+1} ) \]
\[3. r_m \in F (機械が受理状態で終わる) \]

等価性

等価(equivalent)：二つの機械が同じ言語を認識すること。
「すべての非決定性オートマトンは等価な決定性オートマトンを持つ」