応用情報技術者 2016年 秋期 午前2 問04
問題文
表は、入力記号の集合が {0, 1}、状態集合が である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左(上位ビット) から順に読み込んで最後が 110で終わっているものを受理するには、どの状態を受理状態とすればよいか。
選択肢
ア：
イ：
ウ：（正解）
エ：
有限オートマトンの受理状態判定【午前2 解説】
要点まとめ
- 結論：長さ3以上のビット列の末尾が「110」であることを判定するには、状態を受理状態にすればよいです。
- 根拠：状態遷移表から、状態は直前の入力が「11」の後に「0」が来た状態を表し、「110」で終わる入力を正しく受理します。
- 差がつくポイント：状態遷移の意味を理解し、末尾3ビットのパターンを追跡できるかが合否を分けます。
正解の理由
状態遷移表を読み解くと、
- 状態は初期状態で、まだ「110」のパターンを検出していない状態です。
- 状態は直前の入力が「1」であることを示します。
- 状態は「11」が続いた状態ですが、次に「1」が来ると状態$d」のままなので「110」にはなりません。
- 状態は「11」の後に「0」が来た状態で、つまり末尾が「110」で終わる入力を受理する状態です。
したがって、状態を受理状態に設定するのが正解です。
よくある誤解
状態が「11」の状態なので受理状態にしがちですが、次の入力が「0」でなければ「110」にはならず誤りです。
また、状態$b」や「a」は部分的なパターンしか示さず、末尾3ビットの判定には不十分です。
また、状態$b」や「a」は部分的なパターンしか示さず、末尾3ビットの判定には不十分です。
解法ステップ
- 状態遷移表を確認し、各状態がどのような入力履歴を表すか理解する。
- 「110」で終わるパターンを状態遷移に当てはめて追跡する。
- 「11」の後に「0」が来た状態を特定する。
- その状態を受理状態に設定する。
- 選択肢の中から該当する状態を選ぶ。
選択肢別の誤答解説
- ア:
初期状態であり、特定のパターンを示さないため受理状態には不適切です。 - イ:
「1」が直前に入力された状態で、「110」の末尾判定には不十分です。 - ウ:
「11」の後に「0」が来た状態で、「110」で終わる入力を正しく受理します。 - エ:
「11」が続いた状態ですが、次の入力が「0」でなければ「110」にならず誤りです。
補足コラム
有限オートマトンは入力列のパターン認識に用いられ、状態遷移表は各状態での入力に対する次状態を示します。
特に末尾の特定パターン検出は、状態をパターンの部分一致に対応させることで実現可能です。
この問題は「部分文字列検出オートマトン」の基本的な応用例です。
特に末尾の特定パターン検出は、状態をパターンの部分一致に対応させることで実現可能です。
この問題は「部分文字列検出オートマトン」の基本的な応用例です。
FAQ
Q: なぜ状態が「110」の末尾を表すのですか？
A: 状態は「11」の後に「0」が入力された状態で、これが「110」の末尾パターンに対応します。
A: 状態は「11」の後に「0」が入力された状態で、これが「110」の末尾パターンに対応します。
Q: 状態はなぜ受理状態にならないのですか？
A: 状態は「11」が続いた状態ですが、次の入力が「0」でなければ「110」にならず、末尾判定に不適切です。
A: 状態は「11」が続いた状態ですが、次の入力が「0」でなければ「110」にならず、末尾判定に不適切です。
関連キーワード: 有限オートマトン、状態遷移表、パターン認識、文字列検出、受理状態
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！