前回、誤差の種類を整理しました。今回は、少し毛色の変わったテーマ「オートマトン・状態遷移図」の読み方を整理します。
オートマトンとは
オートマトンとは、いくつかの「状態」と、状態と状態を結ぶ「遷移(移り変わり)」の組み合わせで、ものごとの動きを表現するモデルのことです。
例えば、自動販売機や信号機のように、「今どの状態にいるか」によって、次に何が起きるかが決まる仕組みを考えるときに使われます。基本情報技術者試験では、この考え方を図で表した「状態遷移図」を読み解く問題が出題されます。
状態遷移図の見方
状態遷移図では、状態を丸(円)で表し、ある状態から別の状態への移り変わりを、矢印で表します。矢印には、その移り変わりが起こる条件(入力)が書かれています。
読み方のポイントは、次の２つです。
- 今、どの状態(丸)にいるかを常に意識する
- 矢印に書かれた条件が発生したときだけ、次の状態に移る
複数の矢印が入り乱れていると混乱しやすいのですが、「今いる状態」から出ている矢印だけに注目すれば、迷わず追えるようになります。
トレースしてみる練習
状態遷移図の問題は、疑似言語のトレースと同じように、実際に手を動かして追ってみるのが近道だと感じています。
自分は、「状態:○○」という形でメモを取りながら、入力が与えられるたびに、どの矢印をたどって次の状態に移ったかを、１つずつノートに書き出す練習をしています。頭の中だけで図を目で追おうとすると、途中でどこにいたか分からなくなることが多いためです。
出題されやすいパターン
科目Aでは、次のようなパターンで出題されることが多いようです。
- ある一連の入力が与えられたとき、最終的にどの状態にたどり着くかを問う
- 特定の状態に到達するために、どのような入力の並びが必要かを問う
どちらのパターンでも、状態と矢印の対応を正確に読み取ることが前提になるので、慌てずに１つずつ確認する姿勢が大切だと感じています。
学習してみた感想
オートマトンという言葉自体は難しそうに聞こえますが、実際の中身は「今の状態」と「矢印の条件」を丁寧に追うだけのシンプルな作業でした。科目Bのアルゴリズムのトレース練習にも近い感覚があり、早めにこの「手を動かして追う」習慣をつけておいてよかったと感じています。
次回は、科目Bの疑似言語に戻り、条件分岐(if・else)の疑似言語表現を整理します。
