計算理論 期末試験
年
月
日実施
学生番号 氏名
文字 と文字列に対して をに出現する の数とする また と する このとき 以下の言語を受理する状態数 以下の の遷移図を求めよ
9
/9
+9
,9
-6*32 7*42
9
.0*02 3*32 8*51
4*42 5*52 3*31
4*41 5*51 6*61 7*71 6*31 8*81 7*41 3*32 4*42 5*52 6*62 7*72
8*52
3*32 4*42 5*52 8*82 0*02
:
0:
+:
,:
-7*43
:
/1*13 4*43 9*62
5*53 6*63 4*42
5*52 6*62 7*72 8*82 7*42 9*92 8*52 4*43 5*53 6*63 7*73 8*83
9*53
4*43 5*53 6*63 7*73 8*83 1*13
:
.8*53 9*62
<
+<
2<
,6*65 7*75 8*85
;*85
<
-9*65 :*75
<
.<
/;*84 3*34
9*94 :*:4
;*;4 6*64 7*74 8*84
<
09*65 :*75 9*95 :*:5 6*65 7*75 8*85 6*65 7*75
8*85
;*85 ;*;5
6*65 7*75 8*85
9*64 :*74
<
1;*;5 6*65 7*75 8*85
9*65 :*75 ;*;5 6*65 7*75 8*85
9*64 :*74 3*35
:
0:
+:
,:
-7*43
:
.1*13 4*43 8*52
5*53 9*93 4*42
5*52 7*72 8*82 9*92 7*42 4*43 5*53 7*73 9*93
8*53 4*43 5*53 8*83 9*93 1*12
:
/9*63 4*43
5*53 ;
1;
-;
.;
/8*54
;
02*24 9*63 5*54 6*64
7*74
5*53 6*63 7*73 8*83 9*93
8*53 5*54 6*64 7*74 8*84
9*64 5*54 6*64 7*74 9*94 2*23
;
+;
,8*84 9*94
:*73 2*24 8*83 9*93
=
3<*96
=
+=
,8*86
=
-:*76
=
.4*46 7*76 ;*85
8*86
7*75 8*85 :*:5 ;*;5
;*86 7*76 :*75
=
/=
08*86 9*96
=
1:*76
=
24*46
;*85 7*76 8*86
9*96
7*75 8*85 9*95 :*:5
;*;5
;*86 :*75
7*76 9*96
<*96
<*96
4*45
言語½¾ に対して 連接言語½¾を ½¾ ½ ½¾ ¾と定義する このとき½と¾が帰納的であるならば½¾も帰納的であることを示したい 以下の問 に答えよ
空欄を埋めた上で は正しい語に丸を付けよ
½を受理して停止する を½ ¾を受理して停止する を¾ 入力を
½
とする このとき以下のように動作する を構成する
の入力を½¾と考えてそのすべての 通りの½¾ に対して まず½を入力½に対して動かす そして ½が½を
受理する ならば¾ を¾ に対して動かし 受理しない な らば は受理しないで 停止する この動作を同時に通り 行う
は 通りの¾の少なくとも一つ が受理となるときに を受理して停止しそうでないときはを受理しないで停止する
は½¾を受理し かつ 必ず停止する ので ½¾は帰納的である
は「受理する」「受理して」でも正解
½ ¾ ¿の場合に で構成した を図示せよ ただし ½の入力½と¾ の入力¾を明記すること
に対してをアルファベットとするすべての を½¾ とする 言語
を 文字列
がによって受理されるような の集合 すなわち以下のよ うに定義する
このときの補集合 が帰納的可算でないことを示したい 以 下の証明を完成させよ
背理法で示す が帰納的可算であると仮定する このとき とな る が存在する 文字列 に対して となる場合と とな る場合について考える
のとき の定義により となる より となる
一方 のとき の定義により となる より
となり となる
したがって どちらの場合も矛盾する この矛盾は が帰納的可算であると 仮定したことから生じたのでが帰納的可算ではない
とし の対応問題の実例を ½ ½
·
とする また をに含まれない相異なる記号とし½
¾
½
とする さらに ½ ¾を以下のように定義する
½
½
½
½
½
½
¾
ここで
である このとき 以下の問いに答えよ
½を生成する文脈自由文法½ ¾½ に対して ½を求めよ
¾を生成する文脈自由文法¾ ¾ ¾ に対して ¾ を求めよ
½
½
½
½
½
½
½
½
任意の文脈自由文法に対して 「 か」という問題が決定不能であるこ とを以下のように証明する 空欄を埋めよ
½
¾
¾ とする このとき は文脈自由言語となるので となる文脈自由文法が存在する
の定義より「¾か」という問題は「½¾ か」とい う問題と同値である 一方 ½と¾の定義から ½¾となるが存在す る場合 ½より ただし½
となりさらに ¾より
½
½
½
½ となる を除く ことで½ ½ となる したがって¾であるこ とと とが解をもつ ことが同値となる これは の対応問題 が決定不能であることに矛盾する ゆえに 「 ¾か」という問題も 決定不能である
!! 関数に対する以下の性質を利用して が原子帰納的でない ことを証明せよ
性質 任意の変数原始帰納的関数½ に対して
½
½
となる定数 が存在する
を原始帰納的であると仮定する この仮定より も 原始帰納的となる 一方 !!関数の性質より
となるような定数 が存在する このとき をとおけば
となり矛盾する
