計算理論 期末試験
年
月
日実施
学生番号 氏名
·
に対して
で を反転した文字列
で の
と を入れ替えた文字 列を表すとする
例えば
に対して
である
また
とする
このとき
以下の言語を受理する状態数
以下の
の遷移図を求 めよ
·
8
++*54 +*+4 ,*,4
8
18
,5*54 6*64 7*74
+*+3 ,*,3 5*53 6*63 7*73 ,*64
7*74 +*+4 ,*,4
8
-2*24
7*74
5*54 6*64
5*54 6*64 8
.8
/+*53 ,*63
8
02*24 :
++*76 +*+6 ,*,6
:
3:
,7*76 8*86
+*+5 ,*,5 7*75 8*85
,*86
9*96 +*+6 ,*,6
:
-4*46
9*96
7*76 8*86
7*76 8*86 :
.:
/+*75 ,*85
:
07*76 8*86 :
19*95
:
29*96
左の
は の左端の空白を探して処理
右の
は の未探索部分を探して処理
·
9
++*65 +*+5 ,*,5 8*85 6*65 7*75 9
,6*65 7*75
+*+4 ,*,4 6*64 7*74 8*84 ,*75 9
-3*34
3*34
6*64 7*74
6*65 7*75 9
.9
/+*64 ,*74
9
03*35
+*+5 ,*,5 8*85 6*65 9
27*75
6*65 7*75 3*35 9
18*85
:
++*76 +*+6 ,*,6 9*96 7*76 8*86 :
,7*75 8*85
,*86 :
-4*45 4*45
7*75 8*85
7*76 8*86 :
.:
/+*75 ,*85
:
0+*+6 ,*,6 9*96 7*76 :
38*86
7*76 8*86 4*46 :
29*96
+*+5 ,*,5 :
17*76 9*95 8*86
左の
は の左端の空白を探して処理
右の
は の未探索部分を探して処理
を帰納的可算言語とし
を
を受理する
とする
このとき
以下の言語が常に帰納的可算である場合にはそれを受理する
を構成し
そうでない場 合は以下の言語が帰納的可算にならないような
½と
¾の反例を挙げよ
½
¾
½
¾
受理
受理
受理
½
¾
½
¾
とすると
½も
¾も帰納的可算である
ところが
½¾は帰納的可算ではない
½ ¾
½
¾
受理
受理 受理
½
¾
½
¾
とすると
½も
¾も帰納的可算である
ところが
½ ¾は帰納的可算ではない
とし
の対応問題の実例を
½ ½
·
とする
このとき
以下の問に答えよ
½
½
となる文脈自由文法
に対して
生成規則
を求めよ
½
½
½
½
·
となる文脈自由文法
に対して
生成 規則
を求めよ
と
から
文脈自由文法
の生成規則
を
と定義する
この
を用いて
文脈自由文法が曖昧か否かが決 定不能であることを証明する
以下の空欄を埋めよ
証明は
ア
が解を持つ ための必要十分条件が
イ
が曖昧である ことを示せばよい
½
が
の解である仮定する
このとき
の後
の導出に よって以下のような非終端記号列を得ることができる
ウ
½
½
ウ
エ
½オ
½となるので
ウ
は
カ
の後
の導出によって得ることができる
これらの導出は同 じ非終端記号列を生成する二つの異なる導出なので
異なる構文木を持つ
ゆ えに
は曖昧である
逆に
が曖昧であると仮定する
と
は曖昧ではないので
が曖 昧であるためには
一方が
の後
の導出が続き
他方が
の後
の導出が続き
かつ
生成される終端記号列が同一である場合だけである
これら二つの導出を持つ終端記号列が同一であることから
キ
½
½
となるような
·が存在する
したがって
ク
½ケ
½となり
は解
コ
½を持つ
関数
に関する以下の
つの性質を用いて
となることを
と
に関する数学的帰納法で証明せよ
なお
証明なしに用いてよいもの は以下の
つの性質だけであり
それ以外のもの
プリント中の補題など
を用いる場合に は
それも証明をしなければ不正解とする
ならば
である
のとき
を
に関する帰納法で証明する
のとき
左辺
右辺
のとき
が成り立つとして
のとき
左辺
右辺
性質
帰納法の仮定
のとき
が成り立つとして
のとき
が成り立つことを
に関する帰納法で示す
のとき
が成り立つとして
が成り立つことを示す
右辺
帰納法の仮定と性質
性質
左辺
のとき
が成り立つとして
が成り立つことを示す
右辺
に関する帰納法の仮定と性質
に関する帰納法の仮定
性質
