＝＝＝課題９＝＝＝ 受付開始日時 2015-06-26 11:30 (2015-06-30 16:00) 受付終了日時 2015-07-08 18:00 閲覧設定 提出者本人と教員のみ閲覧・コメント可（個別指導） 学生による再提出の許可 再提出を許可する ●必須課題9-1 [記述(pdf)] 有限状態機械 課題に関する説明 ・２入力記号集合に対する１クロック遅延の有限状態機械を実現するＣプログラムを考えよう． ・１クロック遅延の機械とは１クロック前に入力した入力記号を新たな入力後に表示する機械のことである． ・http://www.kameda-lab.org/lecture/2015-tsukuba-algorithm/dfa2015.c (1) ムーアマシンの定義を述べなさい． (2) ミーリーマシンの定義を述べなさい． (3) 本プログラムで示されている機械の５要素のうち，入力アルファベット（記号）集合，開始状態，遷移関数，受理状態集合を，授業中の表記に倣って書き下しなさい． ※受理状態は空集合であることに注意． (4) 状態i (プログラム中でいう ttable[i][*], i=0,1,2) の意味を，１クロック遅延の出力作業に合わせた形で日本語でそれぞれ説明してみなさい． (5) １クロック遅延を出力する有限状態機械をミーリーマシンで実現するためには，どのように出力関数を構成するべきか，授業に例に倣って書き下しなさい． ・先頭に学籍番号・氏名・課題番号を示すこと． ●必須課題9-2 [プログラム(zip)] １クロック遅延を出力する機械 課題に関する説明 ・課題9-1で挙げたＣプログラムに対して，１クロック遅延出力が出来るように，出力関数に相当する部分を加えなさい． ・プログラム内のコメントとして，出力関数に相当する部分を，授業に習って書き留めること． ・ただし，初回のみ"-"という記号を出力するものとする．（出力アルファベットは0,1,-の３つ．） ・010010111という入力を行って，１クロック遅延が実現できていることを示しなさい． ・プログラムソースの先頭に，学生番号，氏名，課題名をコメントで記入すること． ・プログラムで工夫した部分について、プログラムソースの何行目付近を確認してほしいか明記し（複数場所可）、其々の場所では何かしらの説明をコメントの形でプログラム中に書き込むこと． ・実行結果は，Result.txtに保存すること． ・Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。 ⇒誰かに教えてもらった場合：その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を独自の説明で数行以上書き込むこと。 （教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） ⇒誰かに教えてあげた場合：その学生（氏名・学籍番号）をプログラム先頭に記すこと。 ⇒お互いに相談した場合：お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。 ◇発展課題9-A [プログラム(zip)] ５入力アルファベットに対する１クロック遅延 課題に関する説明 ・課題9-2のプログラムをベースにして，入力アルファベット集合を{a,b,c,d,e}，出力アルファベット集合を{*,a,b,c,d,e}として，１クロック遅延するプログラムを作成しなさい． ・プログラムの改変は出来るだけ小規模にとどめておくことが望ましい． ・acebbbdddeeeという入力を行って，１クロック遅延が実現できていることを示しなさい． ・可能であれば，指定された入力記号以外を受け付けないようにプログラムを改良しなさい． ・プログラムソースの先頭に，学生番号，氏名，課題名をコメントで記入すること． ・プログラムで工夫した部分について、プログラムソースの何行目付近を確認してほしいか明記し（複数場所可）、其々の場所では何かしらの説明をコメントの形でプログラム中に書き込むこと． ・実行結果は，Result.txtに保存すること． ・Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。 ⇒誰かに教えてもらった場合：その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を独自の説明で数行以上書き込むこと。 （教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） ⇒誰かに教えてあげた場合：その学生（氏名・学籍番号）をプログラム先頭に記すこと。 ⇒お互いに相談した場合：お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。 ◇発展課題9-B [プログラム(zip)] ２６入力アルファベットに対する任意の有限要素機械の読込 課題に関する説明 (1) 課題9-Aのプログラムをもとに，ミーリーマシンの４要素（受理状態集合は考えない）をファイルから読み込んで実行するプログラムを作成しなさい．ファイルは引数で与えること． (2) 読み込むファイルは， ・#で始まる行はコメント ・入力アルファベット集合（各記号はアルファベット１文字） ・状態は番号で区別 ・初期状態は番号で指定 ・出力アルファベット集合（各記号はアルファベット１文字） ・遷移関数，出力関数は１行ずつ１つ定義 とする．下記に例を示す． === DFAset_9B.txt === # Input symbols 01 # Number of states 3 # Start state 2 # Transition table (current state, input, next state) 0 0 0 0 1 1 1 0 0 1 1 1 2 0 0 2 1 1 # Output table (mealy) (current state, input, output) 0 0 1 0 1 1 1 0 0 1 1 0 2 0 - 2 1 - ================== ・課題9-2の機械に相当するテキストファイルをDFAset-92.txtとして用意すること． ・課題9-Aの機械に相当するテキストファイルをDFAset-9A.txtとして用意すること． ・実行結果を，Result92.txt, Result9A.txtとして用意すること． ・DFAset_9B.txtはどのような有限状態機械を現しているか，説明を試みなさい(Text-9B.txtに示すこと)． ・プログラムソースの先頭に，学生番号，氏名，課題名をコメントで記入すること． ・プログラムで工夫した部分について、プログラムソースの何行目付近を確認してほしいか明記し（複数場所可）、其々の場所では何かしらの説明をコメントの形でプログラム中に書き込むこと． ・Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。 ⇒誰かに教えてもらった場合：その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を独自の説明で数行以上書き込むこと。 （教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） ⇒誰かに教えてあげた場合：その学生（氏名・学籍番号）をプログラム先頭に記すこと。 ⇒お互いに相談した場合：お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。