表は，入力記号の集合が{0，1}，状態集合が{a，b，c，d}である有限オートマトンの状態遷移表である。長さ 3 以上の任意のビット列を左（上位ビット）から順に読み込んで最後が 110 で終わっているものを受理するには，どの状態を受理状態とすればよいか。
| 0 | 1 | |
|---|---|---|
| a | a | b |
| b | c | d |
| c | a | b |
| d | c | d |
平成28年度 秋期 応用情報技術者 問4
テクノロジ系
正解と解説
正解 ウ
どの状態から始めても、110を読み終えた時点の状態はcになるので、cを受理状態にします。
表から、1を読むとbかdに、0を読むとaかcに移ります。aからは1でb、もう一度1でd、0でcに移ります。bから始めるとd、d、c、cから始めるとb、d、c、dから始めるとd、d、cになります。どの状態から読み始めても、最後の3ビットが110なら状態cで終わるので、cを受理状態とします。
ア：aは0を読んだ直後で、その前も0のとき（末尾が00）に到達する状態です。110を読み終えてaになることはありません。
イ：bは末尾が01のときに到達する状態です。最後に0を読んだ後はbになりません。
エ：dは11と続けて読んだ直後の状態です。110の最後の0を読むと、dからcに移ります。
出典：平成28年度 秋期 応用情報技術者試験 問4
全年度から出題。10問で実力を判定します。登録不要。
出典：平成28年度 秋期 応用情報技術者試験 問4（独立行政法人情報処理推進機構）
解説と用語ページは生成 AI が書き、別の生成 AI が確かめています。作り方