「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」が0回以上繰り返し現われるパターンを「a*」と書く． たとえば「」(空の文字列)，「aa」，「aaaaa」は， 「a*」に合う． - 連続するパターンが繰り返す場合は「
()」で囲む． たとえば「(hey)*」は，「」(空の文字列)，「hey」， 「heyhey」，「heyheyhey」などに合う． 逆に「gooo*gle」の「*」は， 直前の「o」の繰り返しを意味するので， 「google」「gooogle」「goooogle」 などに合う． - 「
|」は複数のパターンの「どちらか」を意味する． たとえば「t(hi|a|ha)nk」は， 「think」「tank」「thank」に合う．
(a|b)*c」だったときに終了状態となるような
オートマトン．
すなわち，aとbが何回か続いた後，cが入力された直後だけ終了状態となり，
さらにそれ以降に文字が続いたら終了状態でなくなると考えよ．
Exercise 5: ((a|b)*c)*
入力が正規表現で「((a|b)*c)*」だったときに
終了状態となるようなオートマトン．
何も入力されていないときも終了状態であることに注意．
Exercise 6: abac of 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文字のパスワードを覚えてロックし，
パスワードを打つと解除される電子錠．
- 最初は解除状態(=終了状態)だとする．
- 解除状態のときは，文字キーが2回以上押された後ロックキーが押されるものとする．
- ロックキーが押された後はロック状態(=非終了状態)になる．
- ロック状態のときは，文字キーしか押されないものとする．
- ロック状態のときに， ロックキーを押す直前に押された2つの文字キーを同じ順序で押されると， 解除状態になり，最初に戻る．
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」という入力は与えられない．