有限オートマトン

有限オートマトン（英語では finite state machine または finite automaton）は、ごく単純なコンピュータの計算モデルです。いくつかの状態といくつかの遷移からなり、与えられた語を受理するか、受理しないかを判定できます。

例

まずは形式的でない形で、有限オートマトンを表す状態遷移図を使って説明します。

簡単な有限オートマトンの例

オートマトンは状態からなります。図では、丸で表した3つの状態 q₀、q₁、q₂ です。これらの状態の間には遷移があり、それが矢印です。また、オートマトンには初期状態がなければなりません。ここでは状態 q₀ です。初期状態は、どの状態からも出ていない矢印がその状態に向かっている形でよく表します。さらに、オートマトンにはふつう受理状態があり、二重丸で表します。図では状態 q₂ です。

このように組み立てたオートマトンは、語を受理します。オートマトンに語を入力すると、オートマトンはその語を受理しようとします。受理すれば「YES」、受理しなければ「NO」と答えます。このオートマトンは文字「a、b、c」からなる語を受理しようとするので、語「abbc」を入力してみましょう。

初期状態 q₀ から始め、入力は語「abbc」です。ここからは矢印に従って進みます。

語はふつうどおり左から右へ読むので、最初に記号「a」を読みます。入力「a」の矢印は状態 q₁ に向かっているので、そこへ移り、語から記号「a」を取り除きます。入力は語「bbc」になります。

入力「b」の矢印は、ノード q₁ にもどってきます。再び最初の文字を取り除くと、入力は語「bc」になり、やはり状態 q₁ にとどまります。最後に、入力は語「c」になります。状態 q₁ からは、入力「c」の矢印で状態 q₂ に移ります。

入力語の文字をすべて読み終え、受理状態である状態 q₂ にいます。したがって、この有限オートマトンは語「abbc」を受理します。

最後に受理状態にいなければ、オートマトンはその語を受理しません。また、ある状態で進む先がない場合も、オートマトンはその語を受理しません。例えば、入力「ab」では状態 q₁ に着いたところで終わるので、オートマトンはこの語を受理しません。語「aabbc」を試しても、状態 q₁ から文字「a」の矢印が出ていないので、やはり受理されません。

このように、有限オートマトンはある語の集合を見分けるために使います。実際には、例えば入力された語が有効なメールアドレスかどうかを調べるのにオートマトンを使うことができます。

有限オートマトンの定義

オートマトンをさらにうまく扱えるように、有限オートマトンについてのこれまでの直観的なイメージを形式化します。

有限（決定性）オートマトンとは、5つ組 ⟨Q, Σ, δ, q₀, F⟩ のことです。ここで、

Q は状態の有限集合、
Σ（大文字のシグマ）はアルファベット（記号、つまり文字の有限集合）、
δ: Q × Σ ⟶ Q は遷移関数、
q₀ ∈ Q は初期状態、
F ⊆ Q は受理状態の集合です。

先ほどのオートマトンにもどると、

状態の集合 Q には3つの状態があり、Q = {q₀, q₁, q₂} です。アルファベット Σ には、オートマトンが受理したり受理しなかったりする語をつくるための文字が入っています。ここではおそらくアルファベット Σ= {a, b, c} ですが、これを含むどんな集合でもかまいません。初期状態 q₀ は状態 q₀ で、ここは変わりません。このオートマトンの受理状態の集合には状態が1つしかなく、F = {q₂} です。

遷移関数とは、文字のついた3本の矢印のことです。δ: Q × Σ ⟶ Q という書き方がわかりにくければ、これは δ が、Q の状態と Σ の文字の組に対して値をとる関数（写像といったほうがよいかもしれません）だという意味にすぎません。その値は、その状態でその文字を読んだときの次の状態です。この遷移関数は、次のような表で定めることができます。

$\begin{array}{ccc} Q & Σ & \to Q \\ q_{0} & a & q_{1} \\ q_{1} & b & q_{1} \\ q_{1} & c & q_{2} \end{array}$

