平成30年度 春期 基本情報技術者試験 午前 問4
テクノロジ／基礎理論入力記号，出力記号の集合が{0，1}であり，状態遷移図で示されるオートマトンがある。0011001110を入力記号とした場合の出力記号はどれか。ここで，S1は初期状態を表し，グラフの辺のラベルは，入力／出力を表している。
出典：平成30年度 春期 基本情報技術者試験 午前 問4
- ア0001000110
- イ0001001110
- ウ0010001000
- エ0011111110
正解：ア
解説
状態遷移図は，各状態からの遷移を「入力／出力」のラベルで示しています。初期状態S1から，入力記号0011001110を1文字ずつたどりながら，遷移先の状態と出力記号を順に確認していきます。S1で0が入力されるとS1に留まり出力0，1が入力されるとS2へ遷移し出力0，S2で0が入力されるとS1に戻り出力0，S2で1が入力されるとS3へ遷移し出力1，S3で1が入力されるとS3に留まり出力1，S3で0が入力されるとS1に戻り出力0となります。この規則に従ってすべての入力をたどると，出力記号列が求まります。
選択肢ごとの解説
- ア正しい。入力0011001110を状態遷移図の規則どおりにたどると，出力記号列は0001000110になります。
- イ誤り。0001001110は，途中の遷移（S3からS1へ戻る0の出力）を誤って1のままにするなど，一部の遷移先を誤って追跡した場合に生じる出力です。
- ウ誤り。0010001000は，S1とS2の遷移における出力の対応を取り違えた場合などに生じる出力です。
- エ誤り。0011111110は，S3に一度入った後はすべて1を出力すると誤解した場合に生じる出力で，S3から0の入力でS1に戻る遷移が反映されていません。