情報処理安全確保支援士試験 情報セキュリティスペシャリスト試験 平成28年度秋期 午前Ⅰ 問2: 表は，入力記号の集合が {0, 1}，状態集合が {a, b, c, d} である有限オートマトンの状態遷移表である。長さ 3 以上の任意のビット列を左（上位ビ

問題本文

表は，入力記号の集合が {0, 1}，状態集合が {a, b, c, d} である有限オートマトンの状態遷移表である。長さ 3 以上の任意のビット列を左（上位ビット）から順に読み込んで最後が 110 で終わっているものを受理するには，どの状態を受理状態とすればよいか。

選択肢

• ア.a
• イ.b
• ウ.c
• エ.d

正解

ウ. c

解説

末尾が「110」で終わる入力を受理する有限オートマトンの受理状態を問う問題。入力を1文字ずつ読んで状態遷移をたどると，直前までに読んだ末尾パターンが各状態に対応する。1→b（末尾1），11→d（末尾11），110→c（末尾110）と遷移するため，「110で終わる」ことを表す状態はc。よって受理状態はウのc。状態に意味（ここでは読み込んだ末尾ビット列）を割り当てて追う考え方は字句解析やパターンマッチの基礎。

選択肢ごとの解説

• ア.状態aは末尾が0または初期に相当し，110で終わった状態ではないため誤り。
• イ.状態bは末尾が1になった直後を表し，110完成を示さないため誤り。
• ウ.11の後に0を読むとcへ遷移し，末尾110の完成を表すため受理状態として正しい。
• エ.状態dは末尾が11（1が連続）の状態で，最後の0を読む前なので誤り。