状態遷移図をたどって出力列を求める方法
基本情報技術者試験 平成30年度春期 午前 問4 ／ 基礎理論 › 情報に関する理論
過去問にチャレンジ
入力記号，出力記号の集合が{0，1}であり，状態遷移図で示されるオートマトンがある。0011001110 を入力記号とした場合の出力記号はどれか。ここで，は初期状態を表し，グラフの辺のラベルは，入力／出力を表している。 〔状態遷移図〕
- ア
0001000110
- イ
0001001110
- ウ
0010001000
- エ
0011111110
会話形式の解説
講師入力を1文字ずつ読み、その直前の状態から進む矢印を確かめましょう。矢印の「入力／出力」の右側を記録します。
受験者1を読んだときの出力が状態によって違うので、入力だけを見て並べると間違えそうです。
講師そのとおりです。初期状態S1で最初の00を読むと、状態はS1のままで、出力は00です。
受験者続く11は、S1からS2、さらにS3へ進むので、出力は01ですね。
講師はい。次の00では、最初の0でS3からS1へ戻り、次の0でもS1に留まります。出力は00です。
受験者ここまでの出力は000100です。残りの1110は、戻ったS1から読み始めるのですね。
講師はい。残りの出力は0110なので、全体では0001000110です。正解はアです。
受験者0001001110は7文字目だけ違います。6文字目の0の後も、前の状態を引きずってしまったのでしょうか。
講師6文字目を読んだ時点でS1です。7文字目の1ではS2へ進み、出力は0なので、その列は誤りです。
受験者0010001000は3文字目を1にしていますが、最初の00の後はS1なので、3文字目の出力は0です。
講師そのとおりです。0011111110も、5文字目の入力0に対して1を出しています。S3からS1へ戻る矢印は0／0なので、ここも0です。
受験者各文字を読む直前の状態を確認し、矢印の右側だけを順に書けばよいのですね。
まとめ
正解はアの0001000110です。初期状態S1から入力を1文字ずつ読み、対応する矢印の「／」の右側を出力として記録します。入力0ではどの状態からもS1へ戻るため、その後の1を読む直前の状態を取り違えないことが大切です。
解答・解説
正解はアです
この問題のテーマ
状態遷移図をたどり、入力列に対応する出力列を求める問題です。
解き方の考え方
初期状態S1から、入力を左から1文字ずつ読みます。通った矢印のラベルは左側が入力、右側が出力なので、右側の記号を順に並べます。入力が0のときは、どの状態からでもS1へ移り、0を出力します。
選択肢ごとの解説
- ○ア 0001000110最初の「00」はS1に留まって「00」を出力します。続く「11」ではS1→S2→S3と移り「01」、次の「00」ではS1へ戻って「00」を出力します。残りの「1110」の出力は「0110」なので、つなげると0001000110です。
- ×イ 0001001110イの0001001110は、7文字目の出力を1としています。しかし、6文字目の0を読んだ時点で状態はS1です。7文字目の1ではS2へ移り、出力は0になります。
- ×ウ 0010001000ウの0010001000は、3文字目の出力を1としています。最初の二つの0を読んだ後も状態はS1なので、3文字目の1ではS2へ移って0を出力します。
- ×エ 0011111110エの0011111110は、5文字目の入力0に対する出力を1としています。図ではS3から入力0でS1へ戻る矢印に「0／0」とあるため、この位置の出力は0です。
POINT
- 各入力を読む直前の状態を確認してから、対応する矢印を選びます。
- 矢印のラベル「入力／出力」では、斜線の右側を出力列に記録します。
- 1を読んだときの出力は状態によって異なるため、入力列だけから決められません。