オートマトンと状態遷移図の読み方｜入力/出力を1文字ずつ追う方法【基本情報技術者試験】

まず結論

状態遷移図を使うオートマトンの問題は、入力を左から1文字ずつ読み、今いる状態から対応する矢印をたどるだけです。

矢印に

1/0

と書かれていたら、

1 / 0
↑   ↑
入力 出力

と読みます。

つまり、「1が入力されたら、その矢印をたどり、0を出力する」という意味です。

基本情報技術者試験では、まず次の手順を判断軸にします。

① 初期状態を探す
      ↓
② 入力を左から1文字読む
      ↓
③ その入力に対応する矢印を探す
      ↓
④ 「/」の右側を出力する
      ↓
⑤ 矢印の先の状態へ移動する
      ↓
次の入力へ

入力を一気に考えず、1文字ずつ「入力 → 出力 → 移動」を繰り返す。

直感的な説明

状態遷移図は、現在地によって次に進む道が変わる地図だと考えると分かりやすくなります。

例えば、現在S1にいるとします。

現在地
  S1
   │
   │ 1/0
   ▼
  S2

ここで入力が 1 なら、1/0 と書かれた道を進みます。

そのとき、

入力：1
出力：0
移動：S1 → S2

となります。

大切なのは、次の入力を読むときには、すでにS2に移動していることです。

図の記号を先に覚える

初めて状態遷移図を見る場合は、次の4つだけ先に確認します。

→ S1
  ↑
初期状態

(S1)
 ↑
状態

S1 ──1/0──→ S2
      ↑
    入力/出力

   ↻ 0/0
  (S1)
   ↑
自己ループ
（同じ状態に戻る）

黒い矢印など外側から入ってくる矢印が付いた状態が初期状態です。

定義

オートマトンは、現在の状態と入力に応じて、次の状態へ遷移する仕組みです。

状態遷移図では、その動きを状態と矢印で表します。

今回のように矢印へ「入力/出力」が書かれ、遷移するときに出力が決まる形式は、Mealy（ミーリ）型の有限オートマトンとして整理できます。

ただし、FEの問題を解くときは、名称を先に暗記するよりも、

矢印の「入力/出力」を読んで、1文字ずつたどれること

を優先すると解きやすくなります。

状態とは

状態は、その時点で機械が置かれている状況を表します。

S1 → 状態1
S2 → 状態2
S3 → 状態3

S1、S2という文字自体に特別な意味があるとは限りません。

遷移とは

ある状態から別の状態へ移ることを状態遷移といいます。

S1 ─────→ S2
     遷移

自己ループとは

矢印が同じ状態へ戻っている場合、その状態にとどまります。

  ┌─0/0─┐
  ↓     │
 ( S1 )─┘

これは、

S1で0を入力
↓
0を出力
↓
次もS1

という意味です。

どんな場面で使う？

入力列から出力列を求める問題

FEでは、例えば次のような入力列が与えられます。

入力
0 0 1 1 0

このとき、最初から全部の経路を頭の中で追う必要はありません。

次の表を作ると安全です。

回	現在の状態	入力	使用するラベル	次の状態
1	S1	0	0/0	S1
2	S1	0	0/0	S1
3	S1	1	1/0	S2

ポイントは、「現在の状態」を毎回更新することです。

実際の処理を表現する

オートマトンは、入力によって状態が変わる仕組みのモデル化に使えます。

例えば、

待機
↓ ボタンを押す
動作中
↓ 完了
待機

のように、装置やソフトウェアの状態変化を表現できます。

よくある誤解・混同

「1/0」は1÷0を表す

違います。

1/0
↓
入力1 / 出力0

割り算ではありません。

入力と出力を逆に読む

よくあるミスです。

入力 / 出力

なので、左が入力、右が出力です。

入力列をまとめて処理する

一度に全部を考えると、現在の状態を見失いやすくなります。

入力列：0 0 1 1 0
          ↑
      まずここだけ

1文字処理したら状態を更新し、それから次の1文字を読みます。

矢印を入力だけで選ぶ

入力が同じでも、現在の状態が違えば使う矢印も違うことがあります。

現在S1 ＋ 入力1
→ S1から出る「1」の矢印

現在S3 ＋ 入力1
→ S3から出る「1」の矢印

判断には「現在の状態」と「入力」の両方が必要です。

自己ループでは何も起こらない

自己ループでも入力を1文字消費し、指定された出力を行います。

違うのは、処理後も同じ状態にいることだけです。

まとめ（試験直前用）

最初に初期状態を確認する
矢印のラベルは 入力/出力
入力列は左から1文字ずつ読む
現在の状態から、入力に対応する矢印を選ぶ
「/」の右側を出力として記録する
矢印の先へ移動してから次の入力を読む
自己ループでも入力と出力の処理は行う
迷ったら「現在状態・入力・次状態・出力」の表を作る

状態遷移図は、入力を1文字読む → 出力する → 移動する、を繰り返す。