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

正解

ウ. c

正答率 50.0%（2人中 1人が正解）

問題の解説

末尾が110で終わる列を受理する問題。初期状態aから遷移表に従い「110」を読むと、a→(1)→b→(1)→d→(0)→cとなり、直前が110で終わる状態はcに到達する。任意の長さの列でも最後の3ビットが110なら最終的にcで止まるため、受理状態はcが正解(ウ)。有限オートマトンは字句解析やパターン照合の基礎理論。

選択肢ごとの解説

• アaは0で自己ループする状態で、末尾110を表さないため受理状態にできず誤り。
• イbは末尾が1の状態(…1)を表し、110で終わる条件とは一致せず誤り。
• ウ110を読み終えるとaまたはcからcへ到達し、末尾110を正しく表すため正解。
• エdは末尾が11の状態(…11)を表し、110で終わる条件と一致しないため誤り。