計算理論の基礎(正規言語) part3
[計算理論]正規言語
決定性・非決定性
・決定性(deterministic):次の入力文字を読み出すと、次の状態が何であるか決まる
・非決定性(nondeterministic):どの時点においても次の状態としての複数の選択肢が存在する
非決定性有限オートマトン(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は受理状態の集合 \]