演習: 計算のモデル (7月17日)

目的

この演習では、有限状態機械の1つであるオートマトンをシミュレータを用いて作り、計算機の基本的な原理の一端を理解します。

目次

  1. シミュレータのダウンロードと実行
  2. 練習用のオートマトンを作り、実行する
  3. オートマトンのテストをする
  4. オートマトン作成練習 (10:15まで)
  5. 課題: 身のまわりの機械のモデル化

シミュレータのダウンロードと実行

  1. 右のリンクをクリックし、オートマトンシミュレータをダウンロードしましょう: AutoSim.jar (参考: シミュレータについて)
  2. デスクトップにAutoSim.jarというファイルが現われます。(ブラウザの設定によっては、デスクトップ以外の場所にダウンロードされるかも知れません。)それをダブルクリックします。
  3. 次のようなウインドウが開けば、準備完了です。

練習用のオートマトンを作り、実行する

シミュレータを使って教科書p.139 図6.5にある電子錠の働きをするオートマトンを作成してみよう。なお、このオートマトンシミュレータは数字のかわりに「a」から「j」までの10種類の文字を入力として受け取る。そこで教科書に出てくる「1,2,3」は「a,b,c」と読みかえる。

  1. シミュレータを使う前に、完成したオートマトンの動きをチェックする表を作りましょう。ここでは、何文字か入力した後、終了状態になっている(解錠する)かどうかだけに注目します。「abac」が全部入力されて始めて解錠する、途中で間違えるとやり直しが効かない、「abac」の後に何か入力しても二度は解錠しない、といった細かな点もチェックしたいので、それらが確認できるような例も含めるようにします。(問題が曖昧な場合もあるので、そのような場合は、この段階ではっきりさせておきましょう。)
    入力終了状態
    無し
    a
    ab
    aba
    abac終了
    abaca
    aabac
    abacabac
  2. 状態とその間の関係を考え、p.139 図6.5 のような図を紙に描く。
  3. シミュレータに図を入力する。
  4. チェック表をもとに作成したオートマトンのテストをしましょう。
    1. 緑色の三角ボタンをクリックすると、オートマトンの実行がはじまる。開始状態が緑色になり、画面下の左端の桝目に緑色の三角が現われます。
    2. キーボードから「a」「b」「a」「c」と順にタイプすると、下図のように二重丸の終了状態が緑色になり、「解錠」できたことが分かる。
    3. 緑色の三角ボタンを再度クリックするとオートマトンの状態を元に戻すことができるので、チェック表の他の入力についてもテストする。「否」と予想した入力をタイプした後、二重丸の終了状態が緑色になっていないことを確認する。例えば下は「aabac」と入力した後の状態である。緑になっている状態が二重丸でないので「否」という予想通りになっていることが分かる。
  5. 作成したオートマトンは「File」メニューの「Save」で適当なファイル名を付けて保存したり、「Print」で印刷することができる。

オートマトンのテストをする

正しいオートマトンができたと思ったら、自動的なテストを実行してみましょう。
  1. 「Test」メニューの「Test...」を選びます。すると下のようなウインドウが表示されます。
  2. 「テストファイルのURL:」と題された欄に、以下のURLを書き込み Enter を押します。コピーして貼り付けると間違いなくできるでしょう。
  3. 自動テストの内容が読み込まれると、「テスト」と書かれたボタンと左側に、オートマトンの一覧が表示されます。ここでは「My first automaton」をクリックして選択し、「テスト」を押しましょう。
  4. 用意された入力についてオートマトンが自動的にテストされ、その結果が表示されます。
    ここで
  5. このように、上で定義したオートマトンは一度解錠した後に、さらに入力されたときのことを考えていなかったことが分かりました。この点を修正し、もう一度テストしてみましょう。(修正は最後の状態から何を入力しても「失敗」を意味する状態への遷移を加えるだけです。自分でやってみて下さい。)すべてのテストに成功すると「テスト」ボタンの左の表示が「My first automaton: 成功」に変わります。

オートマトン作成練習

