AP | 有限オートマトン③

2019年3月21日木曜日

応用情報技術者試験

t f B! P L
前回は有限オートマトンの問題を解説しました。

今回は別の問題を解いてみましょう!

問題


図は、偶数個の1を含むビット列を受理するオートマトンの状態遷移図であり、二重丸が受理状態を表す。a,bの適切な組み合わせはどれか。



 (a) 0 (b) 0
 (a) 0 (b) 1
 (a) 1 (b) 0
 (a) 1 (b) 1

 (平成25年春季試験)



解き方


太い矢印から始まって、二重丸で終わるような a と b を探しましょう。

偶数個の1を含むので、例えば 0101 というビット列を想定しましょう。

① 一つ目の0

0なので、左の輪をとおり偶の状態にもどります。

② 二つ目の1

1なので、中央上側の矢印をとおり、奇の状態になります。(このとき1はとられ、1は残り1つ(奇数)になります)

③ 三つ目の0

0なので、1の数は、1つ(奇数)を維持する必要があります。そこで、b は0になります。

④ 四つ目の1

1なので、この1をとり、1の数を0(偶数)にしなければいけません。そこで a は1になります。

いかがでしたか?


今回は少しむずかしかったですね。

状態遷移図の使い方を理解しているかが有限オートマトン攻略のコツとなります。

次回は異なるトピックをとりあげます。

QooQ