Automaton - otomaton (English spelling) automaton

Japanese: オートマトン - おーとまとん（英語表記）automaton

The word is said to come from the Greek word autòmatos (meaning to move by itself). In the past, it meant a device that imitated the movements of humans and animals, and was eventually replaced by the word robot. Currently, automaton refers to one of the research subjects in information science as an abstract model of an automatic machine. The source material for automaton includes the Turing machine (1936) as a thinking computer, the mathematical model of neural networks (1943), and the theory of sequential machines as an abstraction of sequential circuits (1955). In an automaton, time is recorded discontinuously as 0, 1, 2, ..., t, ..., and at each moment t, it takes one of a finite number of internal states. Among the finite number of internal states, there is one initial state and several final states, and it starts moving in the initial state and stops in the final state. A Turing machine consists of a tape that is nailed to the squares and has a left end but extends indefinitely to the right, the main body, and a head that writes, erases, and reads symbols on the tape. One symbol can be written in each square. In each Turing machine, the action and internal state at the next moment are determined by the current internal state and the symbol being viewed. There are three actions: rewriting the currently viewed symbol with another symbol, and moving the head one square to the right or left. A finite string of characters is written on the tape from the left end, and the machine looks at the left end of the string in the initial state, and performs one of the three actions while changing the internal state according to a set rule. If it reaches the final state, the string originally written on the tape is said to have been accepted by the machine. Turing machines do not place any restrictions on the time required or memory capacity, and therefore cannot be said to be a faithful model of an electronic computer. Therefore, a more faithful model that places restrictions on time and space is called a finite automaton, or simply an automaton.

[Toshio Nishimura]

Finite automaton

Each finite automaton has a finite number of input symbols, and the output and internal state at the next moment are determined by the current internal state and the input symbols. The first character of a finite input string is input in the initial state, and the internal state is changed as each character is input in order. If the final state is reached when the string is read, the string is said to be accepted by the automaton. Various finite automatons can be created by providing various sets of input symbols, sets of internal states, initial states, sets of final states, and internal states at the next moment. When a finite automaton is given, a set of strings that it accepts is determined. The set of strings that a finite automaton accepts is also called a normal set. Finite automatons are often represented by state transition diagrams or transition diagrams. A machine that combines a special storage device called a pushdown stack with this finite automaton is called a pushdown automaton. In general, a pushdown stack stores a finite string that consists of symbols different from the input symbol. This machine places a specific initial symbol in the pushdown stack and starts operating in the initial state. At each instant in time, the current internal state, the leftmost character of the pushdown stack, and the input determine what string (which may be the null string) will replace the output, internal state, and leftmost character of the pushdown stack at the next instant. The machine stops when a final state is reached or when the pushdown stack is empty. A finite string is read, and if the machine stops when it has finished reading, the string is said to be accepted by the machine.

[Toshio Nishimura]

Relationship with mathematical linguistics

Thus, automata were established as an abstract model of electronic computers in the latter half of the 1950s. At the same time, through the creation of computer programming languages and their compilers (programs for translating them into machine code), they also came to be inextricably linked to mathematical language theory, becoming one of the central topics in information science. That is, for a language generated by a regular grammar, it is possible to create a finite automaton that accepts the same set as that language. Conversely, for a regular set accepted by a finite automaton, it is possible to give a regular grammar that generates the same language. The same holds true between context-free languages and pushdown automata. Furthermore, there is a similar relationship between phrase structure grammars and Turing machines. For context-sensitive grammars, there is a similar relationship between linear bounded automata with a certain restriction on the length of the tape of a Turing machine.

[Toshio Nishimura]

"Language Theory and Automata" by Hopcroft and Ullman, translated by Akihiro Nozaki et al. (1971, Science Press) " "Automata and Language Theory" by Namio Honda (1972, Corona Press)

[Reference] | Turing machine

automaton
©Shogakukan ">

automaton

Source: Shogakukan Encyclopedia Nipponica About Encyclopedia Nipponica Information | Legend

Japanese:

