Aritalab:Lecture/Automata/Regular

Revision as of 04:13, 27 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が受理する言語を全て受理することができます。

正規表現とεNFAの等価性

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

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

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

DFAで受理できる言語 ⊃ NFAで受理できる言語 ⊃ εNFAで受理できる言語 ⊃ 正規表現

であることがわかります。

NFAと正規表現の等価性