基本情報技術者 2018年 春期 午前（科目A） 問04

有限オートマトンの入力出力変換【午前解説】

正解の理由

解法ステップ

1. 初期状態 S1 を確認する。
2. 入力列を左から順に1文字ずつ処理する。
3. 現在状態と入力に合致する遷移をたどり、遷移ラベルの右側（出力）を順次並べる。
4. 遷移先の状態を現在状態に更新して次の入力へ進む。
5. 最後まで処理した出力列を選択肢と照合する。

選択肢別の誤答解説

• ア: ア 0001000110 — 正解。上記手順で一文字ずつシミュレーションして得られる出力列と一致します。
• イ: 0001001110 — 8文字目（右から3番目）の出力が誤っており、S3 の 1 を自己ループと見なした際の出力変化を正しく反映していません。
• ウ: 0010001000 — 前半の遷移（S1→S2、S2→S3 など）の出力扱いを誤り、3〜4文字目の出力が逆転しています。
• エ: 0011111110 — 中盤以降をすべて 1 とした出力だが、S1 や S2 に戻る 0/0 遷移を無視しており不正解です。

よくある誤解

• S3 の 1/1 を「1 を読むと必ず S1 に戻る」と誤解して遷移先を間違える。実際は S3 の 1 は自己ループで S3 に留まります。
• 出力を状態に依存すると誤解して Moore 型と混同する。ここは遷移ラベルに出力がある Mealy 型で、入力ごとに即座に出力が決まります。
• 出力列の長さミス：入力列と出力列の長さは常に等しい（各入力に対して一つの出力がある）ことを忘れると桁合わせで誤る。

補足コラム

# 状態を文字列で管理する簡易シミュレータ
trans = {
    ('S1','0'): ('S1','0'),
    ('S1','1'): ('S2','0'),
    ('S2','0'): ('S1','0'),
    ('S2','1'): ('S3','1'),
    ('S3','1'): ('S3','1'),
    ('S3','0'): ('S1','0'),
}
def run(input_seq):
    state = 'S1'
    out = []
    for c in input_seq:
        state, y = trans[(state,c)]
        out.append(y)
    return ''.join(out)

print(run("0011001110"))  # -> 0001000110

FAQ