会社の新人研修でオートマトンの講義を担当した。 資料を探してみたのだが、 オートマトンを解説したWebページはなかなか見つからない。 ほとんどが大学の学内向けの授業紹介のようである。
仕方が無いので自分で資料を作った。 埋もれさせるのも勿体無いのでHTMLにしてみた。 それに手を加えて読み易くしたのがこのページである。 本質的な部分の感覚的な理解に重きを置いた。
初心者にもわかる説明を心がけたつもりだ。 しかし筆者の力量不足でうまくいっていない個所もあると思う。 読者諸氏のご意見・ご叱責を俟つ。
「オートマトン」とは何か? 自動羊肉である、というオヤジギャグは使い古されてて嫌なので(^_^;) 英和辞典で調べてみよう。 例えばEXCEED英和辞典 （三省堂）には次のように書かれている。
と、言う事だ。 つまりは自動機械の事である。 これを状態とその遷移という考え方で解釈するのがオートマトンの本質だ。 そこを理解してもらいソフトウェア設計の参考にしていただこうというのが本稿の主旨である。
本稿は次のような構成になっている。
まず状態と状態遷移の概念を説明する。 実はこれだけでオートマトンの基礎的な説明は終わってしまうのだが(^_^;) それではあまりに芸が無さすぎる。 幾つか変わり種を示してみよう。 最も基本的な物を4つ挙げる。 演習問題も2つほど用意した。 ここまでは教科書にも大抵は書いてある内容だ。 本稿ではわかり易く噛み砕いた説明を心がけた。 細かい話も省いている。 そのため厳密さに欠けてしまった個所もある。 必要に応じて教科書などを参照されたい。
その後は普通の教科書ではあまり触れられない話題を載せた。 実際のシステム開発に応用する際の問題点である。 オートマトンの応用と言うと通常は文字列の解析 （字句解析） が主眼となる。 このような話題に触れている教科書は少ない。 ほんの一言二言であるが本稿では触れてみる事にした。 基礎教養として頭の片隅に置いていただければと思う。 読者諸氏のお役に立てれば幸いである。
「状態」 という言葉は面白いもので、 わかる人には感覚的にピピッと来るものがあるが、 わからない人には何だかわかったようでわからないようで妙に落着かない単語のようである。 「状態」 という単語を感覚的に理解しているのは電算関係に造詣の深い人に多い傾向があると思われる。 かく言う筆者も実は、 ピピッと来るようになったのは学校でオートマトンを習って以降の事だ。
と言ってもそんなに御大層なモノではない。 要は 「そのモノの内部の様子を表す単語」 である。 それ以上の意味は無い。
「状態」 という単語に関連して馴染み深い言葉を考えてみよう。 例えば 「健康状態」 が挙げられる。 履歴書などには健康状態について書く欄がある。 通常は良好などと書き込んだりする。 健康状態が良好でない場合とは即ち病気にかかっている場合だ。 それもひどくなると重病と言われ、 立って歩くのも辛くなる。 寝込んで額に氷嚢を当てる絵はマンガで良く見かける。
と言う訳で、 健康状態と言えばとりあえず次の3つの単語が出てくる。
ここで健康状態にはこの3つしかないものと仮定する。 更に次のような台本を考えてみよう。
この時に注意すべきは次のような点である。
ここで良好・病気・重病といった単語は健康という観点から体内の様子を分類し表現している。 このような時、 これらの単語によって象徴される内部の様子を 「状態」 と言う。 ある状態から別の状態へ移り変わる事は状態の 「遷移」 と呼ばれる。 ここで重要なのは次の2点である。
ところが世の中なかなか割り切れるものではない。 状態もしかり。 状態と一口に言っても実は中間状態があったり無限の状態があったり、 そんな事もあり得ないとは言い切れない。 が、 ここではそんなややこしい話は忘れよう。 今後は状態が有限である場合だけを扱う事にする。 即ち 「状態は3個ある」 などと具体的に個数を数える事が出来る場合である。 ソフトウェアへの応用を考えるならそれで十分だ。 と言うより、 オートマトンとして研究されているのは通常は状態数が有限のモノであるので、 ここでもその流儀に則ろうという事だ。
さて、 健康状態について語るのは結構だが、 文章でズラズラと書かれてもわかりにくい。 もう少しわかり易く表現したいものだ。 例えば次のような図にすると一目でわかるようになる。
┌─────┐┌─────┐ │ ↓│ ↓ ┏━┷┓ ┏━┷┓ ┏━━┓ ┃良好┃ ┃病気┃ ┃重病┃ ┗━━┛ ┗┯━┛ ┗┯━┛ ↑ │↑ │ └─────┘└─────┘
このような図を「状態遷移図」と呼ぶ。 これと同じ情報は次のような表にまとめる事も出来る。 このような表を「状態遷移表」と呼ぶ。
| 現状 | 次 |
|---|---|
| 良好 | 病気 |
| 病気 | 重病 |
| 病気 | 良好 |
| 重病 | 病気 |
状態が遷移する条件を明示する事もある。
不摂生 無理 ┌─────┐┌─────┐ │ ↓│ ↓ ┏━┷┓ ┏━┷┓ ┏━━┓ ┃良好┃ ┃病気┃ ┃重病┃ ┗━━┛ ┗┯━┛ ┗┯━┛ ↑ │↑ │ └─────┘└─────┘ 休 薬
| 現状 | 条件 | 次 |
|---|---|---|
| 良好 | 不摂生 | 病気 |
| 病気 | 無理 | 重病 |
| 病気 | 休 | 良好 |
| 重病 | 薬 | 病気 |
以上のような図や表によって象徴される、 状態とその間の遷移が定義された構造を 「状態機械」 と呼ぶ。
各々の状態の意味は考えない。 全く考えないのかといえばそうでもないのだが、 少なくとも理論上は状態として何を持ってきても構わない。 健康状態のように明らかな意味を持つモノを状態とする事もある。 何が何だかさっぱりわからないモノを状態とする事もある。 スゴロクの桝目のようなモノは後者の例と言えよう。 問題を解く為に最も便利なモノを状態として定義すればよい。
この問題は比較的有名である。 パズルとして解いた事のある方もいらっしゃる事と思う。 この問題は状態機械の考え方を利用すると機械的に、 かつ完璧に解く事が出来る。 その手順が最短なのか? 他に有効な手順は無いのか? そのような疑問にも答えられるのだ。 是非試みられたい。 勿論トンチの類は認められない(^_^;) 虎と野菜を舟に乗せて人は羊と共に泳ぎながら舟を引く、 などという回答は却下する…
似たような問題をもう一問。 登場人物が増える分、 パズルとしてはこちらの方が難易度は高い。 だが同様の考え方で完璧に解けるのは言うまでもない。
私の記憶が確かならば、 この問題は 「宣教師と人食い土人」 という題で知られている。 どこからどう見ても人種差別でしかないような文章である。 そんなものをそのまま載せる訳にもいかないので手を入れた。 御容赦いただきたい。
状態機械には遷移の条件の設定方法などによって幾つかの変種が考えられている。 それを議論する為には若干の準備が必要だ。 少々退屈な話になるかも知れないがお付き合い願いたい。
電算についての科学的な理論体系を 「計算機科学」 と呼ぶ。 その中に 「言語理論」 という分野がある。 そこでは言語の形式的な記述とその限界、 またその理論の応用などを議論する。 状態機械の基礎はその中で研究されている。 これから述べる変わり種もそこで提示されているものだ。 従ってその理解には言語理論特有の用語が若干、 どうしても必要になってくる。 ここでは最低限必要な内容だけを説明しよう。 詳しく知りたい方はその筋の教科書を参照のこと。
言語理論では 「言語」 とは文字列の集合の事である。 ここで言う集合とは数学的な意味での集合である。 と言ってもそんなに身構える必要は無い。 つまりは 「ある文字列がその言語に所属するかどうかを明確な基準ではっきりと判定できる」 という程度の意味である。
例えば英語という言語は次の2項目をもって定義できるだろう。
しかしこの定義はあまり厳密では無い。 使用する文字や記号類についてはとりあえず問題無かろう （具体的に100〜200文字程度を挙げれば十分であろう）。 一方で英文法を示せと言われると困難を伴う。 複雑なだけではない。 かなり曖昧さを含むものになってしまうからだ。 別な言い方をすれば、 文字列によっては英文であるかどうかの判断が、 見る人や時と場合などの条件によって変わってしまう恐れがあるという事だ。
そこで曖昧さを排除する為の策を考えなくてはならない。 英語ほど複雑な言語は今回は置いておく。 もっと単純な言語について考えてみよう。 そこで登場するのが状態機械である。 状態機械をどのように使うのかは後述するとして、 ここでは言語についてもう少し補足説明しておく。
本稿で考察の対象としているような簡単な言語とは例えば次のような物である。
およそこういう操作を組合せて得られる言語を想定している。 このような言語は 「正規言語」 または 「正則言語」 と呼ばれている。 UNIXなどで使われている 「正規表現」 によって表現できる文字列集合である。 （ちなみに 「拡張正規表現」 はこの範疇ではない）
最後に少し特殊な文字列と言語について触れておこう。
「長さ0の文字列」 というものが存在する。 というよりそのような文字列が存在するものとして話を進めると都合が良い。 作譜作業に精通していらっしゃる方ならばわかると思う。 このような文字列は 「空文字列」 （くうもじれつ） と呼ばれている。 それは言語理論でも同じこと。 こちらではεと書いて表現する。 研究者によってはλと表現する流儀もあるが本稿ではεで統一する。
などという言語も考えられる訳だ。
同様にして 「文字列を一つも含まない言語」 も考えておくと何かと便利だったりする。 数学的な集合で言う所の 「空集合」 （くうしゅうごう） に相当する。 おわかりだろうか？ どんな文字列を持ってきてもこの言語には所属していない。 このような言語を 「空言語」 （くうげんご） と呼んでφと書く。
注意。 空文字列だけからなる言語と空言語とを混同してはいけない。 空言語には空文字列すら所属しないのである。
いよいよオートマトンの話である。 状態機械に若干の手を加える。 ある文字列がある言語の要素かどうか判定できるようにしてみよう。 このような物を 「オートマトン」 と呼ぶ。 この章で説明する物は特に 「決定性有限オートマトン」 と呼ばれている。 有限なのは大体わかっていただけると思う。 何がどう決定性なのかは次章で明らかになる。
問題は状態機械にどのように手を加えてどう判定するかである。 これは次のようにする。
もう少し詳しく見てみよう。 まずは状態機械に次のような手を加える。 このような物を 「オートマトン」 と呼ぶ。
そして次のように動かす。
途中でどの状態を経過したかは全く関係無い。 とにかく最後の終了状態まで無事遷移する事が出来たかどうかだけが判断基準となる。 そしてこの言語に所属すると判定された事を 「この文字列はこのオートマトンによって受理された」 と言う。 逆にオートマトンによって受理されないのは次の2つの場合である。
さて、 「決定性」 に対して 「非決定性」 である。 非決定性と言うからにはきっと決める事が出来ないのだろう。 果たして何を決められないのだろう？
実は遷移先の状態を一つに決められないのである。 決定性オートマトンでは各々の文字に対して遷移先が必ず1つに決まっていた （または遷移先が存在しなかった）。 だが非決定性オートマトンでは、 とある状態でとある文字が来た時の遷移先が2つも3つも指定されていたり、 馬鹿な事言っちゃいけないよ！ と思わず叫びたくなってしまうような、 そんな事があり得ないとは言い切れない。
そんな得体の知れないモノをどうやったら動かす事が出来るのか。 カギは 「分身の術」 だ。 いや冗談を言っているのではない。
何やらすごい事をやっているようにも見える。 だがそれは見かけだけだ。 実際、 決定性有限オートマトンと非決定性有限オートマトンには文字列を受理する能力に差が無い。 つまりどういう事かというと、 非決定性有限オートマトンで表現できる言語は必ず決定性有限オートマトンでも表現できるのだ。 奴に出来る事なら俺にだって出来るという訳だ。
そんな似て非なる、 しかし能力的には変わらないような物をなぜわざわざ考えたのだろうか。 面倒なだけで実りが無いようにも見える。 が、 これにはちゃんと理由がある。
先に目的の言語を考えてからそれを受理するようなオートマトンを構成しようとした場合。 この場合は次のような手順を踏むのが定石となっている。
という寸法だ。 この手順に従えば機械的にオートマトンを構成できる。 が、 複雑になるのでここでは詳しくは触れない。
もう1つ。 状態数が圧倒的に少なくなる可能性があるのだ。 同じ言語を受理するのに決定性オートマトンよりもかなり 「簡単な」 物で処理できるかも知れない。
以上、 複雑な代わりに得られる物も大きいのだと理解して欲しい。
また新しい言葉が出てきた。 「ε遷移」… このεとは空文字列の事である。 と言う事は空文字列と関係のある状態遷移があるのだなと考えたなら、 それは正しい。 ズバリ空文字列に対しての状態遷移が存在する。 正確には 「存在する可能性がある」 というのが正しい。
空文字列と言う事は文字が無いと言う事だ。 元々は文字列の先頭から順に文字を取り出していた。 その文字によって状態が遷移していた筈だ。 その筈だったのに文字が無くても遷移するとは何事か？
ある文字を取り出した。
その文字に従って次の状態に遷移した。
次の文字を取り出した。
いやちょっと待て。
その前に更に次の状態に移ってしまおう。
それから文字に合わせて状態遷移。
とまあ、 こんな感じで動いていく訳だ。 「いやちょっと待て、 その前に更に次の状態に」 という動作をε遷移と呼ぶ。 空文字列 ε で遷移するからε遷移である。
「いやちょっと待て」 が無い事も、 勿論ある。 その判断基準はどこにあるのだろうか。 ここでもやはり非決定性である。 つまり 「いやちょっと待て」 を行う分身と、 ちょっと待たない分身を作る。 最終的にちょうど終了状態で終わった分身が一つでもあれば、 このオートマトンで文字列を受理できたと考える。 どの分身も全部終了状態にならなかった場合のみ受理されなかったと判定する。
言語の表現能力に関してはどうか。 例によって同じだったりする…。 ε遷移があろうが無かろうが変わらない。 奴に出来る事なら俺にも出来る。 奴に出来ない事は俺にも出来ない。 オートマトンで表現できる言語は表現できるし、 そうでない言語はやっぱり表現できないのだ。
ここで少し変形の方向を変えてみよう。 状態遷移の際に出力を伴う物を考える。 このようなオートマトンを 「出力付き有限オートマトン」 または 「順序機械」 と呼ぶ。
順序機械での興味は文字列の受理ではない。 入力に対してどのような出力が出てくるかが問題となる。 そのため終了状態は考えない。 入力がある限り延々と動き続ける。
入力や出力と言っても関数とはちょっと違う。 "world" という文字列を入力すると "hello" という文字列が出力される、 そういうのとは若干異なる。 いや見方によってはそれで正しいのだが…。 細かい事を言うと次のように動くのだ。
更に細かく言うと、 出力の決め方によって２種類に分類される。
Mealy型 : 状態遷移に対して出力が決まる。
ｌ／ｌ ┌───┐ │ │ ┏━┓ ┏━┓ ┏━┓ ┏┷┓ │ ┃０┠────→┃１┠────→┃２┠────→┃３┃←─┘ ┗━┛ ｗ／ｈ ┗━┛ ｏ／ｅ ┗━┛ ｒ／ｌ ┗┯┛ │ │ｄ／ｏ ↓ ┏━┓ ┃４┃ ┗━┛
| 現状 | 入力 | 出力 | 次 |
|---|---|---|---|
| ０ | ｗ | ｈ | １ |
| １ | ｏ | ｅ | ２ |
| ２ | ｒ | ｌ | ３ |
| ３ | ｌ | ｌ | ３ |
| ３ | ｄ | ｏ | ４ |
Moore型 : 遷移先の状態に対して出力が決まる。
ｌ ┌───┐ ｈ ｅ ｌ │ │ ┏━┓ ┏━┓ ┏━┓ ┏┷┓ │ ┃０┠────→┃１┠────→┃２┠────→┃３┃←─┘ ┗━┛ ｗ ┗━┛ ｏ ┗━┛ ｒ ┗┯┛ │ │ｄ ↓ ┏━┓ ｏ┃４┃ ┗━┛
|
|
ちなみにこの二者は異なっている。 入力として許される文字列の集合、 各入力に対する出力の文字列、 そのどちらか （あるいは両方） が違うのだ。 どう違うか考えるのは練習問題としておこう。 納得するまで何度でも見直して欲しい。
なお、 例によってMealy型とMoore型は相互に変換が可能である。 表現能力に差は無い。 問題に応じて使い易い方を用いれば良い。
例えば次のような内容が研究されている。 詳細は省略する。
次の制御を行う出力付きオートマトンを作れ。
ある物がｑという状態になるのを待って別の物の状態がｐになる。 いわゆる待合せ動作である。 これを状態機械で表現してみよう。
まずシステム全体としては次のような物を想定する。
これが次のように動作する。
状態遷移図は次のようになるだろう。
┏━━━┓ ┃０００┃←───────────┐ ┗┯┯┯┛ │ │││ │ Ａ＝１┌───────┘│└───────┐Ｂ＝１ │ ↓ │ ↓ │ ┏━━━┓ │Ａ＝Ｂ＝１ ┏━━━┓ │ ┃１００┃ │ ┃０１０┃ │ ┗━┯━┛ │ ┗━┯━┛ │ │ │ │ │ Ｂ＝１└───────┐│┌───────┘Ａ＝１ │ ↓↓↓ │ ┏━━━┓ │ ┃１１０┃ │ ┗━┯━┛ │ │ │ │Ｃ＝１ │ ↓ │ ┏━━━┓ │ ┃１１１┃ │ ┗━┯━┛ │ │ │ │Ａ＝Ｂ＝０ │ ↓ │ ┏━━━┓ │ ┃００１┃ │ ┗━┯━┛ │ └──────────────┘ Ｃ＝０
この図を見ればおわかりと思う。 システム全体の状態は 〔Ａの状態〕 〔Ｂの状態〕 〔Ｃの状態〕 を並べたモノとしている。 実際のシステムではこれがもっと大規模になる。 幾つもの物が並列に動いていて、 それらが相互に待合せを行っている。 それを一つの状態遷移図で表そうとすると状態の個数がとても多くなってしまう。
| システム全体の状態集合＝ | （構成要素Ａの状態集合 × Ｂの状態集合 × Ｃの状態集合 × …） − ありえない組合せ |
きちんとしたシステムを作ろうとするとエラーの対処も必要だ。 その結果 「ありえない状態」 は非常に少なくなってしまう。 構成要素が大量にある場合にはそれだけで困る事になる。 状態が多くなり過ぎて手に負えない。 これを 「状態の爆発」 と呼ぶ。
システム全体を一つの状態機械として扱う限り状態の爆発は避けられない。 別々の状態機械の集まりと捉えれば爆発は避けられるかも知れない。 その場合には待合せの為に特別な表記法が必要になる。 例えばUMLのアクティビティ図での並行遷移を表す記号などが挙げられる。
テストはシステム開発において非常に重要な位置を占める。 異常動作の有無を確認し、 使用に際しての正常動作を保証する。 その為には全状態に対しあらゆる入力を実際に与えてみなければならない。 これがどれだけ大変な作業かは前述の通り。 大規模システムでは事実上不可能となってしまう。
テスト工程の手間を減らすにはどうしたら良いか。 何よりも設計の段階で考慮するのが肝要だ。 例えば次のような対策が考えられる。
つまり巨大なシステムを巨大なまま漫然と取り扱っていては後が大変という事だ。 設計時にしっかりと考察して欲しい。 詳細はテスト作業に関する文献を探られたい。
状態機械は言語理論の退屈な小道具ではない。 システム開発に必須の基礎概念である。 重要なのはその感覚を身に付ける事だろう。 その為に必要な話は一通り説明できたと思う。
細かい話や厳密な話はすべて省いている。 概要を把握できたら教科書でしっかりと勉強して欲しい。 理論をきちんと学べば新たな発見があるだろう。
平成13年05月07日 初版
平成14年02月21日 厳密な話はすべて省く
平成15年04月27日 推敲
平成17年10月07日 XHTML適合。同時に文章を推敲