例えば δ(q₁, c) の値は表の3行目からわかり、状態 q₂ です。これは状態遷移図と同じです。状態 q₁ にいて入力が文字「c」なら、状態 q₂ に移ります。オートマトンがある語を受理するとはどういうことかを形式的に定義する前に、この概念を直観的に理解したうえで、ほかの例を見てみましょう。

ほかの例

2文字のアルファベット、つまり Σ= {0, 1} 上で動き、1で終わる語だけを受理するオートマトンをつくりなさい。例えば、1、01、000001、0101011を受理します。

このオートマトンには、初期状態 q₀ と受理状態 q₁ の2つの状態があります。入力が数字1のときはいつでも受理状態 q₁ に移り、そこにとどまります。逆に、入力が数字0のときは非受理状態 q₀ に移り、やはりそこにとどまります。
2文字のアルファベット上で、最初の文字と最後の文字が異なる語だけを受理するオートマトンをつくりなさい。

このオートマトンは、最初のステップで2つの「部分オートマトン」に分かれます。語が0で始まればオートマトンは左側の部分に入り、そのままそこにとどまります。1で始まれば右側の部分に移ります。あとはこれまでと同じです。左側の部分にいて入力が1なら受理状態に移り、そこにとどまります。入力が0なら、受理状態でない状態 q₁ に移ります。

これまでのオートマトンと違って、このオートマトンには受理状態が複数あり、F = {q₃, q₄} です。
2文字のアルファベット上で、0が2つ続けて現れない語だけを受理するオートマトンをつくりなさい。

このオートマトンには、おもしろい点が2つあります。1つ目は、空語を受理することです。オートマトンに空語を入力してみると、初期状態が受理状態でもあれば、オートマトンは空語を受理します。このオートマトンはそうなっています。空語は0が2つ続けて現れない語なので、これで正しいのです。もう1つのおもしろい点は、このオートマトンのすべての状態が受理状態であることです。オートマトンが語を受理しないのは、ある状態から遷移が1つも出ていない場合だけです。これは状態 q₁ で起こります。この状態には0の遷移がありません。0の遷移があると、語に0が2つ続けて現れてしまうからです。
アルファベット {-,+,.,0,1,…,9} 上で、数を表す語だけを受理するオートマトンをつくりなさい。つまり、2、548、98263のような整数か、5584.48、3.14のような小数で、どちらもマイナスの符号をつけた負の数 -2、-548、-3.14 も、プラスの符号を明示した +2、+548、+3.14 も含みます。さらに、0.123を .123（先頭の0なし）とだけ書くこともでき、これもどちらの符号もつけられるようにします。10個の数字に対して遷移を10本書く代わりに、補助的な記号 N を使うことにします。
2文字のアルファベット上で、0ⁿ1ⁿ の形の語だけを受理するオートマトンをつくりなさい。つまり、語のはじめにいくつかの0があり、続いて同じ個数の1がある語です。このような語の例は0011、00001111、01です。

このようなオートマトンはつくれません。0の個数を「覚えておく」場所がどこにもないからです。2つ目の例のように、いくつかの「部分オートマトン」をつくらなければなりませんが、その「部分オートマトン」は n の値ごとに1つずつ、無限個必要になってしまいます。

オートマトンの計算の形式化

ここまでで、有限オートマトンそのものは形式的に定義しました。次に、このオートマトンが実際に何をするのか、つまりオートマトンの計算を定義する必要があります。

オートマトンの様相： 組 ⟨q, w⟩ ∈ Q × Σ^∗ をオートマトンの様相といいます。ここで、q はオートマトンが今いる状態、w は語のまだ読んでいない部分です。Σ^∗ はアルファベット Σ のクリーネ閉包、つまりアルファベット Σ の文字からつくることのできるすべての語の集合を表します。クリーネ閉包には空語も含まれ、空語は ε で表します。

オートマトン ⟨Q, Σ, δ, q₀, F⟩ があり、語 w を受理するかどうかを調べるとき、オートマトンは初期様相 ⟨q₀, w⟩ にあります。先ほどのオートマトンにもどって、