以下のような性質を持つオートマトンを作成せよ。シミュレータのテスト中の「Exercise」の番号に対応しているので、完成したらテストせよ。なお、新しいオートマトンを作成すると古い定義は捨てられてしまうので、その前にファイルに保存しておくようにせよ。演習時間中にどれだけ作成できるか試みてみよう。

  1. 暗証番号「ababc」が入力されたときに解錠する(終了状態になる)電子錠。ただし、途中間違った暗証番号を押しても後から「ababc」と入力すれば解錠するものとする。また「ababc」と入力された後、何か入力されたら施錠する(終了状態でなくなる)ものとする。入力は「a」「b」「c」の3文字だけと仮定してよい。
  2. 入力は「a」が何回か続き、最後に「b」が1回だけ現われるものとする。「b」が現われたときに、それまでに「a」の現われた回数が3の倍数だったときだけ終了状態になる。(3の倍数には0を含む、つまりaが1回も現われていないときも終了状態になる。)
  3. 入力が先頭から「a」または「b」が何回か続き、最後に「c」が1回だけ現われるものとする。「c」が現われたとき、それまでに「a」がちょうど3回現われていた場合のみ終了状態になるようなオートマトン。c以降のことは考えなくてよい。
  4. 正規表現(regular expression)は、文字列検索などで使われる検索パターンの書き方である。正規表現では このとき、入力が正規表現で「(a|b)*c」だったときに終了状態となるようなオートマトン。aとbが何回か続いた後、cが入力された直後だけ終了状態となり、さらにそれ以降に文字が続いたら終了状態でなくなると考えよ。
  5. 入力が正規表現で「((a|b)*c)*」だったときに終了状態となるようなオートマトン。(何も入力されていないときも終了状態であることに注意。)
  6. 2つの暗証番号が「abac」または「baca」どちらが押されても解錠するような電子錠。ただし、途中間違った暗証番号を押しても後から正しい暗証番号を入力すれば解錠するものとする。入力は「a」「b」「c」の3文字だけと仮定してよい。一度解錠されたら、どんな文字が来ても解錠されたままだとする。(注: 「abaca」と入力すると4文字目と5文字目の両方で解錠する。)
  7. 150円のジュースを販売する自動販売機を模倣したオートマトン。ただし、「a」を100円玉の投入、「b」を50円玉の投入、「c」を購入ボタン、「d」取消・返却ボタンとして、ジュースを出すタイミングのときを終了状態とする。ただし自販機にお金がたまるのは200円までとする。例えば「100円玉を2回投入し購入ボタンを押した」後は終了状態になるし「100円玉を投入し、取消しを押し、50円玉を投入した後で購入ボタンを押し」ても終了状態にはならない。
  8. ab」を文字キー、「c」をロックキー、非終了状態をロックされた状態だとしたときに、2文字のパスワードを覚えてロックし、パスワードを打つと解除される電子錠。 例えば「abc」と押すとロックされ、続けて「ab」と押すとロックが解除される。また「abbc」と押すとロックされ、続けて「aabb」と押すとロックが解除される。
  9. aとbだけからなる入力を、「a」が0、「b」が1に対応した2進数だと読みかえる。このとき、入力が2の倍数になっている場合に終了状態になっているオートマトン。何も入力がない場合は0と等しいので2の倍数だとする。例えば「ba」や「ababa」は終了状態、「b」、「bab」は非終了状態。
  10. 上と同様に入力が3の倍数のときにだけ終了状態となるオートマトン。
  11. 上と同様に入力が6の倍数のときにだけ終了状態となるオートマトン。
  12. aとbだけからなる入力で、それまでに現われたbの個数(B)がaの個数(A)の2倍になっているときだけ終了状態となるようなオートマトン。ただし、2A-Bの絶対値は常に3以下となるような入力しか与えられないとする。例えば「ababbb」は終了状態だし「bbbaab」も終了状態であるが、「aabbbb」という入力は与えられない。

レポート課題

課題5-1: 身のまわりの機械のモデル化

身のまわりの物や、よく知っているものを何か選び、その動きをオートマトンとして表現してみよ。レポートには(a)選んだものが何で、それのどのような動きを表現するかの日本語による説明(b)作成したオートマトンの入力および状態が何に対応しているかの説明(c)作成したオートマトンの定義 (図) (d)工夫した点や苦労した点 (e) 演習に対する意見や感想を書くこと。

身のまわりのものとしては例えば以下のようなものが考えられるが、これらに限らず面白いものを探してみよ。

表現する際には、どのような動作・操作をどの文字に割り当てるか、何を終了状態だとするかは自由である。例えば「ゲートが開いている」ことを終了状態に対応させてもよいし、「ゲートが開く」ことを「a」という文字に対応させ、「a」という文字でしか遷移できない状態を作ってもよいだろう。

提出期限:
2007年8月9日(木)
提出方法:
CFIVEまたは紙のどちらか
注意:
他人の文章を自分の文章であるかのごとく使用することは、試験におけるカンニングと同様の不正行為なので、厳しく対処する。不正なレポートは未提出よりも評価が低い。