Aritalab:Lecture/Automata/Regular

正規表現

アルファベット Σ 上の正規表現 S と、 S が表現する言語 L(S) を以下のように定義します。

1. Φ は正規表現であり、 L(Φ) = Φ
2. ε は正規表現であり、 L(ε) = { ε }
3. a ∈ Σ なら a は正規表現であり、 L(a) = { a }
4. R₁ と R₂ が正規表現なら

R₁ | R₂    R₁R₂    R₁^*

も正規表現であり、それぞれ

L( R₁ | R₂ ) = L(R₁) ∪ L(R₂)

L( R₁R₂ ) = L(R₁) L(R₂)

L( R₁^* ) = L( R₁ )^*

決定性有限オートマトン

状態 K, 入力記号　Σ, 受理状態 F ⊂ K の各有限集合を与えられたとき、決定性有限オートマトン (DFA: Deterministic Finite Automaton) は M = (K, Σ, δ, s₀, F) で与えられます。s₀ ∈ K は初期状態、 δ : K × Σ → K は（状態）遷移関数と呼ばれます。

DFAは与えられた列が言語に属するかどうかを判定する機械と考えるとわかりやすいです。普通は状態を○、状態間の遷移を→、受理状態を◎であらわします。例えば以下は、状態１において入力記号 0 を読み込み、状態２に移動することを意味しています。

0
①　−−−› ②

これを　δ(s₁, 0) = s₂ と書きます。DFAにおける各状態は、全ての入力記号に対応する状態遷移関数（→）を持っています。

この定義だと、状態遷移関数が入力記号毎に与えられていますが、これは列へと自然に拡張できます。まずは再帰的な写像 δ' を用意します。

任意の s ∈ K, a ∈ Σ, x ∈ Σ^* に対して δ'(s, ε) = s かつ δ'(s, xa) = δ(δ'(s, x), a)

この写像を、これからは δ と書きます。状態遷移関数を

δ : K × Σ^* → K

に拡張したわけです。

与えられた列 x を読み込み、最後に受理状態になったとき、その列は受理されたといいます。オートマトン M が受理する列の全体を、M が認識する言語といいます。

例. Σ 上の言語 L を認識する DFA があるとき、L　の補集合 Σ^* - L を受理するDFAを作る

L を認識するDFAを M と書きます。M が受理しない列は、読み終わったときに非受理状態にあります。そのため、M における受理状態を非受理に、非受理状態を受理に全て入れ替えれば完成です。この補集合演算はプログラミング言語における正規表現の ^ 演算子として利用されています。

非決定性有限オートマトン

非決定性オートマトン (NFA: Nondeterministic Finite Automaton) はDFAと同じ M = (K, Σ, δ, s₀, F) で与えられます。異なるのは状態遷移関数だけで、

K × Σ → {s₁,.. s_n }   (s ∈ K)

です。つまり、各入力記号に対して→が複数あってもよく、また存在しなくてもよいというものです。ここでも δ の定義を拡張します。

任意の s ∈ K, a ∈ Σ, x ∈ Σ^* に対して δ'(s, ε) = s かつ δ'(s, xa) = {q | p = δ'(s, x), q = δ(p,a) となる p ∈ K が存在する }

最後の「が存在する」という部分が重要です。与えられた記号列 x を読んで δ(s₀, x) に少なくともひとつの受理状態が含まれれば、その列　x は受理されるといいます。いかなる受理状態にも到達できないときに、受理されないといいます。

例. Σ 上の言語 L を認識する NFA があるとき、L　の補集合 Σ^* - L を受理するNFAを作る

これはDFAのときと同じで、受理状態と非受理状態をすべて入れ替えれば構築できます。

NFAとDFAの等価性

部分集合構成という手法を用いて、言語 L がNFA N で認識されるとき、対応するDFA D でも認識できることを示します。 N の状態集合の任意の部分集合を S₁ とします。初期状態から列をある程度読んだときに、S₁　のどの状態にも到達可能と仮定しましょう。そのとき、更に記号 a を読 んで到達できる状態集合を以下のように定義します。

S₂ = { q | q ∈ δ(p,a) となる状態 p ∈ S₁が存在する }

ここで、S₁　S₂ をそれぞれ単独の状態とみなせば、入力記号 a によって S₁　→ S₂ と遷移することにおなじです。つまり、N の状態集合の部分集合のそれぞれを状態とするDFA Dを構成し、初期状態として S₀ = { s₀} を読み替えれば構成できます。つまり、状態数は指数的に増えてしまいますが受理できる言語のクラスはNFAもDFAも変わらないということになります。