「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 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文字のパスワードを覚えてロックし,
パスワードを打つと解除される電子錠.
- 最初は解除状態(=終了状態)だとする.
- 解除状態のときは,文字キーが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」という入力は与えられない.