入力記号, 出力記号の集合が{0, 1} であり,状態遷移図で示されるオートマトンがある。001101110 を入力記号とした場合の出力記号はどれか。ここで, Si は初 期状態を表し,グラフの辺のラベルは,入力/出力を表している。
ア 0001000110
イ 0001001110
ウ 0010001000
エ 0011111110
解説を読む
正解：ア
解説：
入力が001101110となっているので上位ビットから順にアウトプットの様子をトレースします。
最初の00はS1で遷移しアウトプットも0ですのでアウトプットも00となります。
３桁目の１ではじめてS2に遷移します。この際のアウトプットは0です。
ここまででアウトプットの上位３桁が000で確定しましたのでウ,エの正解は無くなりました。
インプット４桁目は1なのでS2からS3へ遷移します。その際のアウトプットは1です。
インプット５桁目は0なのでS3からS1へ遷移します。その際のアウトプットは0です。
インプット6桁目は0ですのでS1の中で遷移しアウトプットは0です。
ここまでのアウトプット状況は000100となっており、絞り込んだア,イの選択肢では次の７桁目が違います。
インプット７桁目は１なのでS1からS2に遷移します。その際のアウトプットは0です。
上位７ビットが0001000であることが確定しましたのでこの時点で正解はアとなります。
念のため残りビットも遷移させてみます。
８ビット目のインプットは１なのでS2からS3に遷移し、アウトプットは1となります。
９ビット目のインプットは１なのでS3で遷移し、アウトプットは1となります。
最後の10ビット目は0なのでS3からS1に遷移しアウトプットは0となります。
以上によりアウトプットは0001000110となりアが正解となります。
解説を閉じる
コメント