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

問題本文

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

選択肢

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

正解

ウ. c

解説

末尾が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で終わる条件と一致しないため誤り。