オートマトンシミュレータの使い方　

手順の詳細

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

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

  

練習用のオートマトンを作る

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

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

2. 状態とその間の関係を考え、図を紙に描く。
3. シミュレータに図を入力する。
   • 状態を作るには、ウインド左上に並んでいる中にある赤丸のボタンをクリックした後、作った状態を置く場所をクリックする。
   • 状態が変化する規則を作るには、ウインド左上に並んでいる中にある線分のボタンをクリックした後、「元の状態」から「次の状態」までドラッグする。すると、状態間に青色の矢印が引かれ「none」と表示される。「none」と書かれた所を右ボタンでクリックすると、「a, b, c, d, else, delete」というメニューが出るので、入力文字を選ぶ。「else」は、「他の文字全て」を意味する。
   • 終了状態を選ぶには、状態を右ボタンクリックして「Final State」を選ぶ。
   • 「A」と書かれたボタンを選ぶと、画面上に文字を書くことができるが，実行には関係がない．
   • 状態や状態間の矢印を消すには、それぞれを右ボタンクリックして「delete」を選ぶ。
   • 全部消して作り直すには，[File]->[New]->[Deterministic Finite Automaton]を選ぶ．
   • できあがりは下図のようになる。

     

4. チェック表をもとに作成したオートマトンのテストをする。
   • 緑色の三角ボタンをクリックすると、オートマトンの実行がはじまる。開始状態が緑色になり、画面下の左端の桝目に緑色の三角が現われる。
   • キーボードから「a」「b」「a」「c」と順にタイプすると、下図のように二重丸の終了状態が緑色になり、「解錠」できたことが分かる。

     

   • 緑色の三角ボタンを再度クリックするとオートマトンの状態を元に戻すことができるので、チェック表の他の入力についてもテストする。「否」と予想した入力をタイプした後、二重丸の終了状態が緑色になっていないことを確認する。例えば下は「aabac」と入力した後の状態である。緑になっている状態が二重丸でないので「否」という予想通りになっていることが分かる。

     

   • 次の状態がないような入力が入ると，緑になっている状態がなくなってしまう．これはプログラムで言うとエラーにあたるが，この問題中ではエラーも「否」と 同等に判定する．エラーとなるオートマトンも，「エラー状態」に対応する状態を 作って，「else」の矢印が出ていない状態に「エラー状態」へのelseの矢印をつ ければ，エラーとならないオートマトンになる．