平成28年度 秋期 応用情報技術者試験 問4

解説

正解は3です。 有限オートマトンは、入力を1文字読むごとに状態遷移表に従って状態を移します。 末尾が110の列を受理するには、どの状態にいても「1、1、0」と読んだ後に必ずたどり着く状態を受理状態にします。 【各状態から110を読んだ場合】 aから始めると、1でb、次の1でd、最後の0でcになります。 bから始めると、1でd、次の1でd、最後の0でcになります。 cから始めると、1でb、次の1でd、最後の0でcになります。 dから始めると、1でd、次の1でd、最後の0でcになります。 どの状態から始めても最後はcに到達するので、受理状態はcです。 【選択肢別解説】 1：× aは、直前の2ビットが00のときに到達する状態です。 110を読み終えたときにaにいることはないので、受理状態にできません。 2：× bは、最後に1を読んだ状態です。 末尾が0の列はbで終わらないので誤りです。 3：○ 上のとおり、どの状態から始めても110を読み終えるとcに到達します。 4：× dは、直前の2ビットが11のときの状態です。 110の最後の0を読むとdからcに移るので、dでは終わりません。 【ポイント】 この表は、直前に読んだ2ビットを状態として覚えています（a＝00、b＝01、c＝10、d＝11）。 そのため、厳密には010で終わる列もcに到達します。 本問は「110で終わる列を必ず受理する状態」を選ぶ問題として、cが正解とされています。