入力記号，出力記号の集合が{0，1}であり，状態遷移図で示されるオートマトンがある。
0011001110を入力記号とした場合の出力記号はどれか。
ここで，S1は初期状態を表し，グラフの辺のラベルは，入力／出力を表している。
正答1
解説
正解は1です。
状態遷移図（オートマトン）に入力記号を1文字ずつ与え、出力を順に記録する問題です。
図の遷移は次のとおりです。
S1では、入力0なら0を出力してS1にとどまり、入力1なら0を出力してS2へ移ります。
S2では、入力0なら0を出力してS1へ戻り、入力1なら1を出力してS3へ移ります。
S3では、入力1なら1を出力してS3にとどまり、入力0なら0を出力してS1へ戻ります。
【遷移のたどり方】
1文字目の0では、S1で0を出力し、S1のままです。
2文字目の0では、S1で0を出力し、S1のままです。
3文字目の1では、S1で0を出力し、S2へ移ります。
4文字目の1では、S2で1を出力し、S3へ移ります。
5文字目の0では、S3で0を出力し、S1へ戻ります。
6文字目の0では、S1で0を出力し、S1のままです。
7文字目の1では、S1で0を出力し、S2へ移ります。
8文字目の1では、S2で1を出力し、S3へ移ります。
9文字目の1では、S3で1を出力し、S3のままです。
10文字目の0では、S3で0を出力し、S1へ戻ります。
出力を並べると0001000110です。
【選択肢別解説】
1：○ たどった出力0001000110と一致します。
2：× 0001001110は、7文字目の1に対して1を出力しています。
このときの状態はS1で、S1で1を入力したときの出力は0です。
3：× 0010001000は、3文字目で1を出力しています。
初期状態S1で1を入力したときの出力は0なので誤りです。
4：× 0011111110は、入力が1のたびに1を出力したような結果です。
1を出力するのは、1が2回以上続いたときだけです。
【ポイント】
この機械は「1が2回以上連続したときに1を出力する」働きをしています。
状態遷移の問題は、入力1文字ごとに現在の状態と出力を書き出すと確実です。