平成28年秋期試験問題 午前Ⅰ 問2
問2解説へ
次の表は,入力記号の集合が{0,1},状態集合が{a,b,c,d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左(上位ビット)から順に読み込んで最後が110で終わっているものを受理するには,どの状態を受理状態とすればよいか。
- a
- b
- c
- d
正解 ウ問題へ
分野:テクノロジ系
中分類:基礎理論
小分類:情報に関する理論
中分類:基礎理論
小分類:情報に関する理論
広告
解説
表の有限オートマトンを図にすると次のようになります。ビット列「110」が入力されるときに、a~dのどの状態であるかはわかりませんが、最後の0が入力されて遷移する先はaかcのどちらかしかないので、bとdは正解候補から除外できます。
aとcを比較してみると、cが受理状態となるケースは、
一方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です。
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
一方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です。
広告