ようこそ。睡眠不足なプログラマのチラ裏です。

正規表現とオートマトン


オートマトン」とはなんじゃらほい。


簡単に言ってしまうと、なんらかの入力を逐次的に受け取り、
入力に従って内部の状態を遷移させる仮想的な機械のことである。
つまり、複数の状態とそれに応じた入力結果に対して、どのような処理を行うのか、
あらかじめ定められた関数で構成されたモデルのことをオートマトンと言います。*1


もっとも単純にモデル化したものとして、よく自動販売機が例にあげられる。
自動販売機をオートマトンとすると、入力は硬貨です。自動販売機は硬貨を受け付けるたびに
内部の状態(投入された合計金額)を遷移させていき、それが飲み物の金額に達したとき、
飲物を選ぶためのボタンが点灯し選択権を得ることができます。


自販機で120円の缶コーヒーを買うのに、100円入れました。まだ買えません。
さらに10円いれました。まだ買えません。さらに10円入れました。買えます。
こんな感じのシステムがオートマトンっちゅーやつです。シンプル。


正規表現が特定の文字列にマッチするかどうかは、FA*2によって調べることができる。
そのためにはまず、正規表現をFAに変換します。続いて、このFAに対して調べたい文字列を与えます。
FAは文字列を1文字ずつ読み取り、読み取った文字列に従って内部の状態を遷移させていきます。


遷移結果が受理状態に達すれば、この正規表現は入力として受け取った文字列に
マッチしたと判断することができます。現在「正規表現」と呼ばれているものは
FAを起源としたクリーネの正規表現よりも、遥かに複雑ですが、
正規表現の動作原理の基本がオートマトンという点は、今現在も変わりません。

*1:状態に応じた振る舞いを持つって意味では、オブジェクト指向におけるクラスもオートマトン的であるっちゃー、あるかもね。

*2:Finite Automaton(有限オートマトン