平成25年度 春期 午前 問3
基礎理論
オートマトンに関する問題
図は，偶数個の 1 を含むビット列を受理するオートマトンの状態遷移図であり，二重丸が受理状態を表す。a，b の適切な組合せはどれか。
〔状態遷移図〕
状態は2つ。◎（二重丸）＝受理状態は「偶」だけ。開始を指す矢印も「偶」に入る。 ┌──────────── 1 ────────────┐ │ ↓ ◎偶 ○奇 ↑ │ │ ↑ └0┘ └b┘ │ │ └──────────── a ────────────┘ 辺は4本 … 偶→偶（0）／偶→奇（1）／奇→偶（a）／奇→奇（b）
- アa＝0 ／ b＝0
- イa＝0 ／ b＝1
- ウa＝1 ／ b＝0
- エa＝1 ／ b＝1
答えと解説を見る
✓ これが正解ウa＝1 ／ b＝0
解説
状態が変わるのは 1 を読んだときだけです。
二つの状態は、ここまでに読んだ 1 の個数が偶数か奇数かを覚えています。受理状態は偶数の側です。すでに描かれている二本の辺を読むと、0 を読んでも状態はそのままで、1 を読むと反対側へ移ることが分かります。つまり規則は、0 なら据え置き、1 なら反転です。この規則を空欄に当てはめます。奇数側から偶数側へ向かう辺は状態が反転していますので、そこに入る入力は 1 です。奇数側から自分自身へ戻る辺は状態が変わりませんので、入る入力は 0 です。実際にビット列を流して確かめると、1 を二つ読めば受理側に戻り、1 を一つだけ読んだ列は受理されません。0 だけの列は最初の状態のままなので、1 の個数を 0 個と数えて受理されます。オートマトンの空欄は、その辺で状態が変わるかどうかから先に決めるのが近道です。状態に意味の名前を与えると、入力は一意に定まります。
ほかの選択肢はなぜ違うのか
- アa＝0 ／ b＝0：奇数側から出る二本の辺がどちらも 0 になり、1 を読んだときの行き先が無くなります。同じ入力 0 に対して行き先が二つできる点でも、図として成り立ちません。
- イa＝0 ／ b＝1：二つの入力を入れ替えた形です。この組合せでは 1 を読むたびに奇数側へ留まり続けますので、1 を二つ読んだ列も受理側へ戻れず、偶数個という条件を表せません。
- エa＝1 ／ b＝1：奇数側から出る二本の辺が同じ入力 1 になり、行き先が二つに割れてしまいます。0 を読んだときの行き先も無くなるため、状態遷移が一意に定まりません。
出典：平成25年度 春期 応用情報技術者試験 午前 問3
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）