平成28年度 秋期 午前 問3
情報に関する理論
状態遷移図に関する問題
300円の商品を販売する自動販売機の状態遷移図はどれか。ここで，入力と出力の関係を“入力／出力”で表し，入力の“a”は“100円硬貨”を，“b”は“100円硬貨以外”を示し，S₀ 〜 S₂ は状態を表す。入力が“b”の場合はすぐにその硬貨を返却する。また，終了状態に遷移する際，出力の“1”は商品の販売を，“0”は何もしないことを示す。
4肢はいずれも状態遷移図（原典は図。「開始の矢印がどの状態に入るか」「二重丸（終了状態）がどれか」「各遷移の入力／出力」を読み取って文に置き換えた）:
- ア開始 → S₀（S₀ が二重丸）。S₀ →S₁ が a／0，S₁ →S₂ が a／0，S₂ →S₀ が a／1。S₀・S₁・S₂ のいずれにも b／0 の自己ループ。
- イ開始 → S₀（S₂ が二重丸）。S₀ →S₁ が a／0，S₁ →S₂ が a／1，S₂ →S₀ が a／1。S₀・S₁・S₂ のいずれにも b／0 の自己ループ。
- ウ開始 → S₀（S₂ が二重丸）。S₀ →S₁ が a／0，S₁ →S₂ が a／1，S₂ →S₀ が a／0。S₀・S₁・S₂ のいずれにも b／0 の自己ループ。
- エ開始 → S₀（S₀ が二重丸）。S₀ →S₁ が b／0，S₁ →S₂ が b／0，S₂ →S₀ が b／0。S₀・S₁ に a／0 の自己ループ，S₂ に a／1 の自己ループ。
答えと解説を見る
✓ これが正解ア開始 → S₀（S₀ が二重丸）。S₀ →S₁ が a／0，S₁ →S₂ が a／0，S₂ →S₀ が a／1。S₀・S₁・S₂ のいずれにも b／0 の自己ループ。
解説
3枚目の硬貨で初めて販売の出力が出る状態遷移図が当たります。
300円の商品なので、100円硬貨が3枚そろって初めて商品が出ます。したがって、硬貨を受け取る遷移のうち商品の販売を示す出力1が出るのは3回目だけで、1回目と2回目は何もしないことを示す0でなければなりません。また3枚目を受け取ったところで取引が終わるので、そのとき移る先が終了状態、つまり二重丸の付いた状態になります。開始の矢印が入る状態と終了状態が同じであっても構いません。硬貨を1枚も入れていない状態へ戻ってきて、そこで終わる、と読めるからです。さらに、100円硬貨以外を表す入力ではすぐ返却するので、どの状態にいても自分自身へ戻り、出力は0のままになります。この三つ、すなわち出力1が3回目に一度だけ出ること、その行き先が二重丸であること、100円硬貨以外では状態が動かないことを、図ごとに順に当てていけば決まります。
ほかの選択肢はなぜ違うのか
- イ開始 → S₀（S₂ が二重丸）。S₀ …：S₁ から S₂ へ移る遷移の出力が1になっており、硬貨が2枚、すなわち200円の時点で商品が出てしまいます。しかも3枚目の遷移の出力も1なので、1回の取引で販売が二度起きる形になっています。
- ウ開始 → S₀（S₂ が二重丸）。S₀ …：2枚目の硬貨を受け取る遷移で出力が1になり、200円で商品が出る形になっています。逆に3枚目を受け取る遷移の出力は0で、300円そろった時点では何も起きません。金額と販売の対応が入れ替わっています。
- エ開始 → S₀（S₀ が二重丸）。S₀ …：状態が先へ進むきっかけが100円硬貨以外の入力になっており、100円硬貨を入れても同じ状態に留まります。すぐ返却するはずの入力で金額が積み上がることになり、設問が定めた二つの入力の意味が逆です。
出典：平成28年度 秋期 基本情報技術者試験 午前 問3
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）