計算理論 期末試験
年
月
日実施
学生番号 氏名
文字 と文字列に対して をに出現する の数とする 以下の問に答えよ
とする このとき を受理する状態数 以下のの遷移図を求めよ
½
とする このとき ½ を受理 するの状態数の最小値をを用いた式で表せ ただし 証明する必要はない
帰納的言語½¾¿を受理するを それぞれ ½ ¾ ¿とする ½ ¾ ¿を 用いて以下の言語を受理するを教科書の図のように図示せよ
½
¾
¿
½
¾
¿
½
¾
¿
とし の対応問題の実例を ½ ½
·
とする このとき以下の問に答えよ
½
½
½
となる文脈自由文法
½の生成規則を求めよ ただしを開始記号とし以外の非終端記号は大文字で書く こと
¾
·
を生成する文脈自由文法¾の生成規則を求めよ た だしを開始記号とし以外の非終端記号は大文字で書くこと
上の½と¾を用いて 任意の文脈自由文法½と¾に対して
「½¾か」
という問題が決定不能であることを証明する 以下の空欄を埋めよ
½
の ½
½
および ¾ の · には 長さ の文字列が含まれていない したがって
½
½
ア であることに注意すると
½
¾
ィ
となる したがって ウ であるための必要十分条件 は エ である の対応問題は決定不能で あるので「 ウか」という問題も決定不能である
関数に関する以下の性質を用いて となるこ とをとに関する数学的帰納法で証明せよ なお 証明なしに用いてよいものは以下の 性質だけでありそれ以外のものプリント中の補題などを用いる場合にはそれも証明 をしなければ不正解とする
性質 ならばである
帰納的に可算な無限集合が帰納的 対 関数によって枚挙できることを証明する 以下 の空欄を埋めよ
を帰納的に可算な無限集合としをを枚挙する関数とする このとき を枚挙する帰納的 対 関数をを利用して以下のように構成する
まず とする 次に に対して を
とは異なるような の列における最初 の
とする このとき
任意のに対してがと異なる という論理式は
ア
と書くことができる よって 論理式アを真にする最小のを求める式は
演算子を用いることで イ と書く
ことができる したがって
ウ
と書くことができる まとめると は以下のようになる
ウ
このが帰納的 対 関数なのは明らかである また エ
オ となるので はを枚挙する
