オートマトン（automaton）

分類

テクノロジ系 基礎理論

出る試験

基本情報応用情報

重要度

★★★☆☆

もう少し詳しい説明

オートマトンは、入力を1文字ずつ読んで、状態を移していく機械を数学的に表したモデルです。「自動機械」という意味の言葉で、試験に出るのは有限オートマトン、つまり状態の数が決まっているものです。

下の図は「1 が2個続けて現れる文字列」だけを受理する機械です。

覚えているのは「いまどこにいるか」だけ

この機械には、これまで読んだ文字を書き留めておく場所がありません。いまどの状態にいるか、それが記憶のすべてです。

S1が持っている情報は「直前が1だった」という一事だけです。何文字目なのかも、その前に何が来たかも持っていません。それでも「1が2個続いたか」は判定できます。何を覚えておけば足りるかを絞り込む。これがオートマトンを作るということです。

受理されるか確かめる手順

開始状態から、1文字ずつ指でたどるだけです。計算も暗記も要りません。

「0110」を入れてみます。

S0 ─0→ S0 ─1→ S1 ─1→ S2 ─0→ S2

最後がS2なので、受理されます。「0101」ではこうなります。

S0 ─0→ S0 ─1→ S1 ─0→ S0 ─1→ S1

最後がS1なので、受理されません。見るのは読み終わった場所だけです。途中で受理状態を通っていても、最後にそこにいなければ受理されません。

同じことを表でも書ける

状態遷移図と同じ内容は、状態遷移表の形でも書けます。どちらの形で出題されても読めるようにしておきます。

表のほうが書き落としに気づきやすいという利点があります。状態が3つ・入力が2種類なら、埋まるべきマスはちょうど6つ。1つでも空いていれば、図に描き忘れた矢印があるということです。

逆に図のほうは、どこを通ると受理へ行けるかという道筋が目で追えます。試験では図を表に直す、表から図を読む、という行き来が問われます。

何に使われているのか

身近なところでは、プログラムの文字列を単語に切り分ける処理（字句解析）がこの考え方で作られています。文字を1つずつ読みながら「いま数値の途中」「いま文字列の途中」と状態を移し、区切りが来たら1語として切り出します。

自動販売機も同じ形で説明できます。状態は「投入額0円」「50円」「100円」、入力は投入された硬貨、受理状態は「商品を出せる額に達した」です。いまの状態と、次に来た1つの入力だけで、次の状態が決まる。この形に当てはまるものは、すべてオートマトンとして書けます。

試験ではこう出る

科目A（旧・午前）の基礎理論で出ます。いちばん多いのは、状態遷移図を与えて「受理される文字列はどれか」を選ばせる形です。選択肢を1つずつたどれば必ず解けるので、時間さえかければ落としません。

ほかに、状態遷移図と状態遷移表を読み替えさせる形、そのオートマトンが受理する文字列がどういうものかを言葉で言い当てさせる形があります。応用情報では、字句解析や正規表現との関係まで広がります。

解くときの注意は2つです。

まず開始状態がどれかを確かめること。試験の図では、どこの状態からも出ていない短い矢印が外から1本だけ刺さっているのが開始です。「start」や「開始」と書き添えてあることもあります。入ってくる矢印が無い状態が開始とは限りません（上の図のS0にも、S1から戻る矢印が入っています）。

もう1つは、読み終わった場所だけを見ること。途中の通り道は関係ありません。

   S1 --0--> S0 ／ S1 --1--> S2
   S2 --0,1--> S2（受理）
 0〜8文字の全512通りで「11 を含む」と受理が一致することを確認済み。

 出題範囲：基本情報技術者試験シラバス ver9.1 中分類1 基礎理論 ＞ 情報に関する理論
 「有限オートマトンの概念，形式言語との関係，状態遷移表，状態遷移図を理解する。」 -->

関連する用語

BNF

正しい書き方のほうを定義する記法。オートマトンは、書かれたものが正しいかを判定する側

正規表現

文字列の形を短い式で表す書き方。有限オートマトンで判定できる範囲とちょうど一致する

フリップフロップ

1ビットを覚える回路。いまの状態と入力で次の状態が決まる、という組み立ては同じ

ホワイトボックステスト

プログラムの中の通り道を網羅するテスト。状態の移り方を図にして数える点が似ている

ミニクイズ

この分野をまとめて解く → 基礎理論と情報メディアのミニテスト（全39問）

最終更新：2026-10-04