情報に関する理論 (全37問中11問目)
No.11
次の表は，入力記号の集合が{0，1}，状態集合が{a，b，c，d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左(上位ビット)から順に読み込んで最後が110で終わっているものを受理するには，どの状態を受理状態とすればよいか。
出典：平成26年春期 問4
- [この問題の出題歴]
- 応用情報技術者 H28秋期 問4
- ソフトウェア開発技術者 H17春期 問7
- ソフトウェア開発技術者 H18秋期 問7
分類
テクノロジ系 » 基礎理論 » 情報に関する理論
正解
ウ
解説
表の有限オートマトンを図にすると次のようになります。
ビット列「110」が入力されるときに、a〜dのどの状態であるかはわかりませんが、最後の0が入力されて遷移する先はaかcのどちらかしかないので、bとdは正解候補から除外できます。
aとcを比較してみると、cが受理状態となるケースは、
一方aのケースを考えてみると、aの直前状態であるcに遷移するには状態b，dに0が入力されなければならず、aが受理状態になるには入力ビット列の後ろ2つが「0」であることが必要条件になります。したがって「110」を受理するルートはありません。
これらのことから「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
一方aのケースを考えてみると、aの直前状態であるcに遷移するには状態b，dに0が入力されなければならず、aが受理状態になるには入力ビット列の後ろ2つが「0」であることが必要条件になります。したがって「110」を受理するルートはありません。
これらのことから「c」が適切とわかります。