Aritalab:Lecture/Automata/Regular

Revision as of 10:41, 30 October 2010

正規表現

アルファベット Σ 上の正規表現 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 を読み込み、状態２に移動することを意味しています。

これを　δ(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_i,.. s_j }   (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の等価性

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 も変わらないということになります。

ε入力つき非決定性有限オートマトン

ε入力つき非決定性有限オートマトン (εNFA) では、入力記号を読まずに遷移することが許されます。この名前は、記号なしの遷移のときに形式的に入力記号 ε を読むと仮定するからです。状態遷移関数の定義は

K × Σ ∪ ε → {s_i,.. s_j }   (s ∈ K)

となります。 入力記号が無くても遷移できてしまうため、特定の状態に「落ち着く」ことがなくなります。入力記号の長さと遷移の数の対応も取れなくなります。 初期状態から記号列 x を読み込んで終了状態まで到達可能であれば、列 x は受理されると考えてください。（正確にはオートマトンの動作途中の状況を表わす概念を導入しないといけません。これを様相といいます。）

εNFAとNFAの等価性

遷移する手段が多い εNFA のほうが NFA よりも受理できる記号列の幅が広いように思われますが、これもそうではありません。 εNFA　E が与えられたら、E の各状態から ε遷移によって移動できる状態の集合を一つの状態とみなす NFA N を構築できます。N の状態数は E と同じで、εNFA が受理する言語を全て受理することができます。

ここまでの話を総合すると、

DFAで受理できる言語 = NFAで受理できる言語 = εNFAで受理できる言語

となります。

正規表現とεNFAの関係

では、どうして εNFA を導入したのでしょうか。それは正規表現をオートマトンで表現するのに、ε遷移があると便利だからです。 正規表現は再帰的に構成されていますが、その構成法をそのまま εNFA でシミュレートできます。

1. Φの場合、枝の無い状態に対応
2. 空文字 ε の場合、ε遷移に対応
3. 記号 a ∈ Σ の場合、a による遷移に対応
4. R₁R₂の場合、R₁ に対応するオートマトンの受理状態と、R₂ に対応するオートマトンの初期状態をε遷移で直列に結ぶ。
5. R₁^*の場合、R₁に対応するオートマトンの受理状態と初期状態をε遷移で結ぶ。
6. R₁ | R₂の場合、R₁に対応するオートマトンの受理状態と、R₂に対応するオートマトンの初期状態をε遷移で並列に結ぶ。

こうすると、正規表現　R で表現される言語 L　を受理する εNFA ができました。

NFAと正規表現の等価性

正規表現で構成される言語が εNFA で認識できても、その逆が言えないと等価性は示せません。ある言語 L が NFA で受理されるなら、L を正規表現 R で表現できることを示しましょう。

まず NFA N が受理する正規表現を Reg( N ) とあらわし、Reg の中身を徐々に分解していくことを考えます。 状態 s から s' への記号 a による遷移に注目しましょう（遷移 A とします）。この遷移1つだけを N から取り除いた NFA を N' とします。 そして、オートマトン N' の構造を保ったまま初期状態を s₀、終了状態の集合を F に置き換えたものを N'(s₀, F) のように書くことにします。

N が受理する記号列は、

• 遷移 A を使う場合（複数回かもしれない）
• 遷移 A を使わない場合

とに分けられ、それぞれの場合は

• N' (s₀, F)
• N' (s₀, {s}) → [s から s' へ aで遷移　（複数回あるかもしれない）] → N' (s', F)

という流れでオートマトン中を遷移していきます。 したがって、N が受理する正規表現は

• Reg( N'(s₀, F) )
• Reg( N'(s₀, {s}) ) [a Reg( N'(s', {s}) )]^* a Reg( N'(s', F) )

を | （または）　でつないだ正規表現に分解できます。スター演算の繰り返しが0回の可能性があるため、 [ ... ]^* のあとに a で一回遷移して、Reg(N'(s', F)) につないでいる点に注意してください。

もとの正規表現は、遷移 A を取り除いてサイズが1つ小さくなったオートマトンを意味する正規表現を用いて構成できました。これを再帰的にずっと繰り返していくと、最後は遷移の枝が0本のオートマトンを意味する正規表現だけで構築できます。遷移の枝が0のオートマトン M を表現する正規表現は

• M の初期状態が受理状態なら ε
• M の初期状態が受理状態でないなら Φ

で置き換えます。結果として、任意の NFA が正規表現で表せることがわかります。

ここまでの話を総合すると、NFAと正規表現が等価であることがわかり、結局、正規表現は DFA と等価なことが示せました。

有限オートマトン（および正規表現）の能力

有限オートマトンはその名のとおり状態が有限個しかなく、その範囲でしか（状態の）記憶ができないため認識できる言語は大きく限られます。直感的には数を憶えておく作業ができないと考えればよいでしょう。以下の結果は、正規言語におけるポンピング補題としてまとめられます。

言語 {0ⁿ1ⁿ | n ≥ 0 } はいかなる有限オートマトンでも認識できない。

上の言語を受理するオートマトン M があると仮定し、その状態数を　k とします。 n ≥ k とすると、M の初期状態から記号を k+1 個読んだとき、たどってきた状態の中には少なくとも2個同じ状態が現われます。 それらの状態に達するまでに読み込む0の数をそれぞれ i, j (i ≠ j) とすると、M は　0ⁱ1ⁱ を受理するのと同時に、0^j1ⁱ も受理してしまうので矛盾します。

括弧の対応はいかなる有限オートマトンでも認識できない。

上から導かれる事実として、入れ子になった括弧の対応はオートマトンで検出できないことがわかります。

(((..(( 例 ))..)))

のように書かれても左右の括弧を数えられないからです。