基本情報技術者講座

★　猫本　3-09　オートマトン(その1)　★

基本情報技術者　平成28年度春期　問2

次の状態遷移図で表現されるオートマトンで受理されるビット列はどれか。ここで，ビット列は左から順に読み込まれるものとする。

ア	0
イ	111
ウ	1010
エ	1111

解説

状態遷移図の受理状態は◎で表される。

よって、ウである。

解答
ウ

基本情報技術者　平成30年度春期　問4

入力記号，出力記号の集合が{0，1}であり，状態遷移図で示されるオートマトンがある。0011001110を入力記号とした場合の出力記号はどれか。ここで，S1は初期状態を表し，グラフの辺のラベルは，入力／出力を表している。

ア	0001000110
イ	0001001110
ウ	0010001000
エ	0011111110

解説

グラフの辺のラベルは，入力／出力を表しています。
(続く)

	①	②	③	④	⑤	⑥	⑦	⑧	⑨	⑩
入力	0	0	1	1	0	0	1	1	1	0
出力	0	0	0	1	0	0	0	1	1	0

よって、アである。

解答
ア

基本情報技術者　平成28年度秋期　問3

300円の商品を販売する自動販売機の状態遷移図はどれか。ここで，入力と出力の関係を"入力／出力"で表し，入力の"a"は"100円硬貨"を，"b"は"100円硬貨以外"を示し，S0～S2は状態を表す。入力が"b"の場合はすぐにその硬貨を返却する。また，終了状態に遷移する際，出力の"1"は商品の販売を，"0"は何もしないことを示す。

解説

イ	初期状態から100円硬貨を投入した場合に遷移先が決まらない(S0→S1，S0→S2)。
ウ	初期状態から100円硬貨が2枚投入された時点で商品が販売されてしまう。
エ	初期状態から100円硬貨を投入しても遷移しない。

よって、アである。

解答
ア