分野 ：テクノロジ系
中分類：基礎理論
小分類：情報に関する理論

表の有限オートマトンを図にすると次のようになります。ビット列「110」が入力されるときに、a～dのどの状態であるかはわかりませんが、最後の0が入力されて遷移する先はaかcのどちらかしかないので、bとdは正解候補から除外できます。

aとcを比較してみると、cが受理状態となるケースは、

• b→(1)→d→(1)→d→(0)→c
• c→(1)→b→(1)→d→(0)→c
• a→(1)→b→(1)→d→(0)→c
• d→(1)→d→(1)→d→(0)→c

という4通りが考えられます。

一方aが受理状態となるケースを考えてみると、aの直前状態のうち、aに遷移するには状態aまたはcに0が入力されなければならず、cに遷移するには状態bまたはdに0が入力されなければならないので、aが受理状態になるには入力ビット列の後ろ2つが「0」であることが必要条件になります。したがって「110」を受理するルートはありません。

以上より「c」が正解とわかります。

【別解】
ビット列「110」が入力されるときに、a～dのどの状態であるかはわかりませんが、最初の1が入力されて遷移する先はbかdのどちらかしかなく、次の1が入力されて遷移する先はdしかないので、最後の0が入力されて遷移する先はcです。