有限オートマトン

http://d.hatena.ne.jp/takemita/20061228/p1
　前回、順序機械というのをやったよ。システムがどの状態のときにどんな入力があると次にどんな状態になるかが決まっている機械だよ。それのムーア型というのがあったよ。これはシステムの出力が、そのときの状態によって決まる順序機械だよ。あわせていうと、どんな状態でどんな入力があるかによって、次にどんな出力があるかが決まるようなシステムだよ。
　入力記号を連続して入力すれば、それに応じてシステムの状態はピピピピピッと推移していき、またそれに応じて出力もピピピピピッと出るよ。このときの連続して打ち込んだ記号の連続を、入力記号列というよ。
　入力記号の集合と、出力記号の集合はあらかじめ定義されているけど、入力記号列は、入力記号を順番に並べて無限につくることができるよ。
　さてそこで、出力記号を「受理／非受理」（「1/0」でもいいよ）の2つに決めてしまうよ。そうすると、システムがとる状態は「受理（1）を出力する状態」と「非受理（0）を出力する状態」の2種類に分けられるよ。ある記号列を入力したら、システムの状態がピピピピピッと推移していって、受理を出力する状態で止まったらその記号列は受理され、そうでないと受理されないということだよ。受理されたときに

ニュウリョクヲニンシキシマシタ

と表示されるようにしておけば、このムーア型順序機械は、特定の記号列だけを認識するように設計された認識機械だとみなせるよ。
　こういう認識機械としてのムーア型順序機械を有限オートマトンというよ。
　初期状態をあらかじめ決めておいて、受理を出力する状態を最終状態と呼ぶことにすると、この有限オートマトンによって認識される記号列というのは、入力するとシステムが初期状態から双六のようにピピピピピッと状態を推移させていって最後に最終状態で止まるような記号列だよ。こういう記号列は複数ありうるけど、その集合は可能な入力記号列全体の集合からみると部分集合だよ。ある有限オートマトンが受理するすべての記号列の集合を、その有限オートマトンが受理（認識）する言語というよ。これは正則（正規）言語ともいうよ。
　受理する言語が等しい2つの有限オートマトンは互いに等価だというよ。