アルゴリズム論 過去問06年

1.ポスト対応問題
(1)文脈自由言語k=4の例
ポスト対応問題のインスタンスをなんとなく(110,01),(10,0)(001,111),(1,11)とおく。

すると、L(x1,x2,x3,x4)={1#10#11#100#110001011}
になる。

これより、文脈自由文法は
S→ij# S xijR
S→ε

(2)2つの文脈自由文法が作る言語の和集合は空集合かどうかを判定する問題は非可解
ポスト対応問題の非可解性から還元。
教科書にyes,noが逆だが同じ問題があった。
(1)とは全く関係ない。

2.言語{1^p | pは素数}を1テープ標準TMで認識
有名な「エラトステネスのふるい」の問題ですね。

具体的には、

1番目の1は無視。しるしつけとく。

while(テープの左はしから右に見ていって、印がついてない記号がまだある){
if(その記号が最後の文字)　return 受理
その1の桁数の倍数番目の1にしるし。　既に印ついてるのは無視。
}
return 非受理

これでO(n^2)かな？
sqrt(n)まで調べればいいとか使えば、もうちょい高速化できそう。