語 w = abbc を受理するかどうかを調べるなら、初期様相は ⟨q₀, abbc⟩ です。

計算のステップは、集合 (Q × Σ^∗) × (Q × Σ^∗) 上の、つまりオートマトンの様相の間の関係 ↦ として定義します。w = w₀w₁… w_n を、語 w のまだ読んでいない部分とします。δ(q₁, w₀) = q₂ であるとき、またそのときに限り、組 ⟨q₁, w₀w₁… w_n⟩ と ⟨q₂, w₁… w_n⟩ は関係 ↦ にあるといい、

$⟨ q_{1}, w_{0} w_{1} \dots w_{n} ⟩ \mapsto ⟨ q_{2}, w_{1} \dots w_{n} ⟩,$

と書きます。先ほどの例にもどると、初期様相は ⟨q₀, abbc⟩ です。状態遷移図から、入力「a」に対して状態 q₁ に進めることがわかります。そこで、

$⟨ q_{0}, a b b c ⟩ \mapsto ⟨ q_{1}, b b c ⟩,$

と書けます。δ(q₀, a) = q₁ が成り立つからです。これで、計算を1ステップ行いました。与えられた入力（＝語のまだ読んでいない部分の最初の文字）に対してどの状態に進むべきかを調べ、そこへ移り、語のまだ読んでいない部分から最初の文字を取り除いたのです。こうして新しい様相が得られました。

計算のステップの関係の反射推移閉包を ↦ ^∗ で表します。K₁, K₂ をオートマトンの様相として K₁ ↦ ^∗ K₂ と書くと、様相 K₁ から何ステップかの計算で様相 K₂ にたどり着けるという意味になります。言いかえると、次のような様相の有限列が存在するということです。

$K_{1} \mapsto K_{11} \mapsto K_{12} \mapsto K_{13} \mapsto \dots \mapsto K_{2}$

例えば、このオートマトンでは ⟨q₀, abbc⟩ ↦ ^∗ ⟨q₁,bc⟩ が成り立ちます。計算を2ステップ行うと語「bc」が残り、状態 q₁ にいるからです。つまり、次の様相の列が存在します。

$⟨ q_{0}, a b b c ⟩ \mapsto ⟨ q_{1}, b b c ⟩ \mapsto ⟨ q_{1}, b c ⟩$

オートマトンが語 w を受理するのは、次を満たす q_f ∈ F が存在するとき、またそのときに限ります。 $⟨ q_{0}, w ⟩ \mapsto^{*} ⟨ q_{f}, ε ⟩$ つまり、オートマトンが語 w を受理するのは、計算のステップの列で、その最後に語全体を読み終えていて、オートマトンの受理状態にいるようなものが存在するとき、またそのときに限ります。語全体を読み終えたことは、様相の語の位置に空語 ε があることで表されます。このオートマトンが語 abbc を受理するのは、次の様相の列が存在し、

$⟨ q_{0}, a b b c ⟩ \mapsto ⟨ q_{1}, b b c ⟩ \mapsto ⟨ q_{1}, b c ⟩ \mapsto ⟨ q_{1}, c ⟩ \mapsto ⟨ q_{2}, ε ⟩$

しかも、状態 q₂ が受理状態、つまり q₂ ∈ F だからです。

オートマトンが受理する言語とは、オートマトンが受理するすべての語の集合です。オートマトン A の言語を L(A) で表します。したがって、L(A) ⊆ Σ^∗ であり、次が成り立ちます。

$L (A) = {w \in Σ^{*} | A が語 w を受理する}$

正規言語とは、ある有限オートマトンが受理する言語のことです。

2つの有限オートマトンが等価であるとは、同じ言語を受理することです。つまり、L(A₁) = L(A₂) が成り立つとき、オートマトン A₁ と A₂ は等価です。

参考文献

章: 有限オートマトン, 完全なオートマトン, 非決定性有限オートマトン, 非決定性オートマトンのシミュレーション, NFA から DFA への変換

« 前へ: 形式言語

次へ: 完全なオートマトン »