演習: 計算のモデル (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. シミュレータに図を入力する。
   • 状態を作るには、ウインド左上に並んでいる中にある赤丸のボタンをクリックした後、作った状態を置く場所をクリックします。
   • 状態が変化する規則を作るには、ウインド左上に並んでいる中にある線分のボタンをクリックした後、「元の状態」から「次の状態」までドラッグします。すると、状態間に青色の矢印が引かれ「none」と表示される。「none」と書かれた所を右ボタンでクリックすると、「a, b, ..., j, else, delete」というメニューが出るので、入力文字を選びます。「else」は、「他の文字全て」を意味します。
   • 終了状態を選ぶには、状態を右ボタンクリックして「Final State」を選びます。
   • 「A」と書かれたボタンを選ぶと、画面上に文字を書くことができます。
   • 状態や状態間の矢印を消すには、それぞれを右ボタンクリックして「delete」を選びます。
   • できあがりは下図のようになります。
     
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. 用意された入力についてオートマトンが自動的にテストされ、その結果が表示されます。
   
   ここで
   • 「成功 <文字列:'aabac', 期待:非終了状態, 結果:非終了状態>」とあるのは、初期状態から「aabac」と入力した時点では、非終了状態になっているはずで、実際その通りなので「成功」であるという意味です。
   • 「●失敗● <文字列:'abaca', 期待:非終了状態, 結果:遷移がありません>」とあるのは、初期状態から「abaca」を入力したときのことを考えなければいけないのに、「abac」を入力した後の状態には「a」に対応する遷移がなかったのでそこで止まってしまったという意味です。
   • また「●失敗● <文字列:'aba', 期待:非終了状態, 結果:終了状態>」とあるのは、初期状態から「aba」を入力したときには非終了状態になっているはずなのに、実際には終了状態になっていたので「失敗」したという意味になります。
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」が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が入力された直後だけ終了状態となり、さらにそれ以降に文字が続いたら終了状態でなくなると考えよ。
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文字のパスワードを覚えてロックし、パスワードを打つと解除される電子錠。
   • 最初は解除状態(=終了状態)だとする。
   • 解除状態のときは、文字キーが2回以上押された後ロックキーが押されるものとする。
   • ロックキーが押された後はロック状態(=非終了状態)になる。
   • ロック状態のときは、文字キーしか押されないものとする。
   • ロック状態のときに、ロックキーを押す直前に押された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または紙のどちらか

• CFIVEの場合: レポートは1つのファイルにまとめて提出せよ。
  • ファイル名は「ユーザ名.拡張子」のようにせよ。例えば学生証番号が987654で、PDFファイルであれば「g987654.pdf」のようにする。 レポート名は自由(空欄でよい)。
  • ファイル形式はPDFのみとする。
• 紙の場合: 情報教育棟大演習室1の外にあるレポートボックス (夏休み中は情報教育棟が閉館する日がある。開館日程)

注意:

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