計算理論期末試験

(1)

計算理論期末試験

年

月

日実施

学生番号氏名

とするただし図において○は状態を表す

£に対して^¼^£

½

と遷移する初期状態が^¼で受理状態が^½となる

½を下に遷移を書き加えることで完成させよ

,

*

,

+

½

¾

½

£に対して ^½^½^¾^½^£

¾

½

¾

½

と遷移する初期状態と受理状態が^½となる ^¾を下に遷移を書き加えることで完成させよ

0

,

+*/-

,/- //. /*/-

(2)

の^½との^¾を用いて上の偶数長の文字列^½^·½^¾に対して中央にを挿入するすなわち ^¼^½^·½^¾ ^£ ^½^·½^¾ と遷移するを構成するこのときの^½との^½を同一視し下に遷移を書き加えることでを完成させよただし ^½と^¾の遷移は書き加える必要はない

1

+

1

,

1

0

//. /-.

(3)

£に対してをの反転とし ^£に対して ^£ とするこのとき以下の定理が成り立つ

定理^½ が帰納的であればは帰納的である定理^¾ が帰納的であればは帰納的である

定理^¿ とが帰納的可算であればは帰納的である

これらの定理と対偶およびという性質を用いてそのことを明記しながら以下を証明せよ

が帰納的であればも帰納的である

が帰納的でなければも帰納的でない

が帰納的でなければも帰納的ではない

が帰納的可算あるが帰納的でなければは帰納的可算でない

(4)

とし ^£を以下のように定義する

は同じ長さの異なる文字列を含む

が帰納的でないこと証明する以下の空欄を埋めることで証明を完成させよまずと文字列^£から任意の入力に対してとは無関係に

のときには受理言語がとなりのときには受理言語が空となる ^½を考えるすなわち

½

のとき

となる ^½はの受理状態の後に入力とだけを受理する遷移を加えることで構成できる

が帰納的であると仮定するこのときとなるが存在する

このは入力に対してがと

きは受理ときは非受理となる

このを用いて以下のような ^¼を構成する

½

非受理受理

受理非受理

¼

このとき以下が成り立つ

¼

½

は

½

したがって ^¼ となる

またがので^¼もした

がってはとなるがこれはがでないことに矛盾するゆえにはではない

(5)

としの対応問題の実例を ^½ ^½

·

とするまた ^½ をに含まれない相異なる記号とし

½

とするさらに ^½と^¾を以下のように定義する

½

¾

½

ここで^£に対してはを反転した文字列を表す

½を生成する文脈自由文法^½ ^½ に対して ^½を求めよ

¾を生成する文脈自由文法^¾ ^¾ に対して ^¾を求めよ

とするこのとき上の^½と^¾を用いて「^½^¾ か」という問題が決定不能であることを証明する以下の空欄を埋めよ

文字に対して文字列に対して文字列 ^½ ^¾に対して ^½ ^¾ となるので½

½

となるよって ^½と^¾は

½

¾

となるしたがって ^½^¾ ^£

となる

が解^½ を持つと仮定するこのとき

となるのでとなるしたがって

である

逆にと仮定するこのときとなるのでであるしたがっては解^½ を持つ

つまりが解を持つための必要十分条件はとなることであるしたがって「か？」という問題は決定不能であるゆえにその否定問題である「か？」という問題も決定不能である

(6)

!!関数に対してを以下のように定義する

¼

·½

このとき以下の式が成り立つことをに関する数学的帰納法で証明せよ

·½

" "

計算理論 期末試験