応用情報技術者 2016年 秋期 午前2 問04

末尾110の受理状態【午前2解説】

正解の理由

解法ステップ

1. 遷移表を見て，状態遷移が「直前2ビット（末尾2ビット）」に依存していることを確認する。すなわち各状態からの遷移が同型に見える点に注目する。
2. 初期状態 a から長さ2のすべての入力を試し，どの状態に落ちるかを調べる（以下に示す代表例参照）。ここから各状態がどの末尾2ビットを表すかを対応付ける。
3. 「末尾が110」である文字列の末尾2ビットは "10" なので，そのとき到達する状態（c）を受理状態にすれば目標を満たすと判断する。

• "00" → a
• "01" → b
• "10" → c
• "11" → d

選択肢別の誤答解説

• ア: a
  • a は末尾2ビットが "00"（空列や 0, 00, 100 などの類）を表す代表状態です。末尾が "110" のときは末尾2ビットが "10" なので a に落ちることはありません。よって不適。
• イ: b
  • b は末尾2ビットが "01" を表します（例："01","101" など）。"110" の末尾2ビットは "10" なので b は不適。
• ウ: c
  • c は末尾2ビットが "10" を表す状態であり，末尾が "110" の文字列は必ずここに到達するため適切です（本問の正答）。
• エ: d
  • d は末尾2ビットが "11" を表します。末尾3ビットが "110" のときはここにはなりません。よって不適。

よくある誤解

1. 状態 c を「直前が '11' の後に 0 が来た状態」と限定的に説明する誤り。実際には c は「末尾2ビットが '10' である状態」を表し，"11" の直後の 0 以外の経路（例："010" や "10110" の末尾）からも到達します。
2. 「状態は末尾3ビットを表す」と誤解すること。与えられた遷移は末尾2ビットを追跡する構造であり，状態数4は末尾2ビット (4通り) に対応します（末尾3ビットを正確に判定したいなら別の設計（接頭辞関係を扱う遷移）や受理条件の工夫が必要になる場合があると混同しがちです）。

補足コラム

• 与えられた遷移表は「シフトレジスタ的に末尾2ビットを保持する」DFAに相当します。状態 a,b,c,d をそれぞれ末尾2ビット "00","01","10","11" に対応させると，どの入力を読んでも次の末尾2ビットに適切に更新されることが確かめられます。
• 問題文が「長さ3以上の任意のビット列を対象」としているのは，長さが不足する入力（長さ1や2）は末尾3ビットの定義ができないためであり，設問の意図は「長さが十分にある入力に対して末尾が110であることを判定したい」という点にあります。与えられた遷移で「末尾が110である入力は必ず状態 c に落ちる」点が重要です。

FAQ