基本情報のオートマトンと状態遷移図は、図の見た目が独特なので、最初は「どこから読めばいいのか分からない」と感じやすい分野です。丸と矢印だけを見ると簡単そうなのに、入力列が長くなると今どの状態にいるのか見失ってしまうことがあります。
ただ、オートマトンの問題でやることはかなりシンプルです。初期状態から始めて、入力を左から1文字ずつ読み、矢印の条件に従って状態を移動し、最後に受理状態へいるかを確認します。
この記事では、基本情報のオートマトンと状態遷移図について、用語の意味、図と表の読み分け、入力列を追う手順、間違えやすいポイントまで順番に整理します。
- オートマトンは入力に応じて状態を変える仕組み
- 状態遷移図は丸と矢印で動きを表した図
- 入力列は左から1文字ずつ追う
- 最後に受理状態へいるかで判定する
基本情報のオートマトン基礎
オートマトンとは何か
オートマトンとは、入力を受け取るたびに状態を変えていく数学的なモデルです。基本情報で出てくる範囲では、難しい理論名を深追いするよりも、「いまいる状態」と「次の入力で移動する先」を追えるかどうかが重要になります。
たとえば、自動販売機をイメージすると分かりやすいです。お金を入れる前、100円入った後、商品を選べる状態など、機械の内部には段階があります。ボタンを押す、硬貨を入れる、取り消すといった入力によって、次の状態へ移動します。このように、入力と状態変化を組み合わせて考えるのがオートマトンです。
試験問題では、細かい証明を求められるというより、与えられた状態遷移図や状態遷移表から、入力列を入れたときにどの状態へ到達するか、どの文字列が条件を満たすかを選ぶ形が中心です。まずは図を怖がらず、順番に追跡する対象として見るのが第一歩ですね。
もう少し試験寄りに言うと、オートマトンは「条件を満たす文字列を見分ける装置」と考えると理解しやすくなります。入力列が規則に合っていれば受理状態で終わり、規則に合っていなければ別の状態で終わります。正規表現や形式言語の入口にある考え方ですが、基本情報ではまず図を読めれば十分です。
苦手意識がある人は、丸の数や矢印の多さに注目しすぎています。見るべきなのは常に現在地だけです。今AにいるならAから出る矢印だけを見る、今Bに移ったならBから出る矢印だけを見る。この姿勢に変えるだけで、問題がかなり小さく見えてきます。
つまり、オートマトンは「図全体を覚える」分野ではなく、「次に進む先を選ぶ」分野です。この捉え方に変えると、初見の図でも手順通りに処理できます。
有限オートマトンの用語
基本情報で扱うオートマトンは、多くの場合「有限オートマトン」として出てきます。有限という言葉の通り、取り得る状態の数が限られている仕組みです。状態がA、B、Cの3つだけなら、入力を何回読んでも、必ずA、B、Cのどれかにいます。
用語を知らないまま問題に入ると、どの丸から始めるのか、どの丸で終わればよいのかが曖昧になります。そこで、最初に最低限の言葉を押さえておきましょう。特に「初期状態」と「受理状態」は、選択肢を判断する最後の決め手になります。
| 用語 | 意味 | 見る場所 |
|---|---|---|
| 状態 | 機械が今いる段階 | 丸で表される |
| 初期状態 | 入力を読む前の出発点 | 外から矢印が入る丸 |
| 遷移 | 入力によって状態が変わること | 丸同士を結ぶ矢印 |
| 受理状態 | 条件を満たしたと判定する状態 | 二重丸で表されることが多い |
| 入力列 | 順番に読む記号の並び | 問題文に与えられる |
この表の言葉が分かれば、問題文の読み取りで大きく迷うことは減ります。最初の丸を見つけ、矢印の条件を見て、最後に受理状態かどうかを確認する。この流れだけでも、かなり多くの問題に対応できます。
特に初期状態は見落としやすいです。図の左側にある丸から始まるとは限らず、外側から矢印が入っている丸や、問題文で「状態Sから開始する」と指定された丸が出発点になります。左端の丸をなんとなく選ぶと、最初から違うルートを追うことになります。
受理状態も同じで、必ずしも図の右端にあるとは限りません。二重丸が複数あることもありますし、問題文で受理状態が文章指定されることもあります。用語は暗記で終わらせず、図のどこを見ればよいかまでセットで押さえるのが実戦的です。
用語問題として聞かれた場合でも、この対応関係を思い出せば迷いにくくなります。丸、矢印、出発点、終点という形で視覚的に覚えておくと、文章だけの選択肢にも対応しやすいです。
状態遷移図と表の違い
オートマトンは、状態遷移図で出ることもあれば、状態遷移表で出ることもあります。状態遷移図は丸と矢印で関係を示すため、流れを直感的に見やすいのが特徴です。一方、状態遷移表は、現在の状態と入力の組み合わせから、次の状態を表で確認できます。
どちらが出ても、考えている中身は同じです。図なら矢印をたどり、表なら行と列の交点を見るだけです。苦手な人は、図を見た瞬間に全体を理解しようとして混乱しますが、実際には「現在の状態」と「次の入力」だけを見れば十分です。
| 形式 | 得意なこと | 注意点 |
|---|---|---|
| 状態遷移図 | 全体の流れを見やすい | 矢印の条件を読み落としやすい |
| 状態遷移表 | 次の状態を機械的に探せる | 行と列を取り違えやすい |
科目Bのアルゴリズム問題でトレース表を書く感覚に近いので、状態遷移表が出たときは、現在地を1行ずつ更新していくと安定します。トレースの考え方が不安な場合は、基本情報のトレース表の書き方も合わせて確認しておくとつながりやすいです。
状態遷移図が苦手なら、一度自分で表に直すのも有効です。現在の状態を行、入力を列、移動先をセルに書くと、毎回矢印を探さずに済みます。逆に、状態遷移表が苦手なら、丸と矢印の図にしてみると全体の流れが見えやすくなります。
本番では時間が限られるので、全部を書き直す必要はありません。ただ、選択肢を比べても分からないときだけ、関係する状態だけを小さな表にするのはかなり使えます。図と表は別物ではなく、同じルールを違う見せ方にしたものだと考えてください。
表に直すときは、全状態を網羅しようとしなくても大丈夫です。自分が追っている入力列で実際に通る状態だけを書けば、途中の確認には十分です。時間を使いすぎないことも試験対策では大切です。
受理状態をどう見るか
受理状態は、入力列をすべて読み終えた後に「この文字列は条件を満たす」と判定する状態です。状態遷移図では二重丸で表されることが多く、問題によっては「終了状態」「受理する状態」のように説明されます。
大事なのは、途中で受理状態を通ったかどうかではなく、入力列を全部読み終えた時点でどの状態にいるかです。途中で二重丸に入っても、その後の入力で別の状態へ移動すれば、最終的には受理されないことがあります。ここを勘違いすると、選択肢を早く決めすぎて失点しやすいです。
- 入力をすべて読み終えてから判定する
- 途中で受理状態を通っても即決しない
- 最後にいる丸が二重丸か確認する
- 問題文で受理状態の指定がないか読む
「二重丸に入ったから終わり」と考えるのではなく、「最後にどこへいるか」を確認する癖をつけてください。基本情報の選択肢は、途中経過を見て早合点した人を引っかける形になっていることがあります。
たとえば、ある入力列の途中で受理状態に入っても、次の入力で受理状態から出てしまうなら、その文字列は受理されません。反対に、途中で受理状態に一度も入らなくても、最後の1文字で受理状態へ入れば受理されます。判定タイミングは常に「入力を全部読み終えた後」です。
この考え方は、試験の選択肢を消すときにも役立ちます。候補の文字列を順番に追い、最後が受理状態でないものを消していけばよいからです。全体の規則を言葉で説明できなくても、到達状態を正しく追えれば正解に近づけます。
受理状態が複数ある場合も考え方は変わりません。最後にいる状態が、指定された受理状態のどれかに含まれていれば受理です。二重丸が一つだけとは限らない点も、落ち着いて確認しましょう。
試験で問われる形
基本情報でオートマトンや状態遷移図が問われる場合、出題の中心は「入力列を与えられたときの到達状態」「受理される文字列」「条件を満たす遷移の読み取り」です。つまり、知識暗記だけでなく、手を動かして追う力が必要になります。
IPAの公式ページでは基本情報技術者試験の試験要綱・シラバスが公開されており、出題範囲全体の確認に使えます。細かい用語の深掘りよりも、シラバス上の分野の中で「何を問われるか」を意識して学ぶ方が、試験対策としては効率がいいですね。公式情報はIPAの試験要綱・シラバスで確認できます。
アルゴリズムや擬似言語の読解にも近い考え方なので、科目Bが苦手な人ほど、状態を1つずつ追う練習が効きます。全体の学習順を整理したい場合は、基本情報のアルゴリズム対策も参考になります。
よくある設問は、「次のうち受理される入力列はどれか」「入力列を与えたときの最終状態はどれか」「この状態遷移図が表している条件はどれか」です。最初の2つは手順通りに追えば解けます。最後の1つは少し抽象的ですが、複数の入力例を試すと規則が見えてきます。
難しい言葉が出ても、まずは問題が何を答えさせたいのかを見てください。用語説明なのか、入力列の判定なのか、図と表の対応なのかで作業が変わります。読み始める前に設問の末尾を確認しておくと、無駄に図全体を眺める時間を減らせます。
選択肢が文字列になっているなら、それぞれを追えばよい問題です。選択肢が状態名になっているなら、与えられた入力列を最後まで追います。設問の形を先に見れば、必要な作業がはっきりします。
基本情報の状態遷移図の解き方
入力列を左から追う
状態遷移図の基本手順は、入力列を左から1文字ずつ読むことです。たとえば入力列が「101」なら、最初に1、次に0、最後に1を読みます。現在の状態から、その入力に対応する矢印を選び、矢印の先へ移動します。
ここで大切なのは、入力をまとめて処理しようとしないことです。最初から最後の状態を予想すると、矢印が分岐した瞬間にミスが起きます。面倒でも、入力1つにつき状態を1回更新する方が安定します。
外から矢印が入っている丸、または問題文で指定された出発点を確認します。
現在の状態から、その入力に対応する矢印だけを探します。
矢印の先を新しい現在状態としてメモします。
入力をすべて読んだ後、受理状態にいるかを確認します。
この4手順を守れば、図が少し複雑でも落ち着いて処理できます。状態遷移図は、理解力だけでなく作業の丁寧さで正答率が変わるタイプの問題です。
入力列を読むときは、声に出すような感覚で「いまA、1を読む、Bへ移動」と処理するとミスが減ります。頭の中で高速に処理しようとすると、同じ入力が続いたときやループ矢印があるときに現在地を間違えやすくなります。
また、問題によっては入力が0と1だけではなく、aやb、文字種、操作名で与えられることもあります。記号が変わってもやることは同じです。現在の状態から、その入力に対応する矢印を選ぶ。この一点に集中すれば、表現が変わっても対応できます。
入力列が長い場合は、数文字ごとに区切って確認するのも有効です。ただし、区切った場所で判定して終わるのではなく、あくまで現在地を確認するだけです。最終判定は最後の入力を読み終えてから行います。
状態をメモして迷わない
入力列が短いときは頭の中だけで追えますが、試験本番ではメモを使った方が安全です。特に、状態が4つ以上ある場合や、同じ状態に戻る矢印が多い場合は、今どこにいるかを忘れやすくなります。
おすすめは、入力列の下に状態を書いていく方法です。入力を1文字読むたびに、移動後の状態を小さく書きます。これなら、途中で迷っても直前の状態から再開できます。選択肢を消すときも、根拠を残しやすいです。
| 確認するもの | メモする内容 |
|---|---|
| 読む前 | 初期状態 |
| 入力を1つ読んだ後 | 移動後の状態 |
| 最後の入力後 | 最終状態 |
| 判定時 | 受理状態かどうか |
このメモの取り方は、擬似言語の変数更新にも似ています。変数や配列を追うのが苦手な人は、基本情報の擬似言語対策と合わせて、1ステップずつ状態を更新する練習をしておくと理解がつながります。
メモはきれいに書く必要はありません。入力列の上や横に、A、B、Cのように到達状態だけを書けば十分です。選択肢問題では、最終状態が分かれば答えられることが多いので、途中の理由を長く文章化するより、状態の列を残す方が役に立ちます。
もし途中で分からなくなったら、最初から全部やり直す前に、最後に確実だと思える状態まで戻ってください。どの入力まで読んだかをメモしていれば、そこから再開できます。これができるだけで、本番中の焦りをかなり減らせます。
メモを残す目的は、きれいな解答を書くことではなく、現在地を失わないことです。問題用紙の余白に小さく書くだけで十分なので、暗算で押し切ろうとせず、作業として処理する意識を持つと安定します。
特に同じ状態に戻る矢印が多い図では、頭の中だけだと一つ前の状態と今の状態が混ざります。状態名を毎回書くのは手間に見えますが、結果的には解き直しを減らす近道です。
例題で手順を確認
簡単な例で考えてみます。状態Aを初期状態、状態Cを受理状態とします。Aで1を読むとBへ、Bで0を読むとCへ、Cで1を読むとCにとどまるとします。このとき、入力列「101」を読むとどうなるでしょうか。
まず初期状態はAです。最初の1を読むとAからBへ移動します。次の0を読むとBからCへ移動します。最後の1を読むとCのままです。入力をすべて読み終えた時点でCにいるので、この入力列は受理されると判断できます。
| 読む入力 | 読む前の状態 | 読む後の状態 |
|---|---|---|
| 1 | A | B |
| 0 | B | C |
| 1 | C | C |
同じ図でも、入力列が「100」なら結果は変わります。AからB、BからCまでは同じですが、最後の0でCから別の状態へ移るルールなら、最終状態がCではなくなります。だから、途中で受理状態に入ったことより、最後まで読み切った後の状態が大切です。
この例で大事なのは、文字列そのものを丸暗記しないことです。「101なら受理」と覚えても、別の図では通用しません。必要なのは、Aから始めて、入力を1文字ずつ処理し、最終状態を見るという手順です。手順が身につけば、図が変わっても同じ解き方で対応できます。
練習するときは、正解の入力列だけでなく、不正解の入力列も追ってみてください。なぜ受理されないのかを確認すると、受理状態の意味がかなりはっきりします。特に、途中では正しそうに見えるのに最後で外れる例を作ると、本番の引っかけにも強くなります。
例題を自作するときは、状態数を3つ程度に抑えると練習しやすいです。まずは短い入力列で確実に追えるようにしてから、入力列を少し長くします。いきなり複雑な図に挑むより、手順を体に覚えさせる方が効果的です。
答え合わせでは、最終状態だけでなく、途中の移動も確認してください。どこで間違えたかが分かれば、矢印の読み違いなのか、入力の飛ばしなのかを切り分けられます。
間違えやすいポイント
状態遷移図のミスは、知識不足というより読み方の癖で起きることが多いです。特に、矢印の向きを逆に読む、入力を飛ばす、受理状態を途中判定してしまう、という3つはよくあります。
矢印の向きは必ず現在の状態から外へ出る向きで見ます。近くに同じ入力ラベルの矢印があっても、自分が今いる状態から出ていない矢印は使えません。また、入力列を読み終える前に答えを決めるのも危険です。
- 矢印を逆向きにたどる
- 現在の状態ではない丸から矢印を選ぶ
- 入力を1文字飛ばしてしまう
- 途中で受理状態に入っただけで正解にする
- 問題文の条件を読まずに二重丸だけで判断する
対策はシンプルで、入力列にチェックを入れながら進めることです。読んだ入力に印を付け、移動後の状態を横に書きます。これだけで、入力飛ばしと現在地の見失いはかなり防げます。
もう一つ多いのが、問題文の条件を読み飛ばすミスです。「受理状態は状態Cとする」「入力列の末尾まで読んだ後で判定する」「開始状態は状態Bである」のような指定があると、図だけを見ている人ほど外します。状態遷移図の問題では、図と本文をセットで読む必要があります。
迷ったときは、選択肢から逆算するのも有効です。各選択肢の入力列を短いものから試し、最終状態だけを比べます。規則を完全に言語化できなくても、選択肢を一つずつ検証すれば正解に届くことがあります。基本情報では、この堅実な解き方がかなり強いです。
また、ループ矢印にも注意してください。同じ状態に戻る矢印は見落としやすく、入力を読んだのに状態が変わらないケースがあります。状態が変わらない場合でも、入力を1文字消費したことは忘れないようにしましょう。
まとめ
基本情報のオートマトンと状態遷移図は、初期状態、遷移、入力列、受理状態の4つを押さえれば、かなり解きやすくなります。図全体を一気に理解しようとするのではなく、現在の状態と次の入力だけを見て、1ステップずつ進めるのがコツです。
状態遷移図で迷ったら、まず初期状態に印を付け、入力列を左から読み、移動後の状態をメモしてください。最後に受理状態へいるかを確認すれば、問題文に振り回されにくくなります。
初期状態を確認し、入力を1文字ずつ読み、状態をメモし、最後に受理状態かどうかを判定します。
知識を読んだだけでは慣れにくい分野なので、実際の問題で手を動かす練習も必要です。今すぐ演習したい方は、基本情報の過去問アプリで無料演習できます。
最初は時間がかかっても問題ありません。慣れるまでは、入力列の下に状態を書き、最後に二重丸かどうかを確認するだけで十分です。数問解くと、丸と矢印の見方が自然に身についてきます。オートマトンは暗記量の多い分野ではなく、手順の安定性で点を取りやすい分野です。
次に演習するときは、正解した問題でも「どの入力でどの状態へ移ったか」を一度説明してみてください。説明できれば、たまたま当たったのではなく、状態遷移図を読めている証拠です。その状態まで持っていければ、科目Aでも科目Bでも落ち着いて対応できます。
最後に覚えておきたいのは、状態遷移図はパターン暗記よりも再現性が大切ということです。初期状態、入力、遷移、受理状態の順に見るだけで、初見問題でも同じ手順に落とし込めます。
本番前は、短い入力列の問題を数問解いて、状態をメモする流れを確認しておきましょう。解き方の型さえ固まれば、オートマトンは得点源にしやすいテーマです。
コメント