日本大百科全書(ニッポニカ) 「オートマトン」の意味・わかりやすい解説
オートマトン
おーとまとん
automaton
ギリシア語のautòmatos（自ら動くの意）からきたことばといわれる。古くは、人や動物の動きをまねする装置のことで、やがてロボットということばで置き換えられた。現在オートマトンは、自動機械の抽象的モデルとして、情報科学の一つの研究対象をさしている。オートマトンの素材としては、思考上の計算機としてのチューリング機械（1936）、神経回路網の数学的モデル（1943）、順序回路の抽象化としての順序機械の理論（1955）などがあった。オートマトンでは、時間は0、1、2、……、t、……と不連続に刻まれ、各瞬間tにおいて、有限個の内部状態のどれかをとる。有限個の内部状態のなかには、一つの初期状態と、いくつかの最終状態があり、初期状態で動き始め、止まるのは最終状態である。チューリング機械は、升目にくぎられた、左端をもつが右方向にいくらでも長く伸びているテープと、本体と、テープ上に記号を書いたり消したり読み取ったりするヘッドという部分からなっている。この升目一つには、一つの記号が書き込めるものとする。それぞれのチューリング機械では、現在の内部状態と、見ている記号によって、次の瞬間における動作と内部状態が決まっている。動作には、現在見ている記号を他の記号に書き換える、ヘッドを右、あるいは左に升目一つ分だけ動かす、という三つがある。テープ上に、左端から有限の文字列が書かれていて、機械がこの文字列を、初期状態で左端を見、定められた規則に従って順次内部状態を変えながら三つの動作のどれかを行い、最終状態に到達すれば、最初にテープ上に書かれた文字列は、この機械によって受理されたという。チューリング機械は、所要時間と記憶容量になんらの制限を置かず、電子計算機の忠実なモデルとはいえない。そこで、時間と空間とに制限を置き、より忠実なモデルとして考えられたのが有限オートマトンあるいは単にオートマトンといわれるものである。
［西村敏男］
有限オートマトン
それぞれの有限オートマトンには、有限個の入力記号が定められていて、現在の内部状態と入力記号によって、次の瞬間における出力と内部状態が決定される。ある有限の入力文字列の先頭の文字を初期状態で入力し、1文字ずつ順番に入力するとともに内部状態を変え、この文字列を読み終わったとき最終状態に到達すれば、この文字列はこのオートマトンによって受理されたという。入力記号の集合、内部状態の集合、初期状態、最終状態の集合、次の瞬間の内部状態を、いろいろ与えることによって、さまざまな有限オートマトンをつくることができる。一つの有限オートマトンが与えられると、それによって受理される文字列の一つの集合が定まる。有限オートマトンによって受理される文字列の集合を正規集合ともいう。有限オートマトンは、しばしば状態遷移図または推移図によっても表される。この有限オートマトンに、プッシュダウン・スタックという特別の記憶装置をつけた機械を、プッシュダウン・オートマトンという。一般にプッシュダウン・スタックは、入力記号と異なる記号からなる有限文字列を記憶する。この機械は、プッシュダウン・スタックに特定の初期記号を置き、初期状態で動き始める。各瞬間において、現在の内部状態と、プッシュダウン・スタックの最左端の文字と入力とによって、次の瞬間における出力と内部状態およびプッシュダウン・スタックの最左端の文字がいかなる文字列（空列の場合もある）によって置き換えられるかが決定される。機械が止まるのは、最終状態に到達したとき、あるいはプッシュダウン・スタックが空になったときである。有限文字列を読み込み、読み終わったとき機械が止まるならば、その文字列はこの機械に受理されたという。
［西村敏男］
数理言語論との関係
このようにオートマトンは、1950年代の後半に入り、電子計算機の抽象的モデルとしての姿を確立した。と同時に、電子計算機のプログラム言語と、そのコンパイラ（機械語に翻訳させるためのプログラム）の作成を通じて、数理言語理論と不即不離の関係をも生じるようになり、情報科学の中心的話題の一つともなった。すなわち、ある正規文法によって生成される言語に対しては、その言語と同じ集合を受理する有限オートマトンをつくることができる。また逆に、有限オートマトンによって受理される正規集合に対しては、それと同じ言語を生成するような正規文法を与えることができる。同じことは、文脈自由言語とプッシュダウン・オートマトンの間にも成り立つ。さらに、句構造文法とチューリング機械の間にも同様の関係がある。文脈依存文法については、チューリング機械のテープの長さに、ある制限をつけた線形有界オートマトンとの間に同様の関係がある。
［西村敏男］
『ホップクロフト、ウルマン著、野崎昭弘他訳『言語理論とオートマトン』（1971・サイエンス社）』▽『本多波雄著『オートマトン・言語理論』（1972・コロナ社）』
