6/1 課題(グループ)　

課題内容

• 有限状態機械の1つであるオートマトンをオートマトンのシミュレータを用いて，グループ単位で講義時間内に(12：10まで)なるべくたくさん作る(提出プログラムは後でも動くが，評価は12:10の時点でのものとする).
• 同じオートマトンをグループ内の別々の人が作成しても1つと数えるので，うまく分業してたくさん作成するようにする(全員が別々にやるよりも，グループ内部で2,3人の小グループを作って，チェックしながらやった方が効率があがるかもしれない)．
• 最初の問題だけはあらかじめ公開してあるが，2問目以降にアクセスするためのパスワードは，大部分の 受講者が最初の問題の解き方が分かってから公開する．

手順の詳細

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

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

  

練習用のオートマトンを作り，提出する

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」を選ぶ。
   • 全部消して作り直すには，[File]->[New]->[Deterministic Finite Automaton]を選ぶ．
   • できあがりは下図のようになる。

     

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

     

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

     

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

5. 作成したオートマトンを「File」メニューの「Save」で「1.txt」というファイル名を付けてデスクトップに保存にする．
6. ターミナルウィンドウを開いて，

   /home08/ktanaka/bin/report601 1
   

   と入力する．「/home08/ktanaka/bin/report601」は提出コマンド名で，「1」は問題番号を表すパラメータである．別の問題番号の問題を解答する場合は，この「1」該当する問題番号，に取り替える必要がある．

   作成したオートマトンが正しく動作する場合は，

   課題 1 を提出しました．
   グループ 26 の6/1 の課題の提出状況
   課題 1 は6 月 1 日 8 時 28 分にユーザktanakaによって提出済み
   課題 2 は提出されていません
   課題 3 は提出されていません
   課題 4 は提出されていません
   課題 5 は提出されていません
   課題 6 は提出されていません
   課題 7 は提出されていません
   課題 8 は提出されていません
   課題 9 は提出されていません
   課題 10 は提出されていません
   

   のようなメッセージが出て終了する．たとえば，

   

   のように，間違っていたオートマトンのファイルを指定した時には，

   The result of input (abac) must be Yes, but returns No
   グループ 26 の6/1 の課題の提出状況
   課題 1 は提出されていません
   課題 2 は提出されていません
   課題 3 は提出されていません
   課題 4 は提出されていません
   課題 5 は提出されていません
   課題 6 は提出されていません
   課題 7 は提出されていません
   課題 8 は提出されていません
   課題 9 は提出されていません
   課題 10 は提出されていません
   

   のようなメッセージが出る．このメッセージの例では，「abac」という入力に対して，本来は 「Yes」(終状態)となるのに「No」(終状態以外)となってしまったということを表している．

7. ---

   注意

   • 終状態に更に入力があって他の状態に移るものも許す
   • 複数の状態が終状態であっても良い

   ---

   問題へのリンク

   グ ループで解く問題は全部でで13問ある．アクセス制限がかけてあり，ユー ザ名は，「joho」，パスワードは皆の準備ができたところで，口頭で説明する．