2013.09.09

エセSEだけど頑張ってオートマトンを解説してみる

Book
IT

夏休み(育休)中に頭を使う本を読んだ。ずいぶん前に買って積ん読にしていた本だ。そして育児をしながらというのを差し引いても読了までに時間がかかった本になった。

[amazonjs asin=”4130633570″ locale=”JP”]

本書はオートマトンをファンタジーな世界の物語の中で解説するというってよくありそうでなかった本。オートマトンって聞いたことはあるけど、なんだかわからない自分。物語形式で読めば理解できるかなと思った。そしてきっとオートマトンは情報処理に役に立つに違いないとも思った。その結論が本エントリーになる。

オートマトンとは何か

オートマトンとは、「出力が、入力と状態によって決定される自動機械」だそうだ。

言語の定義を”状態とその遷移”で決めたのがオートマトン。

逆にいえば、ある文字列がある言語の要素かどうか判定(検査)できるようにしたのがオートマトン。つまり、ある文字列をある言語を表現した自動機械オートマトンに入力してみて、判定OKならば、ある文字列はある言語の要素といえるというわけだ。

じゃあこのオートマトン、なにがいいのか。オートマトンの考え方に従うと状態が最小限に表現されているという特徴があるが、これが利点だと思う。

状態の数が少ないと何がよいのか。ここでいきなり話が飛ぶけど、システム屋さんから見れば考えるべき状態が少なければプログラムの最適化がしやすい。そしてなんといっても状態が少なければ試験する項目も少なくてすむことがいい。そう、オートマトンはシステム開発に役立つ考え方なのだ。

以上で話はおしまいなのだけど、さすがにこれだけで理解できる人はいないんじゃないだろうか。なので、例を紹介しつつ、オートマトンを理解してみる。

オートマトンで表現される言語の例

ある言語の例として、a,b,cという文字のみで表現される言語を考察する。

その言語は

aで始まる
cで終わる(cの後には文字は存在しない)
bはaとcの間に存在しえる(0個でも何個でも)

と定義付けされた文字の集合とする。実際に記述すると、

{ac} {abc} {abbc} {abbbc} {abbbbc} …

といった文字集合の言語だ。

これをオートマトンの考えである状態とその遷移で表してみよう。

まず状態を整理する。

aの状態を開始状態と呼ぶ
cの状態を終了状態と呼ぶ
とりあえずbの状態を中間状態と呼ぶ

ということで、考えられる状態は開始、中間、終了の3つ。

条件も考えておこう。これが遷移と呼ばれる部分だ。

はじまりは必ず開始状態なので、aが入力されないとだめ
開始状態のときに遷移できるのは、入力がbの場合の中間状態か、入力がcの場合の終了状態
中間状態のときに遷移できるのは、入力がbの場合の中間状態か、入力がcの場合の終了状態
終了状態のときには終了なので遷移不可

状態とその遷移を図や表に纏めるとオートマトンが完成する。今回は表にしてみた。

No.	今の状態	入力	次の状態
1	–	a	開始
2	開始	b	中間
3	開始	c	終了
4	中間	b	中間
5	中間	c	終了
6	終了	–	–

Noは便宜的に振ってみただけで、順番ではないことに注意されたい。この表に文字列を入力してみて、開始から終了まできちんと表現できるかを確認するのが判定というわけだ。

例えば、文字列{abbc}を入力してみよう文字列{abbc}から1文字づつ左から取り出し、オートマトンに入力する。

1番目の文字がaなので、開始状態に遷移する（No.1）
2番目の文字がbなので、開始→中間に遷移する（No.2）
3番目の文字がbなので、中間→中間に遷移する（No.4）
4番目の文字がcなので、中間→終了に遷移する（No.5）
文字列が終了しているところで次の入力がない遷移になっている（No6）

判定OKだ。

しかし{acb}という文字列では、この表を満たさない。終了状態のあとに遷移先がないからだ。よって判定NGだ。

このような判定をオートマトン的には検査という。文字列をオートマトンに入力するというのは、その文字列がオートマトンで表現された言語かどうかを検査していると言える。

ということで、システム屋さんからみれば、

開始状態
中間状態
終了状態

の3つの状態さえ意識すればいい(試験すればいい)というのがオートマトンの考え方。中間状態がいくつ続いたとしても、それは同じ中間状態なのだ。

と、ここで少し頭を冷やそう。先ほどの表に戻って、入力と次の状態がすっかり同じ表現の部分がある。

開始状態でも中間状態でも、bを入力すれば中間だし、cを入力すれば終了だ。では開始状態と中間状態に違いはあるのかというとまったくない。よってこの表はもっと簡潔に表現できる。

No.	今の状態	入力	次の状態
1	–	a	開始
2	開始	b	開始
3	開始	c	終了
4	終了	–	–

先ほどの結論はもといで、システム屋さんからみれば、

開始状態
終了状態

の2つの状態さえ意識すればいい(試験すればいい)というのがオートマトンの考え方。状態の名前に”開始”という日本語をつけているのでしっくりこない人もいるかもしれないがそこは適当な状態名に変換していただければ。

最後に

上記のように、定義された言語(特定の規則を持った事象、と置き換えてもいい)を最小限に簡潔に表現していくことがオートマトンの考え方、と自分は理解した。

システム開発の中では状態遷移という考えは非常に重要で、さまざまなパターンに対しあらゆる入力を考慮しようとすると無限のパターンが存在するように思える。これを状態としてキチンと整理して、最小限で表現することで、想定された動作が正しく実現できるようになるのだ。正規表現とか考えたことがあれば、この考えはしっくりくることかと思う。

とはいえ、そもそもa,b,cという文字のみで表現される言語って何だよ、形式言語って何に使うんだよと言われると自分も答えに窮してしまう。まああれだ。出力が、入力と状態によって決定されるものをわかりやすく整理するための道具で、これが本質ではないってことだけ覚えておけばよいかな、と。なので、ここまで偉そうに書いておいてなんなのだが、枝葉までを理解しているかと言われると怪しいので、あまり本エントリーを信用しないように。

本の感想としては、なかなかに脳みそを刺激されて、面白かった。ちまみに自分はオートマトンをまったく知らなかったが、そういった未知の知識を学ぶには物語り形式はなかなか効力があると思う。ストーリーが気になって、中身をよく理解しないまま、先へ進んでしまう危険もあるけどね。あらためて本って勉強になると思った。

Pocket