平成30年度 春期 午前 問4
情報に関する理論
オートマトンに関する問題
入力記号，出力記号の集合が {0, 1} であり，状態遷移図で示されるオートマトンがある。0011001110 を入力記号とした場合の出力記号はどれか。ここで，S₁ は初期状態を表し，グラフの辺のラベルは，入力／出力を表している。
〔状態遷移図〕:
初期状態は S₁（左から矢印が入っている） S₁ ──0／0──▶ S₁ （自分へ戻る） S₁ ──1／0──▶ S₂ S₂ ──0／0──▶ S₁ S₂ ──1／1──▶ S₃ S₃ ──1／1──▶ S₃ （自分へ戻る） S₃ ──0／0──▶ S₁
- ア0001000110
- イ0001001110
- ウ0010001000
- エ0011111110
答えと解説を見る
✓ これが正解ア0001000110
解説
1が二つ続いた二つ目から、出力が1になります。
このオートマトンは辺のラベルが入力と出力の対なので、状態をたどりながら1文字ずつ出力を拾っていきます。初期状態では、0を受けてもその場にとどまり、出すのは0でした。1を受けると次の状態へ進みますが、このときの出力もまだ0です。その状態でもう一度1を受けて初めて、出力が1になりました。三つ目の状態にいる間は、1を受けるたびに1を出し続けます。ただし0を受けると初期状態へ戻るので、そこから数え直しになりました。入力の0011001110を順に送ると、出力は0001000110になります。だから、その並びを挙げた肢が当たりました。1が二つ続いた二つ目から1が出る、と読み替えられます。7文字目も1にした並びは、途中の0で初期状態へ戻ることを見落とした形でした。3文字目と7文字目だけを1にした並びは、出力を一つ手前に出しています。3文字目から9文字目までを続けて1にした並びは、0で戻る辺を使っていません。
ほかの選択肢はなぜ違うのか
- イ0001001110：出力を0001001110としています。5文字目と6文字目で0を受けており、そこで初期状態へ戻るはずでした。戻ったあとは、また1を二つ受けるまで0が続きます。数え直しを飛ばしたので、1の付く位置が一つぶん多くなっているのです。
- ウ0010001000：出力を0010001000としています。1を受けた最初の時点で、もう1を出してしまう形でした。初期状態から進むときの辺には、出力として0が書かれています。1が出るのは二つ目を受けたときなので、出す位置が手前へずれました。
- エ0011111110：出力を0011111110としています。最初に1が現れてから最後の1までを、間の0も含めてすべて1で埋めた並びでした。5文字目と6文字目は0を受けているので、そこは0が出ます。0を受けたときに初期状態へ戻る辺が使われていません。
出典：平成30年度 春期 基本情報技術者試験 午前 問4
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）