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

目的

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

目次

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

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

  1. 右のリンクをクリックし、オートマトンシミュレータをダウンロードしましょう: AutoSim.jar (参考: シミュレータについて)
    ECCのiMac環境の標準的な設定ではホームディレクトリの中にあるDownloadsという名前のフォルダにAutoSim.jarというファイルが現われます (ブラウザの設定によっては別の場所にダウンロードされるかも知れません)．
  2. 「ターミナル」を起動します。
  3. cm11409$のようなプロンプトが表示されたら、以下の赤字部分を入力してゆきます。それぞれの行の最後には Return または Enter と書かれたキーを押します。 
    cm11409$ cd 
cm11409$ cd Downloads (空白の後のDだけ大文字です)
cm11409$ ls  (1文字目はLの小文字です)
AutoSim.jar (他のファイル名も表示されるかも知れませんが、AutoSim.jarという
            名前が現れれば問題ありません。ない場合は上の3つの手順が正しい
            かを確認し直して下さい。)
cm11409$ java -jar AutoSim.jar  (AとSが大文字であることに注意)
  4. 次のようなウインドウが開けば、準備完了です。

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

シミュレータを使って教科書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」を選びます。ファイル名を指定するウインドウが開くのでそこに例えば「ex0.txt」のような適当なファイル名を入力し、「保存」(あるいは「Save」)ボタンを押します。このオートマトンシミュレータは一度に1つのオートマトンしか編集できないので、新しいオートマトンを作成する場合には、必ず保存をしておくようにしましょう。
  6. 新しいオ一トマトンの定義を作る場合には「File」メニューの「New」の中にある「Determistic: Finite Automaton」を選びます。「Are you sure you want to clear everything for a new project?」という質問に「はい」(あるいは「Yes」)と答えると、画面に表示されているオートマトン定義は消えてなくなるので、大事な定義を保存し忘れていないか、注意しましょう。
  7. 保存したオートマトン定義を読み込みましょう。「File」メニューの「Open」を選び、以前に保存したオートマトンのファイル名(ex0.txtなど)を選び「開く」(あるいは「Open」)ボタンを押します。このとき、画面に表示されているオートマトン定義は消えてなくなるので、大事な定義を保存し忘れていないか、注意しましょう。

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

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

オートマトン作成練習

以下のような性質を持つオートマトンを作成せよ。シミュレータのテスト中の「Exercise」の番号に対応しているので、完成したらテストし、成功したら ex1.txt のような名前でファイルに保存せよ。演習終了時に何個完成したかの確認を行うので、途中でオートマトンシミュレータを終了させないこと。万が一、終了させてしまった場合は、保存したファイルを読み、再度テストをしておくこと。

  1. 暗証番号「ababc」が入力されたときに解錠する(終了状態になる)電子錠。ただし、途中間違った暗証番号を押しても後から「ababc」と入力すれば解錠するものとする。また「ababc」と入力された後、何か入力されたら施錠する(終了状態でなくなる)ものとする。入力は「a」「b」「c」の3文字だけと仮定してよい。
  2. 入力は「a」が何回か続き、最後に「b」が1回だけ現われるものとする。「b」が現われたときに、それまでに「a」の現われた回数が3の倍数だったときだけ終了状態になる。(3の倍数には0を含む、つまりaが1回も現われていないときも終了状態になる。) b 以降には入力は無いと仮定してよい。
  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: 身のまわりの機械のモデル化

身のまわりの物や、よく知っている物を何か選び、その動きをオートマトンとして表現してみよ。レポートには演習の名前・氏名・学生証番号・6月16日と7月14日の演習それぞれの改善案・レポート作成時間を書くこと。

レポート本文には(a)選んだ物のどのような振舞をオートマトンによって表現するかの言葉による説明(b)作成したオートマトンの入力を選んだ物の何に対応させたかの説明、(c)オートマトンの状態が選んだ物の何に対応させたかの説明(d)作成したオートマトンの図による定義 (e)工夫した点や苦労した点を書くこと。 
情報 レポート4: 計算のモデル
氏名: 東大 花子 学生証番号: 876543K レポート作成時間: 約5時間
6月16日演習改善案: (略)
7月14日演習改善案: (略)

課題5-1:
(a)選んだ物とその振舞: 電子錠が暗証番号を入力した後で「施錠」ボタンを
押すとロックされ、その後はロック直前に入力した暗証番号を入力するまで解
錠されない。また、解錠された後は、再び暗証番号を入力してロックすること
ができる。

(b)入力の対応
a, b 暗証番号に使われる数字ボタン
c    施錠ボタン
なお、暗証番号は2桁だとする。

(c)状態の対応
状態0: 何も入力されていない
状態1,2: 数字が1桁だけ入力された
状態3〜6: 数字が2桁以上入力された
(以下略)

(d)オートマトンの図による定義: (略)

(e)工夫した点・苦労した点: 施錠前に3桁以上の数字が入力されたときでも、
直前の2桁を暗証番号として覚えられるようにした。

ワードプロセッサなどに図を貼り込むには、Mac OS X の「グラブ」機能を使うとよい。紙で提出する場合は、オートマトンシミュレータの「File」メニュー内の「Print」メニューを使うことができる。

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

表現する際には、どのような動作・操作をどの文字に割り当てるか、何を終了状態だとするかは自由である。例えば「ゲートが開いている」ことを終了状態に対応させてもよいし、「ゲートが開く」ことを「a」という文字に対応させ、「a」という文字でしか遷移できない状態を作ってもよいだろう。現実世界の物を正確に表現しようとすると、非常に状態数が多くなるので、「面白い」と思える部分のみに注力して適宜、簡略化することをすすめる。

提出期限:
2007年8月8日(金) 正午   (8月1日(金)正午までに提出されたレポートについては、CFIVE上に提出状況を掲示する。それ以降に提出されたレポートは、形式上の不備があったとしても原則として再提出はできないので、余裕を持って提出することを推奨する。)
提出方法:
CFIVEまたは紙のどちらか
注意:
他人の文章を自分の文章であるかのごとく使用することは、試験におけるカンニングと同様の不正行為なので、厳しく対処する。不正なレポートは未提出よりも評価が低い。また、レポートの内容は独創性を重視する。似た物を対象にしたレポートが大量に提出された場合は、相対的に点数が低くなることがある。