5/26 演習(オートマトンとチューリングマシン)　

今日の課題は2つある．5/26 16:15までは課題(1)に，それ以降は課題(2)に取り組んで欲しい．

課題(1)

提出のテスト

注意: 課題(1)の提出にはITC-LMSは使わない．以下の説明に従って，教育用計算機システム端末のmac環境からコマンドを実行して提出する．
  1. 練習用のオートマトンを作るからオートマトンのテストをするにかけてオートマトンを作成する． 「File」メニューの「Save」で「0.txt」(この0はMy First Automatonの場合，Exercise 1-12は1-12の番号を使うこと．Rollback Automatonの場合は「r.txt」というファイル名)というファイル名を付けてダウンロードフォルダ(Downloads)にダウンロードする．ファイルが既に存在する場合は，上書き保存すること．
  2. 提出プログラムで提出する前に「ダウンロード(Downloads)」に，「{課題番号}.txt」(オートマトンの場合は{課題番号}は0-12, r, チューリングマシンの場合は課題番号はt0-t3)というファイル名でダウンロードしておく必要がある．上書きせずに別の名前でダウンロードしてしまった時は，ファイル名の変更をおこなってから提出プログラムを動かす．
  3. ターミナルを開いて， 
    /home/5320954122/bin/report526 0
    と入力する(/home/5320954122 は「情報木曜4限」担当の田中のホームディレクトリ)． 「/home/5320954122/bin/report526」は提出コマンド名で，「0」は問題番号を表すパラメータである．別の問題番号の問題を解答する場合は，この「0」該当する問題番号，に取り替える必要がある．

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

    課題 0 を提出しました．
0123456789 の5/26 の課題の提出状況
課題 0 は5 月 26 日 8 時 28 分にユーザ0123456789によって提出済み
課題 r は提出されていません
課題 1 は提出されていません
課題 2 は提出されていません
課題 3 は提出されていません
課題 4 は提出されていません
課題 5 は提出されていません
課題 6 は提出されていません
課題 7 は提出されていません
課題 8 は提出されていません
課題 9 は提出されていません
課題 10 は提出されていません
課題 11 は提出されていません
課題 12 は提出されていません
課題 t0 は提出されていません
課題 t1 は提出されていません
課題 t2 は提出されていません
課題 t3 は提出されていません
    のようなメッセージが出て終了する．たとえば，

    のように，間違っていたオートマトンのファイルを指定した時(My First Automatonのテストをパスする前に0.txt を保存した場合，rollback オートマトンの定義を0.txtに保存した場合)には， 
    The result of input (abac) must be Yes, but returns No
0123456789 の5/26 の課題の提出状況
課題 0 は提出されていません
課題 r は提出されていません
課題 1 は提出されていません
課題 2 は提出されていません
課題 3 は提出されていません
課題 4 は提出されていません
課題 5 は提出されていません
課題 6 は提出されていません
課題 7 は提出されていません
課題 8 は提出されていません
課題 9 は提出されていません
課題 10 は提出されていません
課題 11 は提出されていません
課題 12 は提出されていません
課題 t0 は提出されていません
課題 t1 は提出されていません
課題 t2 は提出されていません
課題 t3 は提出されていません
    のようなメッセージが出る．このメッセージの例では，「abac」という入力に対して，本来は 「Yes」(終了状態)となるのに「No」(非終了状態)となってしまったということを表している．
  4. チューリングマシンのファイル(t0.txt - t3.txt)の提出も 
    /home/5320954122/bin/report526  t0
    のように，問題番号t0-t3 を指定して実行する．チューリングマシンの場合は，停止時の状態(終了状態, 非終了状態)が間違っている場合以外に，10000ステップ以内に停止しない場合も間違いと見なして， 
    This Turing machine does not stop in 10000 steps for input (abba)
    のようなメッセージを出す．

  5. 注意

    なるべくたくさんのオートマトン，チューリングマシンを作って提出すると練習になる(課題の評価点に関しては多くても変わらない)．

    オンライン受講者向け情報

    体調が悪かったり，濃厚接触者になった等の理由で対面授業に参加できないなどの理由で オンライン参加している受講者は，作成したオートマトン，チューリングマシンを自分のPC上に「{課題番号}.txt」(オートマトンの場合は{課題番号}は0-12, チューリングマシンの場合は課題番号はt0-t3)というファイル名でダウンロードしておき，5/26 16:15に ITC-LMSで公開される課題「オートマトンとチューリングマシン課題1」に6/2 23:59までに提出してください．締切後に提出されたものは，定期試験までの提出は6割を上限に評価します．大学の演習室の教育用計算機システムを使っている場合は，5/26 16:15を過ぎてからも /home/5320954122/bin/report526 を使って提出してください．

    課題(2) 身のまわりのもののモデル化

    身のまわりの物や、よく知っているものを何か選び、その動きをオートマトンまたはチューリングマシンとして表現してみよ。レポートには

    を書くこと。

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

    なお，チューリングマシンを作成する場合は，以下のような抽象的な問題を扱っても良い(最後の1つは今回使うシミュレータで扱えるサイズになるかどうか微妙)． 表現する際には、どのような動作・操作をどの文字に割り当てるか、何を終了状態だとするかは自由である。例えば「踏切が閉じている」ことを終了状態に対応させてもよいし、「踏切が閉じる」ことを「a」という文字に対応させ、「a」という文字でしか遷移できない状態を作ってもよいだろう。元々，オートマトンは一般のコンピュータと比べて計算能力は劣っているので，あまりに複雑な対象を相手にしようとすると，そもそもモデル化が不可能な場合もある．また，チューリングマシンとして表現可能なものであっても，シミュレータで扱える文字数や，描画可能な状態数の制限により，シミュレータでは実現が難しい場合もある．その場合は，簡単化した問題を扱うのようにする．

    提出方法

    MS-Word, LaTeX等の文書整形システムで作成した文書を「学生証番号.pdf」という名前のPDFファイル(例 J4130395.pdf)にして， ITC-LMSの課題「オートマトンとチューリングマシン課題2」)から提出すること．LaTeXで作成した場合は高く評価する．

    補足

    オートマトンシミュレータからの図の取り込み
    プレビュー(Finderを開いてアプリケーション->プレビュー.app)を起動し，「ファイル」->「スクリーンショットを取る」->「選択部分」として範囲を指定して取り込みを実行し，PNG形式でファイルに保存する．
    PNG形式のファイルのWORD文書での利用
    「挿入」->「写真」->「ファイルから」として，作成したファイルを指定する．
    PNG形式のファイルのLaTeX文書での利用
    HWB: 27.11グラフィックスに説明がある．

    提出期限

    6月16日(木) 23:59．期限を過ぎたものは試験実施まで6割を上限に採点する．