状態遷移・構文規則・マルコフ過程

このレッスンの全体像：4種類とも「表や図を機械的にたどる」だけ

状態遷移・構文規則・マルコフ過程は見た目が違いますが、解き方はどれも同じです。決められた規則を、入力の左から1つずつ当てはめるだけです。頭の中で近道をすると間違えるので、紙に途中経過を書きながら進めるのが正攻法です。

状態遷移図の読み方（最頻出）

状態遷移図は「今どの状態にいて、何が入力されたら、どこへ移るか」を描いた図です。丸が状態、矢印が遷移で、矢印のラベル「入力/出力」は「この入力が来たらこれを出力して矢印の先へ移る」という意味です。自動改札機が「待機中→ICカードをタッチ→残高OKならゲートを開く」と動くのと同じで、今の状態と入力だけで次の動きが決まるのがポイントです。

図の読み方の約束事は次のとおりです。

出題は3つの型に分かれます。

• 出力の列を求める型：遷移のたびに出力を1文字ずつ並べる。
• 受理されるか判定する型：最後の文字を読んだ時点で二重丸にいるかを見る。途中で二重丸を通っても、最後にいなければ受理ではありません。
• 仕様に合う図を選ぶ型（自動販売機など）：「何回目の入力で何を出力するか」を選択肢の図ごとにたどって確かめる。

例えば「300円の商品・100円硬貨だけ受け付ける自販機」なら、正しい図は 100円を3枚入れた3回目の遷移で初めて「/1」（販売）が出て初期状態に戻り、100円以外の硬貨は各状態の自己ループ「b/0」で返却されるものです。2枚目で「/1」が出る図や、a と b の役割が逆の図がひっかけです。

状態遷移図の手順を図で確認

次の図は例題（平成30年度春期 午前 問4）の状態遷移図を描き直したものです。S3 から 0 で S1 に戻る矢印の出力は 0 です。ここを1と読み違えるのが典型的なミスです。

flowchart LR
  S1["S1（初期状態）"] -->|"0/0"| S1
  S1 -->|"1/0"| S2["S2"]
  S2 -->|"0/0"| S1
  S2 -->|"1/1"| S3["S3"]
  S3 -->|"1/1"| S3
  S3 -->|"0/0"| S1

この機械は「1 が2つ以上続いたら、2つ目以降の 1 で 1 を出力する」動きをしています。ただし試験では意味を考えるより、1文字ずつたどるほうが速く確実です。

状態遷移表による文字列検査

状態遷移表は状態遷移図を表にしたもので、行＝今の状態、列＝読んだ文字、交点＝次の状態です。入力チェックの仕組みを表にしたものと考えてください。数値として正しい書き方かを1文字ずつ判定し、ダメなら e（エラー状態）へ落とします。

頻出の表（初期状態 a、e になったら不合格）では、それぞれの状態は次のように読めます。

つまりこの表では、小数点の後に数字が来ると e になります。だから「12.2」が不合格で、「9.△」（小数点の後が空白）は合格です。普通の感覚では 12.2 が正しい数に見えるので、常識で判断すると間違えます。表に書いてあることだけが正解です。

免除試験では「末尾が 110 で終わる列を受理するにはどの状態を受理状態にするか」という逆向きの問題も出ます。表を見ると、各状態は 直前2文字 を覚えていることが分かります（a＝00、b＝01、c＝10、d＝11）。末尾が 110 なら直前2文字は 10 なので、c に必ず着きます。

BNF（構文規則）の適合判定

**BNF（バッカス・ナウア記法）**は「どんな文字の並びが正しいか」を規則で定義する書き方です。プログラミング言語の文法や入力値の書式を厳密に決めるのに使います。API 設計で「ID は英字で始まり、英数字が続く」と仕様に書くのを、記号で正確に書いたものと考えてください。

読み方のコツは再帰（自分自身を使う定義）です。 ＜変数名＞ ::= ＜英字＞ ｜ ＜変数名＞＜英数字＞ は、「英字1文字は変数名」「変数名の後ろに英数字を1つ足したものも変数名」という意味です。つまり先頭は必ず英字（この問題では A〜F だけ）、2文字目以降は英字・数字・_ のどれでもよいとなります。

判定の手順は次の3つです。

1. 各規則が「先頭に何を許すか」「何を繰り返せるか」を日本語に言い換える。
2. 選択肢を先頭の文字から当てはめ、規則で作れない箇所が1つでもあれば除外する。
3. 括弧や演算子の付き方は、規則に書いてある形でしか作れないことに注意する。

免除試験には、R0・R1・R2 が「3で割った余りが0・1・2の数字」、〈A〉が「各桁の和が3で割り切れる数字の列」を表す応用問題も出ています。〈B〉＋R2 なら余り 1＋2＝3 で割り切れる、という組合せを見抜けば、各桁の和が3の倍数かを確かめるだけで答えが出ます（1＋2＋3＝6 なので 123）。

遷移確率行列の性質（行和＝1）

遷移確率は「今の状態がこれのとき、次にこの状態になる確率」です。これを表にしたものを遷移確率行列といいます。行（横の並び）が「今」、列（縦の並び）が「次」です。

同じ行の確率を全部足すと必ず 1（100%）になります。今が「入力0」なら、次は出力0か出力1のどちらかに必ずなるからです。天気予報で「明日は晴れ40%・曇り40%・雨20%」の合計が100%になるのと同じです。

よって入力0の行 a＋b＝1、入力1の行 c＋d＝1 となります。

マルコフ過程：2回後の確率

単純マルコフ過程は「次の状態の確率が今の状態だけで決まり、それより前の履歴は関係しない」という仮定です。雨の翌日の天気を考えるとき、一昨日が晴れだったかは気にしません。

2日後の確率を求めるときは、1日目にどの状態を経由するかで経路を全部挙げます。経路ごとに確率を掛け、最後に全経路を足します。計算に使うのは今日の状態と表だけです。

2日後に X になる確率 ＝ Σ（今日→1日目の確率 × 1日目→X の確率）

市場シェア型（2つのブランドA・B）の問題も同じ計算です。違いは、出発点が「今日は雨」のような1つの状態ではなく「A 50%・B 50%」という割合になることだけです。1回ごとに「今のシェア×遷移確率」を足して、それを2回繰り返します。

試験での問われ方

• 状態遷移図：出力列の選択肢は1〜2文字しか違いません。S3→S1 のように状態が戻る遷移の出力を取り違えさせる作りです。全文字たどってから選びましょう。
• 状態遷移表：同じ表（a〜e、空白・数字・符号・小数点・その他）が何度も出ています。12.2 のような常識的には正しい文字列が不合格になります。
• BNF：先頭に数字や _ が来る選択肢、定義されていない英字（例：A〜F 限定なのに G）を使う選択肢、規則にない括弧の付け方をした式が並びます。
• 遷移確率：行和・列和・全体の合計・対角の和の4択がそのまま選択肢になります。
• マルコフ過程：選択肢に「1日分の確率（30%）」や「1経路だけ掛けた値（0.12や0.15）」が並びます。1回分で計算を止めた値（10%）も並びます。