平成28年度 秋期 応用情報技術者試験 午前 問4
テクノロジ／基礎理論表は，入力記号の集合が{0，1}，状態集合が{a，b，c，d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左（上位ビット）から順に読み込んで最後が110で終わっているものを受理するには，どの状態を受理状態とすればよいか。 現在の状態：0のときの遷移先／1のときの遷移先 a：a／b b：c／d c：a／b d：c／d （注：本サイトでは原問題の表を文字表記に変換しています）
出典：平成28年度 秋期 応用情報技術者試験 午前 問4
- アa
- イb
- ウc
- エd
正解：ウ
解説
状態aは遷移が自分自身に戻る「未マッチ」の状態，状態bは「1」を1文字読んだ状態です。表のcの行はaの行と全く同じ遷移（0でa，1でb）をしており，これはaと同じ振る舞いをしつつ受理フラグだけが立つ状態，すなわち直前に「110」を読み終えた直後の状態を表します。実際に「110」を入力すると a→b→d→c と遷移し，状態cに到達することから，cを受理状態とすればよいことが分かります。
選択肢ごとの解説
- ア誤り。aは何もマッチしていない初期状態であり，受理状態にすると110で終わらない文字列も誤って受理してしまいます。
- イ誤り。bは直前の1文字が「1」であることを示す状態で，「110」の完了を意味しません。
- ウ正しい。表よりcはaと全く同じ遷移をする状態であり，「110」を読み終えた直後にだけ到達する状態なので，cを受理状態とすればよいです。
- エ誤り。dはbと同じ「1」を読んだ直後を示す状態と対応し，「110」の完了を意味しません。