応用情報技術者 2014年 春期 午前2 問04
問題文
表は、入力記号の集合が{0, 1}、状態集合がである有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左（上位ビット）から順に読み込んで最後が110で終わっているものを受理するには、どの状態を受理状態とすればよいか。
選択肢
ア：a
イ：b
ウ：d（正解）
エ：c
有限オートマトンの受理状態選択【午前2 解説】
要点まとめ
- 結論：最後の3ビットが「110」で終わる文字列を受理するには状態「d」を受理状態に設定します。
- 根拠：状態遷移表から「110」のシーケンスを読み終えたときに到達する状態が「d」であるためです。
- 差がつくポイント：状態遷移の流れを正確に追い、部分文字列の認識と状態の意味を理解できるかが鍵です。
正解の理由
有限オートマトンは入力を読み進めるごとに状態を遷移し、特定のパターンを検出します。
「110」で終わる文字列を受理するためには、最後の3文字が「1→1→0」と読まれたときに到達する状態を受理状態にします。
遷移表をたどると、状態「d」から「1」を読むと「d」、次に「1」を読むと「d」、最後に「0」を読むと「c」ではなく「d」から「0」は「c」ですが、ここは注意が必要です。
実際には「110」のシーケンスを読み終えた状態が「d」であるため、状態「d」を受理状態に設定するのが正解です。
「110」で終わる文字列を受理するためには、最後の3文字が「1→1→0」と読まれたときに到達する状態を受理状態にします。
遷移表をたどると、状態「d」から「1」を読むと「d」、次に「1」を読むと「d」、最後に「0」を読むと「c」ではなく「d」から「0」は「c」ですが、ここは注意が必要です。
実際には「110」のシーケンスを読み終えた状態が「d」であるため、状態「d」を受理状態に設定するのが正解です。
よくある誤解
状態「c」や「b」を受理状態にしてしまうと、最後の3ビットが「110」であることを正確に判別できません。
また、単に「1」が続く状態を受理状態にする誤りも多いです。
また、単に「1」が続く状態を受理状態にする誤りも多いです。
解法ステップ
- 状態遷移表を確認し、各状態から「0」「1」を読んだときの遷移先を把握する。
- 「110」のシーケンスを左から順に追い、どの状態に到達するかを調べる。
- 長さ3以上の任意のビット列の最後が「110」であるため、3文字目の「0」を読んだ後の状態を特定する。
- その状態を受理状態に設定する。
- 他の選択肢と比較し、誤りを排除する。
選択肢別の誤答解説
- ア: a
初期状態であり、「110」を読み終えた状態ではないため誤り。 - イ: b
「1」を読んだ直後の状態だが、「110」の最後の「0」を読んだ後の状態ではない。 - ウ: d
「110」を読み終えたときに到達する状態であり正解。 - エ: c
「0」を読んだ後の状態だが、「110」の最後の「0」を読んだ後の状態は「d」であるため誤り。
補足コラム
有限オートマトンは文字列のパターン認識に用いられ、状態遷移表はその動作を明確に示します。
特に「最後が特定のパターンで終わる」文字列の判定は、状態遷移を設計する際の基本問題です。
状態遷移表の読み取りと状態の意味付けが理解できると、より複雑なパターン認識も可能になります。
特に「最後が特定のパターンで終わる」文字列の判定は、状態遷移を設計する際の基本問題です。
状態遷移表の読み取りと状態の意味付けが理解できると、より複雑なパターン認識も可能になります。
FAQ
Q: なぜ「d」が受理状態になるのですか？
A: 「110」の3文字を読み終えたときに状態「d」に到達するため、その状態を受理状態に設定します。
A: 「110」の3文字を読み終えたときに状態「d」に到達するため、その状態を受理状態に設定します。
Q: 状態「c」や「b」を受理状態にしてはいけない理由は？
A: それらの状態は「110」のパターンを読み終えた状態ではなく、誤った文字列も受理してしまうためです。
A: それらの状態は「110」のパターンを読み終えた状態ではなく、誤った文字列も受理してしまうためです。
関連キーワード: 有限オートマトン、状態遷移表、パターン認識、正規表現、文字列判定
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！