問 題
次の表は入力記号の集合が {0, 1}、状態集合が {a, b, c, d} である有限オートマトンの状態遷移表である。ここで初期状態は a であり受理状態は c とする。この有限オートマトンが受理する入力記号列に関する記述として最も妥当なのはどれか。
1. 001 で終わる全ての記号列
2. 001 で始まる全ての記号列
3. 001 を含まない全ての記号列
4. 0 の個数と 1 の個数が同じ全ての記号列
5. 0 の個数と 1 の個数が異なる全ての記号列
正解 (1)
解 説
選択肢 1 から検討します。
「001」という文字列を考えます。a で 0 入力だと、状態は b に遷移します。次に状態 b で 0 入力だと、状態は d に遷移します。最後に状態 d で 1 入力だと、状態 c に遷移します。c が受理状態なので、「001」は受理されました。
ここで、入力の 00 部分に注目すると、状態が a の時 a → b → d と遷移しました。もし状態 b の時 00 を受け取ったとすると、表より b → d → d です。やはり 状態 d に遷移します。 以下、状態 c の時 00 を受け取ると c → b → d 、状態 d の時 00 を受け取ると d → d → d となります。つまり、それまでどのように状態が遷移していようと「00」で d に遷移です。そして、状態 d において 1 を受け取れば c（受理状態）です。
以上をまとめれば、「001 で終わる記号列」は、「必ず受理される」とわかります。よって、正解は 1 です。
コメント