ギリシア語のautòmatos（自ら動くの意）からきたことばといわれる。古くは、人や動物の動きをまねする装置のことで、やがてロボットということばで置き換えられた。現在オートマトンは、自動機械の抽象的モデルとして、情報科学の一つの研究対象をさしている。オートマトンの素材としては、思考上の計算機としてのチューリング機械（1936）、神経回路網の数学的モデル（1943）、順序回路の抽象化としての順序機械の理論（1955）などがあった。オートマトンでは、時間は0、1、2、……、t、……と不連続に刻まれ、各瞬間tにおいて、有限個の内部状態のどれかをとる。有限個の内部状態のなかには、一つの初期状態と、いくつかの最終状態があり、初期状態で動き始め、止まるのは最終状態である。チューリング機械は、升目にくぎられた、左端をもつが右方向にいくらでも長く伸びているテープと、本体と、テープ上に記号を書いたり消したり読み取ったりするヘッドという部分からなっている。この升目一つには、一つの記号が書き込めるものとする。それぞれのチューリング機械では、現在の内部状態と、見ている記号によって、次の瞬間における動作と内部状態が決まっている。動作には、現在見ている記号を他の記号に書き換える、ヘッドを右、あるいは左に升目一つ分だけ動かす、という三つがある。テープ上に、左端から有限の文字列が書かれていて、機械がこの文字列を、初期状態で左端を見、定められた規則に従って順次内部状態を変えながら三つの動作のどれかを行い、最終状態に到達すれば、最初にテープ上に書かれた文字列は、この機械によって受理されたという。チューリング機械は、所要時間と記憶容量になんらの制限を置かず、電子計算機の忠実なモデルとはいえない。そこで、時間と空間とに制限を置き、より忠実なモデルとして考えられたのが有限オートマトンあるいは単にオートマトンといわれるものである。

［西村敏男］

有限オートマトン

それぞれの有限オートマトンには、有限個の入力記号が定められていて、現在の内部状態と入力記号によって、次の瞬間における出力と内部状態が決定される。ある有限の入力文字列の先頭の文字を初期状態で入力し、1文字ずつ順番に入力するとともに内部状態を変え、この文字列を読み終わったとき最終状態に到達すれば、この文字列はこのオートマトンによって受理されたという。入力記号の集合、内部状態の集合、初期状態、最終状態の集合、次の瞬間の内部状態を、いろいろ与えることによって、さまざまな有限オートマトンをつくることができる。一つの有限オートマトンが与えられると、それによって受理される文字列の一つの集合が定まる。有限オートマトンによって受理される文字列の集合を正規集合ともいう。有限オートマトンは、しばしば状態遷移図または推移図によっても表される。この有限オートマトンに、プッシュダウン・スタックという特別の記憶装置をつけた機械を、プッシュダウン・オートマトンという。一般にプッシュダウン・スタックは、入力記号と異なる記号からなる有限文字列を記憶する。この機械は、プッシュダウン・スタックに特定の初期記号を置き、初期状態で動き始める。各瞬間において、現在の内部状態と、プッシュダウン・スタックの最左端の文字と入力とによって、次の瞬間における出力と内部状態およびプッシュダウン・スタックの最左端の文字がいかなる文字列（空列の場合もある）によって置き換えられるかが決定される。機械が止まるのは、最終状態に到達したとき、あるいはプッシュダウン・スタックが空になったときである。有限文字列を読み込み、読み終わったとき機械が止まるならば、その文字列はこの機械に受理されたという。

［西村敏男］

数理言語論との関係

このようにオートマトンは、1950年代の後半に入り、電子計算機の抽象的モデルとしての姿を確立した。と同時に、電子計算機のプログラム言語と、そのコンパイラ（機械語に翻訳させるためのプログラム）の作成を通じて、数理言語理論と不即不離の関係をも生じるようになり、情報科学の中心的話題の一つともなった。すなわち、ある正規文法によって生成される言語に対しては、その言語と同じ集合を受理する有限オートマトンをつくることができる。また逆に、有限オートマトンによって受理される正規集合に対しては、それと同じ言語を生成するような正規文法を与えることができる。同じことは、文脈自由言語とプッシュダウン・オートマトンの間にも成り立つ。さらに、句構造文法とチューリング機械の間にも同様の関係がある。文脈依存文法については、チューリング機械のテープの長さに、ある制限をつけた線形有界オートマトンとの間に同様の関係がある。

［西村敏男］

『ホップクロフト、ウルマン著、野崎昭弘他訳『言語理論とオートマトン』（1971・サイエンス社）』▽『本多波雄著『オートマトン・言語理論』（1972・コロナ社）』

[参照項目] | チューリング機械

オートマトン

出典　小学館　日本大百科全書(ニッポニカ)日本大百科全書(ニッポニカ)について　情報 | 凡例

<<: Otomí (English spelling)

>>: Otomae - Otomae