計算理論 期末試験
年
月
日実施
学生番号 氏名
とする ただし 図において○は状態を表す
£に対して¼£
½
½
と遷移する初期状態が¼で受理状態が½となる
½を 下に遷移を書き加えることで完成させよ
1+
1,
+*+/,*,/ +*+.
-*0. ,*,.
-*0/
1+
1,
+*+.,*,. +*+/
-*0/ ,*,/
0*0/ -*0.
½
¾
½
£に対して ½½¾ ½£
¾
½
½
¾
½
と遷移する 初期状態と受理状態が½となる ¾を下に遷移を書き加えることで完成させよ
/*+.
/*,.
0,
+*/-
,*/-
+*+.,*,.
+*/.
/*+-
/*,- ,*/.
/*/. /*/-
+*+-,*,-
/*/-
/*/.
の½との¾を用いて 上の偶数長の文字列½·½¾に対して 中央にを挿入する すなわち ¼½·½¾ £ ½·½¾ と遷 移する を構成する このとき の½との½を同一視し 下に遷移を書き加 えることでを完成させよ ただし ½と¾の遷移は書き加える必要はない
2+
2, 21
0*0/ +*0. 0*-/
,*0.
-*-.
0*,/
0*+/
2+
2, 21
0*0/
0*-/
+*0.
,*0.
-*-.
0*,/
0*0/ 0*+/
£に対してをの反転とし £に対して £ とする このとき以下の定理が成り立つ
定理½ が帰納的であればは帰納的である 定理¾ が帰納的であればは帰納的である
定理¿ とが帰納的可算であればは帰納的である
これらの定理と対偶および という性質を用いてそのことを明記しな がら以下を証明せよ
が帰納的であればも帰納的である
定理 より が帰納的であればも帰納的である 定理より が帰納的であればも帰納的である
が帰納的でなければも帰納的でない
定理 の対偶よりが帰納的でなければは帰納的でない
定理の対偶とよりが帰納的でなければは帰納的でない
が帰納的でなければも帰納的ではない
定理 の対偶とより が帰納的でなればも帰納的で ない
定理の対偶とより が帰納的でなければも帰納的でない
が帰納的可算あるが帰納的でなければは帰納的可算でない
定理の対偶より が帰納的でなければ とのどちらか一方は帰納的可 算でない
仮定よりは帰納的可算である したがって は帰納的可算でない
とし £を以下のように定義する
は同じ長さの異なる文字列を含む
が帰納的でないこと証明する 以下の空欄を埋めることで証明を完成させよ まず と文字列£から任意の入力 に対して とは無関係に
のときには受理言語が となり のときには受理言 語が空となる ½を考える すなわち
½
のとき
のとき
となる ½はの受理状態の後に入力と だけを受理する遷移を加えるこ とで構成できる
が帰納的であると仮定する このとき となる が存在する この は入力 に対して が同じ長さの異なる文字列を含む ときは受理 同じ長さの異なる文字列を含まない ときは非受理となる この を用いて以下のような ¼を構成する
½
非受理 受理
受理 非受理
¼
このとき 以下が成り立つ
¼
½
½
は同じ長さの異なる文字列を含む
½
したがって ¼ となる
また が 必ず停止する ので¼も した がって は 帰納的 となるがこれは が でないこ とに矛盾する ゆえに は ではない
とし の対応問題の実例を ½ ½
·
とする また ½ をに含まれない相異なる記号とし
½
とする さらに ½と¾を以下のように定義する
½
½
½
¾
½
½
ここで£に対してはを反転した文字列を表す
½を生成する文脈自由文法½ ½ に対して ½を求めよ
½
½
½
½
¾を生成する文脈自由文法¾ ¾ に対して ¾を求めよ
½
½
½
½
とする このとき上の½と¾を用いて「½¾ か」という問題が決定不能であることを証明する 以下の空欄を埋めよ
文字に対して 文字列 に対して 文字 列 ½ ¾に対して ½ ¾ ¾
½ となるので½
½
½
½
½
½
となる よって ½と¾は
½
½
½
¾
となる したがって ½¾ £
となる
が解½ を持つと仮定する このとき ½
½
となるので となる したがって
½
¾
である
逆に と仮定する このとき となるので である したがって は解½ を持つ
つまり が解を持つための必要十分条件は となることである した がって 「 か？」という問題は決定不能である ゆえに その否定問題で ある「 ½¾ か？」という問題も決定不能である
!!関数 に対して を以下のように定義する
¼
·½
このとき 以下の式が成り立つことをに関する数学的帰納法で証明せよ
·½
" "
のとき 以下のように成り立つ
左辺½ ¼
右辺 " "
のとき·½ " " が成り立つと仮定して" のとき
左辺 ·¾
·½
·½の定義 をとみなす
" " 帰納法の仮定
" " !!関数の定義
右辺
