状態遷移図の問題を初学者向けに解く｜問題2-10
問題2-10
次の状態遷移図で表現されるオートマトンで、受理されるビット列はどれか。
ここで、ビット列は左から順に読み込まれるものとします。
選択肢は次の4つです。
ア 0000
イ 0111
ウ 1010
エ 1111正解は、
ウ 1010です。
まず「状態遷移図」とは何か
状態遷移図とは、
今どこにいるか
次に 0 または 1 を読んだらどこへ行くか
最後に受理状態にいるかを見る図です。
今回の図では、丸が3つあります。
左の状態 最初の状態
中央の状態 1を読んだ後に進む状態
右の状態 受理状態右の丸は二重丸になっています。
これは、
ここで終われば受理されるという意味です。
読み方のルール
ビット列は左から1文字ずつ読みます。
たとえば、
1010なら、
1 → 0 → 1 → 0の順番で読みます。
そのたびに、状態遷移図の矢印に従って、現在の場所を移動します。
図の意味を文章にする
今回の状態遷移図は、次のように読めます。
左の状態
左の状態からは、
0 を読んだら、左の状態のまま
1 を読んだら、中央の状態へ進むとなっています。
つまり、最初のうちは 0 が続いても左にいます。
0
00
000のように 0 だけ読んでいる間は、左の状態から動きません。
中央の状態
中央の状態からは、
1 を読んだら、中央の状態のまま
0 を読んだら、右の受理状態へ進むとなっています。
つまり、中央の状態にいるときに 0 を読むと、受理状態へ行けます。
ここがこの問題の一番大事なポイントです。
1 のあとに 0 が来ると、右の受理状態に進みます。
右の状態
右の状態は二重丸です。
つまり受理状態です。
右の状態に入ったあとなら、
0 を読んでも右のまま
1 を読んでも右のままです。
一度受理状態に入れば、その後に 0 や 1 が続いても受理されます。
このオートマトンが探しているもの
この状態遷移図は、簡単にいうと、
ビット列の中に「10」が含まれているかを見ています。
なぜなら、
1 を読む
↓
中央へ行く
↓
その次に 0 を読む
↓
受理状態へ行くからです。
つまり、
10という並びがどこかに出てくれば受理されます。
選択肢を1つずつ確認する
ア 0000
開始
0 → 左のまま
0 → 左のまま
0 → 左のまま
0 → 左のまま最後まで左の状態です。
受理状態である右の状態に行けません。
したがって、アは不正解です。
イ 0111
開始
0 → 左のまま
1 → 中央へ
1 → 中央のまま
1 → 中央のまま最後は中央の状態です。
中央の状態は受理状態ではありません。
二重丸の右の状態まで行っていないので、イも不正解です。
ウ 1010
開始
1 → 中央へ
0 → 右の受理状態へ
1 → 右のまま
0 → 右のまま途中で、
10が出てきました。
そのため、右の受理状態に進みます。
最後も右の受理状態にいるので、ウは正解です。
エ 1111
開始
1 → 中央へ
1 → 中央のまま
1 → 中央のまま
1 → 中央のまま最後は中央の状態です。
0 を読んでいないので、右の受理状態へ進めません。
したがって、エも不正解です。
まとめ
今回の問題では、状態遷移図を見て、
どのビット列を読むと、最後に二重丸の状態にいるかを確認します。
この図では、
1 のあとに 0 が来ると受理状態へ進みます。
つまり、
10 を含むビット列が受理されます。
選択肢の中で 10 を含んでいるのは、
ウ 1010だけです。
したがって、答えは、
ウです。
