オートマンって?

　もしかしたら、質問カテゴリが違うのかもしれませんが、それほどわからないんです。
　数学(?)や、情報工学で出てくる、「オートマン」ってなんなんでしょうか?いろんな検索サイトで調べてみましたがよくわからないんです。
　非常に初心者な質問で申し訳ありませんが、よろしくお願いします。

No.3 ベストアンサー 回答者： stomachman 回答日時： 2003/03/25 13:59

オートマトン（automaton, 複数形はautomata）、直訳すれば「自動機械」ですけど、レッキとした数学です。

ソフトウエアの分野では「状態遷移図」と言った方が通りが良いです。
オートマトンは「メモリが制限されているソフトウエアのモデル」になる。特に人工的な言語の文法（ただし、意味は一切無視）と対応していて、だからプログラミング言語の文法を定義したりコンパイラを作る際に使われます。オートマトンは、メモリの制限の付け方によって幾つかの種類があり、最も簡単なオートマトンは「有限状態機械(finite state automaton)」と呼ばれます。

　有限状態機械は幾つかの「状態」を持っています。状態のうちの一つは「初期状態s0」で、また状態のうちの一つは「終状態se」と呼ばれます。有限状態機械はどれかひとつの「状態」に在り、その状態を「現在の状態s」と言います。そして、「入力i」を受け取ると、iとsだけから一意的に、「出力O(i,s)」と次の状態「N(i,s)」が決まり、O(i,s)を出力して、「現在の状態」がN(i,s)に変化します（状態遷移）。
　プログラム風に書けば

s:=s0
While (入力がまだある）
i:= input()
output(O(i,s))
s:= N(i,s)
end while
display(s)

って感じです。だから、状態の集合S（ただし有限集合）、 初期状態s0, 終状態se, 入力の集合I（ただし有限集合。Iを「アルファベット」と呼びます）, 出力の集合X（ただし有限集合）, I×S→Xの関数O(i,s)（出力関数と言います）,I×S→Sの関数N(i,s)（状態遷移関数と言います）を決めると、これで有限状態機械が一つ決まります。
これはまた、有向グラフで表すこともできます。状態をグラフのノードとします。状態の個数だけノードが出来ます。N(i,s1)=s2 となるようなiが存在する場合、s1からs2へのアークを描きます。そして、そのアークにiとO(i,s)を書き添えておきます。このグラフを状態遷移図と呼びます。

簡単な有限状態機械の例を見てみましょう。
S={sO,sE}
s0=sE
se=sE
I={0,1}
X={w,m}
N(0,sO)=sO
N(1,sO)=sE
N(0,sE)=sE
N(1,sE)=sO
O(0,sO)=m
O(1,sO)=w
O(0,sE)=m
O(1,sE)=m
まずN(i,s)に注目します。0か1が次々と入力されると、状態sOとsEを行ったり来たりする。0が入力されたときには状態は変化しません（N(0,s)=s）し、1が入力されると状態が変化する（N(1,s)≠s）。初期状態はsEですから、偶数個の1が入力された後ではs=sEになり、奇数個の1が入力された後ではs=sOになることは自明です。つまり、このオートマトンは1の個数が偶数なのか奇数なのかを調べる能力を持っています。
入力が尽きた最後に終状態se(=SE)になっていたとき、「オートマトンは入力を受理(accept)した」と言います。ですから、このオートマトンは「1が偶数個含まれている入力を受理するオートマトンである」。
オートマトンが受理するような入力を「語(word)」と呼びます。オートマトンを一つ決めると、語の集合（無限集合かもしれません）が決まります。この集合が、「オートマトンが定義する言語」です。上記のオートマトンは「偶数個の1を含む0,1の列」という「言語」を定義しています。（もちろん、語の意味については何も言っていません。）
次にO(i,s)に注目します。wを「ワンと鳴く」、mを「黙っている」という意味だとすると、s=sO, i=1の時だけ「ワンと鳴く」。ワンと鳴く回数を数えてみると、入力された1の個数の丁度半分か、半分より1回少ない訳です。だからこのオートマトンは1の個数を2で割るという機能も持っています。

O(i,s)としては、外部にある機械を操作する命令を出力すると考えても良い。外部にある機械として、たとえば数値を保持するレジスターA,Bがあって、AとBの和を計算しBに入れる回路がついている、なんてのを考える。
Xとして{Aを0にする、AからBへデータを転送する、A+BをBに入れる、数字をAに付け加える}があり、Iとして｛クリアキー、数字キー、＋キー｝があるとすれば、「足し算しかできない電卓」の動作を表現できます：
・入力が＋キーだったら、「A+BをBに入れる」。
・入力がクリアキーなら、「Aを0にする」。
・ただし入力が２回続けてクリアキーなら、「Aを0にする」そして「AからBへデータを転送する」。
・入力が数字（どの数字かは気にしない）だったら、その「数字をAに付け加える」。
・ただし＋キーのあと数字キーが来たら、「Aを0にする」そして「AからBへデータを転送する」。
という動作を実現するのに、幾つ状態を用意してどんな状態遷移関数を決めておけばよいか、というのはちょっとした練習問題です。
また、＋キーを押すたびに、電卓の操作として意味のある一区切りになりますから、
・＋キーを押した時に終状態seに状態遷移する
ようにしておけば、「語」が電卓の操作という「意味」を持つことになります。

有限状態機械では出来ることが非常に限られています。そこで、プッシュダウン・スタック(push-down stack)をメモリとして持つスタックオートマトンを考えますと、このオートマトンは「文脈自由文法(context free grammer)」という種類の文法と対応し、具体的には、((())()()))のようなカッコの列がうまく対応しているかどうかをチェックする能力を持ちます。この能力によって、数式やプログラミング言語を定義できますので、実際に多くのコンパイラに利用されています。

数学の問題としては、「ある言語を丁度受理するようなオートマトンを作る」ですとか、「あるオートマトンに旨く入力を与えて終状態に持っていくにはどうすれば良いか」ですとか、「オートマトンの中身は分からなくて、入力に対してどんな出力をするか、というデータだけ多量に収集した場合、オートマトンの中身を推定する」ですとか、実用の上で重要な問題が考えられます。

教科書は「オートマトン」のほか、「状態遷移図」「形式言語」「形式文法」などのキーワードで探してみると良いと思います。

No.2 回答者： ymmasayan 回答日時： 2003/03/24 14:32

「オートマトン」はコンピュータの仕組みを極限まで単純化した数学的なモデルです。

入力データと単純な処理装置が有って、どんな条件のときにどんなソフト処理が出
来るかを研究します。
「オートマトン」で検索して見てください。

No.1 回答者： wolv 回答日時： 2003/03/24 14:23

あんまり詳しくないので説明はできませんが、

「オートマン」ではなく、
「オートマトン」ですね。

単なるミスタイプだったらごめんなさい。