演習2 計算モデル

目的

有限状態機械の1つであるオートマトンをシミュレータを用いて作り、その能力と限界を知る

演習の手順

• 演習時間中はグループを作り、グループ単位でオートマトンの作成実験を行う
  1. グループを作る
  2. オートマトンシミュレータをダウンロードし、実行する
  3. 練習用のオートマトンを作り、実行する
  4. 問題にあるオートマトンを可能な限り沢山作る。 演習時間内に最も沢山作ったグループを表彰する。
• 個人単位でレポートを作成し、6月4日(日)23:59までに提出する

手順の詳細

グループを作る

• 3名で1つのグループを作る (自由に決めてよいし、前回の演習と違う人と組んでよい)
• 人が足りない場合は 2 名でもよい
• TAが巡回して、グループ番号を割り当てるので、覚えておくこと
• 遅刻した場合は1人で1グループを作り、TA に申告してグループ番号を割り当ててもらうこと

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

1. 次のリンクからCFIVEへログインし、「第2回演習用オートマトンシミュレータ」をダウンロードする: CFIVE 教材ページ
2. デスクトップにAutoSim.jarというファイルが現われる。(ブラウザの設定によっては、デスクトップ以外の場所にダウンロードされるかも知れない。)それをダブルクリックする。
3. 次のようなウインドウが開けば、準備完了である。
   

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

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

1. シミュレータを使う前に、完成したオートマトンの動きをチェックする表を作る。ここでは、何文字か入力した後、終了状態になっている(解錠する)かどうかだけに注目する。「abac」が全部入力されて始めて解錠する、途中で間違えるとやり直しが効かない、「abac」の後に何か入力しても二度は解錠しない、といった細かな点もチェックしたいので、それらが確認できるような例も含めるようにする。(問題が曖昧な場合もあるので、そのような場合は、この段階ではっきりさせておく。)

   入力	終了状態
   無し	否
   a	否
   ab	否
   aba	否
   abac	終了
   abaca	否
   aabac	否
   abacabac	否

2. 状態とその間の関係を考え、p.139 図6.5 のような図を紙に描く。
3. シミュレータに図を入力する。
   • 状態を作るには、ウインド左上に並んでいる中にある赤丸のボタンをクリックした後、作った状態を置く場所をクリックする。
   • 状態が変化する規則を作るには、ウインド左上に並んでいる中にある線分のボタンをクリックした後、「元の状態」から「次の状態」までドラッグする。すると、状態間に青色の矢印が引かれ「none」と表示される。「none」と書かれた所を右ボタンでクリックすると、「a, b, c, d, else, delete」というメニューが出るので、入力文字を選ぶ。「else」は、「他の文字全て」を意味する。
   • 終了状態を選ぶには、状態を右ボタンクリックして「Final State」を選ぶ。
   • 「A」と書かれたボタンを選ぶと、画面上に文字を書くことができる。
   • 状態や状態間の矢印を消すには、それぞれを右ボタンクリックして「delete」を選ぶ。
   • できあがりは下図のようになる。
     
4. チェック表をもとに作成したオートマトンのテストをする。
   1. 緑色の三角ボタンをクリックすると、オートマトンの実行がはじまる。開始状態が緑色になり、画面下の左端の桝目に緑色の三角が現われる。
   2. キーボードから「a」「b」「a」「c」と順にタイプすると、下図のように二重丸の終了状態が緑色になり、「解錠」できたことが分かる。
      
   3. 緑色の三角ボタンを再度クリックするとオートマトンの状態を元に戻すことができるので、チェック表の他の入力についてもテストする。「否」と予想した入力をタイプした後、二重丸の終了状態が緑色になっていないことを確認する。例えば下は「aabac」と入力した後の状態である。緑になっている状態が二重丸でないので「否」という予想通りになっていることが分かる。
      
5. 作成したオートマトンは「File」メニューの「Save」で適当なファイル名を付けて保存したり、「Print」で印刷することができる。

オートマトンを可能な限り沢山作る

次のページにある問題を解くオートマトンをできるだけ多く作ってみよ。

問題ページ(ユーザ名:project2 パスワードは演習時に通知)

• 完成したら、ホワイトボードにグループ名と番号を書き、TAによるチェックを受ける申請をする。
• TAは申請順に、完成したオートマトンが指定通りに完成しているかのチェックをする。問題があった場合は、修正をして再度チェックの申請をする。
• 申請の受け付けは適当な時間で打ち切る。(演習時間内にチェックを終えるため。)
• 時間内に最も多くのオートマトンを完成させたグループを表彰する。

レポート

オートマトンを作成をした経験をふまえて、次の2点を書いたレポートを作成し、提出せよ。

• 身のまわりの物や、よく知っているものを何か選び、その動きをオートマトンとして表現してみよ。レポートには(a)選んだものの振る舞いの日本語による説明(b)それをどのようにオートマトンの入力や状態させたかの説明(c)作られたオートマトンが正しいことをテストするための表(d)オートマトンの定義(e)考察を必ず書くこと。
• オートマトンでは表わせないものにはどのようなものがあるかを考え、理由とともに説明せよ。(教科書にもそのような例が載っているが、それ以外のものを考えよ。)

形式

レポートは(グループではなく)1人ずつ個別に作成し提出する。 必ず演習番号・氏名・学生証番号・演習に対する意見や感想を書くこと。レポートの体裁の良し悪しも採点の対象となっていることに注意せよ。

提出期限

2006年6月4日(日) 23時59分

提出方法

CFIVEまたは紙のどちらか:

• CFIVEの場合: レポートを1つのファイルにまとめ、次のページの「レポート提出」を使って提出せよ。 CFIVE 課題提出ページ
  • レポート名は「ユーザ名.拡張子」のようにせよ。例えば学生証番号が987654で、PDFファイルであれば「g987654.pdf」のようにする。
  • 提出期限内であれば、新しいレポートを提出し、古いレポートを削除することで何度でも差し換えることができる。ただしCFIVEの不調などで新しいレポートの提出ができない可能性もあるので、「提出→削除」の順で行うこと。
  • CFIVEは数十分間操作をしていないと自動的にログアウトされてしまい、次に操作をしたときに「エラー」と表示されることがある。そのような場合は、一度ログアウトして、再度ログインしてから操作を試みるとよい。
  • 期限を過ぎるとCFIVEは提出を受け付けなくなる。提出期限ぎりぎりになってトラブルがあったとしても救済できないので、1〜2日の余裕を持って提出することを強くすすめる。
• 紙の場合: 情報教育棟大演習室1の外にあるレポートボックスに提出のこと。情報教育棟の開館時間にしか提出できないことに注意せよ。

注意

他人の文章を自分の文章であるかのごとく使用することは、試験におけるカンニングと同様の不正行為なので、厳しく対処する。不正なレポートは未提出よりも評価が低い。