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

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

解答：ウ

＜解説＞

1. 110の左端の1を読み込む：状態がa又はcの時はb、bまたはdの時はdに遷移する
2. 110の中央の1を読み込む：状態がb又はdの時に1を読み込むとdに遷移する
3. 110の右端の0を読み込む：状態がdの時に0を読み込むとcに遷移する

したがって、ウが正解である。

キーワード

• 「有限オートマトン」関連の過去問題・・・有限オートマトンとは
  • 基本情報技術者 平成18年度(秋季) 問11
  • 応用情報技術者 平成21年度(春季) 問3
  • 応用情報技術者 平成26年度(春季) 問4
  • 応用情報技術者 平成28年度(秋季) 問4
  • 高度共通　午前1 平成21年度(春季) 問2