5. オートマトン作成練習

「3. オートマトンのテストをする」で読み込んだテストには,以下のオートマトンに関するものも含まれています.どれだけ作成できるか試してみましょう.

Exercise 1: lock

暗証番号「ababc」が入力されたときに解錠する(終了状態になる)電子錠.ただし,途中間違った暗証番号を押しても,後から「ababc」と入力すれば解錠するものとする.また「ababc」と入力された後,何か入力されたら施錠する(終了状態でなくなる)ものとする.入力は「a」「b」「c」の3文字だけと仮定してよい.

Exercise 2: three a before b

入力は「a」が何回か続き,最後に「b」が1回だけ現われるものとする.「b」が現われたときに,それまでに「a」の現われた回数が3の倍数だったときだけ終了状態になる.なお,3の倍数には0を含むものとする.つまりaが1回も現われていないときも終了状態になる.

Exercise 3: three a before c

入力が先頭から「a」または「b」が何回か続き,最後に「c」が1回だけ現われるものとする.「c」が現われたとき,それまでに「a」がちょうど3回現われていた場合のみ,終了状態になるようなオートマトン.c以降のことは考えなくてよい.

Exercise 4: (a|b)*c

正規表現(regular expression)は,文字列検索などで使われる検索パターンの書き方である.正規表現では

このとき,入力が正規表現で「(a|b)*c」だったときに終了状態となるようなオートマトン.すなわち,aとbが何回か続いた後,cが入力された直後だけ終了状態となり,さらにそれ以降に文字が続いたら終了状態でなくなると考えよ.
正規表現とオートマトンについて詳しく知りたい人ははいぱーわーくぶっくを参照してください.

Exercise 5: ((a|b)*c)*

入力が正規表現で「((a|b)*c)*」だったときに終了状態となるようなオートマトン.何も入力されていないときも終了状態であることに注意.

Exercise 6: abac or baca

2つの暗証番号「abac」または「baca」のどちらが押されても解錠するような電子錠.ただし,途中間違った暗証番号を押しても,後から正しい暗証番号を入力すれば解錠するものとする.入力は「a」「b」「c」の3文字だけと仮定してよい.一度解錠されたら,どんな文字が来ても解錠されたままだとする.注: 「abaca」と入力すると4文字目と5文字目の両方で解錠する.

Exercise 7: vending machine

150円のジュースを販売する自動販売機を模倣したオートマトン.ただし,「a」を100円玉の投入,「b」を50円玉の投入,「c」を購入ボタン,「d」取消・返却ボタンとして,ジュースを出すタイミングのときを終了状態とする.なお,自販機にお金がたまるのは200円までとする(それ以上にお金がたまることはないものとする).たとえば「100円玉を2回投入し購入ボタンを押し」ても,「100円玉を投入し,取消しを押し,50円玉を投入した後で購入ボタンを押し」ても,お金が50円たまった状態となる.ただし,前者は終了状態となるが,後者は終了状態とはならない.

Exercise 8: electric lock

  • ab」を文字キー,「c」をロックキー,非終了状態をロックされた状態だとしたときに,2文字のパスワードを覚えてロックし,パスワードを打つと解除される電子錠. たとえば「abc」と押すとロックされ,続けて「ab」と押すとロックが解除される.また「abbc」と押すとロックされ,続けて「aabb」と押すとロックが解除される.

    Exercise 9: even numbers

    aとbだけからなる入力を,「a」が0,「b」が1に対応した2進数だと読みかえる.このとき,入力が2の倍数になっている場合に終了状態になっているオートマトン.何も入力がない場合は0と等しいので2の倍数だとする.たとえば「ba」や「ababa」は終了状態,「b」,「bab」は非終了状態.

    Exercise 10: multiple of three

    上と同様に入力が3の倍数のときにだけ終了状態となるオートマトン.

    Exercise 11: multiple of six

    上と同様に入力が6の倍数のときにだけ終了状態となるオートマトン.

    Exercise 12: 2A=B

    aとbだけからなる入力で,それまでに現われたbの個数(B)がaの個数(A)の2倍になっているときだけ終了状態となるようなオートマトン.ただし,2A-Bの絶対値は常に3以下となるような入力しか与えられないとする.たとえば「ababbb」は終了状態だし「bbbaab」も終了状態であるが,「aabbbb」という入力は与えられない.