Aritalab:Lecture/Automata/Regular

Revision as of 10:28, 7 May 2013

形式言語理論のトップページヘ

まとめ

ここでは正則表現（または正規表現）という表現形式であらわされる言語が、有限オートマトンが受理する言語と等価であることを示します。 有限オートマトンの能力は、非決定性（同じ入力に対して移動先が複数あってよい）でもε入力つき（入力が無くても移動できる状態があってよい）でも変わりません。

正則表現

アルファベット Σ 上の正則表現 (regular expression) 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 から K × Σ^* → K

に拡張したわけです。

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

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

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

例として、C言語においては A, T, G, C だけを含む文字列を [ATGC]* と記述できます。そしてATGCを１つも含まない文字列は [^ATGC]* と記述できます。

Σ 上の言語 L, L' を認識する DFA があるとき、L ∩ L' を受理する　DFA　がある

L, L' を認識するDFAをそれぞれ M = (K, Σ, δ, s₀, F) , M' = (K', Σ, δ', s'₀, F') と書きます。入力アルファベット Σ は共通にしておきます。ここで、DFA の状態の対 (s, s') ∈ K × K' を状態とし、入力 a ∈ Σ に対して、 (s, s') → ( δ(s, a), δ'(s', a) ) に遷移するオートマトン N を構築します。これは状態数がもとのオートマトンの直積に対応するので、直積オートマトン と呼ばれます。直積オートマトン N において、M と M' の初期状態の組を N の初期状態とし、M と M' の受理状態の組 (複数あればその全ての組み合わせ）を N の受理状態とします。こうすると N は L ∩ L' を受理します。

Σ 上の言語 L, L' を認識する DFA があるとき、L ∪ L' を受理する　DFA　がある

L ∩ L' の場合と同じ議論で構築できます。この演算はプログラミング言語における正則表現の | 演算子に対応しています。

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

Java で正規表現を使うとき、Pattern, Machter というクラスを利用します。API仕様にはいきなり「NFA ベースのマッチング」と書いてありますが、その NFA のことです。 非決定性オートマトン (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 N の状態数を n とすると、DFA D の状態数は 2ⁿ が上限になります。 実際に 2ⁿ レベルの状態を必要とする NFA の族が 2000 年に論文になっています。

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

ε入力つき非決定性有限オートマトン (ε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ⁱ も受理してしまうので矛盾します。

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

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

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

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

言語 { xx | x ∈ { 0, 1 }^* } は、いかなる有限オートマトンでも認識できない

言語 x の具体例として 0ⁿ を考えてみます。0²ⁿだけを認識するオートマトンは、言語 {0ⁿ1ⁿ | n ≥ 0 } の場合と同じ証明手順により、構築できないことがわかります。

上記の例はいずれも、n が無限である点に注意してください。例えば、言語 {0ⁿ1ⁿ | 10000 ≥ n ≥ 0 } であれば有限オートマトンで認識できます。