応用情報技術者試験 応用情報技術者試験 平成28年度秋期 午前 問4: 表は，入力記号の集合が {0, 1}，状態集合が {a, b, c, d} である有限オートマトンの状態遷移表である。長さ 3 以上の任意のビット列を左（上位ビ

問題本文

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

選択肢

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

正解

ウ. c

解説

有限オートマトン(状態遷移表)の動作を読み解く問題。「最後が110で終わる」ビット列を受理させるには、末尾の3ビット 1→1→0 を順に読み込んだ後に到達する状態を受理状態にすればよい。初期状態は通常 a とみなし、110で終わる例(例えば 110)を読ませる。a で「1」を読むと b、b で「1」を読むと d、d で「0」を読むと c に到達する。別の前提の列(例 0110)でも末尾110を読むと、…→d(1)→c(0)…のように最終的にcへ至る。つまり末尾が110で終わる入力を読み終えた状態は c になるため、受理状態は c で正しく、正解はウである。

選択肢ごとの解説

• ア.状態 a は初期状態であり、また「0」が連続した直後など 110 で終わらない多くの列でも到達するため、これを受理状態にすると 110 で終わらない列まで受理してしまい不適。
• イ.状態 b は直前が「1」を1つ読んだ段階で到達する状態であり、末尾が「…1」で終わる(0で終わらない)場合に対応するため、末尾110の判定には合致せず誤り。
• ウ.末尾の 1→1→0 を読むと a/c から b、b から d、d から c へ遷移し、110 で終わる列を読み終えた時点で必ず状態 c に到達する。したがって c を受理状態にすればよく、正しい。
• エ.状態 d は「11」と1が連続した段階(末尾が…11)で到達する状態であり、最後の0をまだ読んでいない状態を表すため、110で終わる判定の受理状態としては誤り。