基本情報技術者試験「有限オートマトン」の問題
入力された0と1の並びについて、これまでに読み込んだ1の個数が偶数か奇数かを判定する有限オートマトンを設計する場合、最低限必要な状態の数はいくつか。
ア判定には3状態が必要となる
イ入力記号と同じ4状態である
ウ2状態で十分である
エ1状態だけで判定できる
正解
ウ．2状態で十分である
必要なのは『1の個数が偶数』と『奇数』の区別だけである。初期状態(偶数)から1を読むたびに偶数⇄奇数を切り替えればよく、0は状態を変えない。2状態で十分なので正しい。
?選択肢ごとの解説
ア ×3状態は余分な状態を1つ持つ設計で、偶数・奇数の2区分には不要であり最小ではない。
イ ×4状態は入力記号数(0と1の2種)と状態数を混同した誤りで、判定に必要な区別は2つだけである。
ウ ○必要なのは『1の個数が偶数』と『奇数』の区別だけである。初期状態(偶数)から1を読むたびに偶数⇄奇数を切り替えればよく、0は状態を変えない。2状態で十分なので正しい。
エ ×1状態では偶数と奇数を区別できず、現在のパリティを保持できないため判定不能である。
✎くわしく
有限オートマトンの状態数は『区別すべき状況の数』で決まる。本問はパリティ(偶奇)という2値情報だけを保持すればよいので最小2状態。0は自己ループ、1は状態反転の遷移を持つ。状態=記憶すべき同値類という見方が核心である。
✓本番での押さえどころ
試験のコツ
オートマトンの最小状態数は『判別に必要な情報の場合の数』で考える。偶奇判定なら2状態と即断する。
覚え方
パリティ判定は『偶』と『奇』の2部屋を1を読むたびに行き来する、と2状態の往復でイメージする。
よくある誤り
入力記号の種類数と状態数を混同する、または必要以上に状態を増やしてしまう誤りが多い。
基礎理論の他の問題
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0091