任意の言語

1. 以下の言語を認識する書き込み可能faを設計せよ.
L1 = {xx | x ∈ {a, b}*}
アルゴリズム論
レポート課題第1回の解説
e.g.
abbabb ∈ L1
aaaaaa ∈ L1
2005/12/8
TA 玉置卓
基本的なアルゴリズム
• 入力を前半と後半に
分ける
• 入力長が奇数なら
受理しない
$babbbabb&
$b’abbbabb&
$b’abbbabb”&
$b’a’bbbabb”&
$b’a’bbbab”b”&
…
• 前半部と後半部の
1文字目から一致するか
どうかチェック
全て一致なら受理
$b’a’b’b’b”a”b”b”&
$#a’b’bb”#ab”b”&
$##b’b’##b”b”&
…
$########&
abaa ∉ L1
aaa ∉ L1
入力を分割するfaの記述
1. 現在位置の記号(a or b)に’を
付けヘッドを右へ
2. ’’の付いた記号が来たら入力列は
奇数長なので非受理
それ以外は’’か&を読むまで右へ
3. ’’か&を読むと左へ移動し現在
位置の記号(a or b)に’’を付け
ヘッドを左へ
4. ’,’’の付いていない最も左のa or b
まで移動
なければ$の右まで移動
$babbbabb&
$b’abbbabb&
$b’abbbabb”&
$b’a’bbbabb”&
$b’a’bbbab”b”&
…
$b’a’b’b’b”a”b”b”&
入力を分割するfaの状態遷移図
a’,b’/R
a”,b”/R
s5
a,b/R
a/a’,R
b/b’,R
s1
s2
a”,b”,&/L
a’,b’/R
$/R
s4
s6
s3
a/a”,L
b/b”,L
前半と後半の一致をチェックする
faの記述
1. 現在位置の記号(a’ or b’)を
$b’a’b’b’b”a”b”b”&
記憶し#に書き換えヘッドを右へ
2. a” or b” が見つかるまで
ヘッドを右へ
見つかったら記憶と比較し一致
すれば#に書き換えヘッドを右へ
そうでなければ非受理
3. 現在位置の記号が&なら受理
そうでなければ最も左のa’ or b’
まで移動し1へ
$#a’b’bb”#ab”b”&
$##b’b’##b”b”&
…
$########&
a,b/L
$b’abbbabb”&
前半と後半の一致をチェックする
faの状態遷移図
a’,b’,#/R
s7
a’/#,R
s6
b’/#,R
• 入力の分割
a”/#,R
b”/#,R
s9
s8
$#a’b’bb”#ab”b”&
a’,b’,#/R
#/R
s10
a’,b’/L
計算時間の解析
&
a”,b”,#/L
a’,b’/L
f
$b’abbbabb”&
先頭と最後尾i番目の文字に印をつけて次の文字に戻るのに
(2n-4i+5)ステップだからi=1からn/2まで和をとって
n2/2+O(n)
• 前半と後半の一致をチェック $#a’b’bb”#ab”b”&
ひとつのペアの比較して戻ってくるのに(n+3)ステップで
n/2ペアについて行うから
n2/2+O(n)
合計 n2+O(n) ステップで終了する
拡張
以下の言語を認識する書き込み可能faを設計せよ.
L1 ' = {xxx | x ∈ {a, b}*}
基本的なアルゴリズム
• 入力を３分割
• 各部分の先頭から比較
$babbabbab&
$b’abbabab&
$b’abbaba”b”&
…
$b’a’b’b”a”b”a”b”&
…
$b’a’b’b”a”b”b”’a”’b”’&
$#a’b’#a”b”#a”’b”’&
…
$#########&
採点基準
• アルゴリズムの正しさ (2点)
• 書き込み可能faとしての設計 (2点)
– アルゴリズムのfaとして実現
– 状態遷移関数/図の概略
• 計算時間の解析 (2点)
– きちんと理由をつけて
× Aの部分はkステップ,…
○ Aの部分でBの操作がi回あるのでkステップ,…
• L1’ についても解いた (1点)
2. 以下の言語を認識するTMを設計せよ.
L2 = {1x | xは素数}
e.g.
11111∈ L2
11 ∈ L2
111111 ∉ L2
1 ∉ L2
前処理を行うTMの記述
基本的なアルゴリズム
• 入力xを2からx-1で
割り切れるかチェック
• カウンタに割る数kを保存
• xからkを繰り返し引き算し
0になれば非受理
引き算できなくなれば
カウンタの値kを1増やす
新たにxからの引き算を
開始
$11111BB…
$1’1’1’1’1’$’11111BB…
$1’1’1’1’1’$’11$”11BB…
$1’1’1’1’1$’11’$”11BB…
$1’1’1’11$’1’1’$”11BB…
$1’1’1’11$’11$”11BB…
$1’1’111$’11’$”11BB…
…
$11111$’11’$”11BB…
$1’1’1’1’1’$’1’1’1’$”1BB…
…
$11111$’11111’$”BB…
前処理を行うTMの状態遷移図
1,$’/R
1/R
s1
s4
$/R
B/1,L
s5
s3
$’/R
s7
1/R
s6
f1
s9
xが現在のカウンタの値kで
割り切れず,かつk=x-1
B
1/R
s8
1/$”,L
f2
$11111$’11111’$”BB…
s9
$1’1’1’1’1’$’11111BB…
1/L
割り算を行うTMの状態遷移図
引き算のループが続行可能
1,$’/L
1’/R
1/1’,R
s2
$11111BB…
$1’1’1’1’1’$’11111BB…
$1’1’1’1’1’$’11$”11BB…
$1’1’1’11$’1’1’$”11BB…
$11111BB…
B/$’,L
1. 空白記号までヘッドを
移動し$’を付け列の先頭へ
2. 1を1’に書き換え空白
記号まで移動し1を書く
3. $’まで左に移動しさらに
一番左の1まで移動して
2.へ戻る
1がなければ4.へ
4. $’から3つ目の1を$”に書き
換え左へ移動
$1’1’1’1’1’$’11$”11BB…
引き算のループが続行不能
カウンタkの値を+1して
次の引き算ループ開始
$11111$’11’$”11BB…
計算時間の解析
• 前処理が O(n2) であることは簡単にわかる
• カウンタの値がkのときの割り算ループの
計算時間はO(n3/k) なのでkについて和をとると
3
O(n logn)
これが主な計算時間
3. どんなTMによっても認識されない
{1}上の言語が存在することを示せ.
L3 = {11,111,11111,..., ?, ?, ?,...}
採点基準
• アルゴリズムの正しさ (2点)
• TMとしての設計 (2点)
– アルゴリズムのTMとして実現
– 状態遷移関数/図の概略
• 計算時間の解析 (2点)
– きちんと理由をつけて
× Aの部分はkステップ,…
○ Aの部分でBの操作がi回あるのでkステップ,…
証明方針
背理法で示す.
1. “どんなTMによっても認識されない{1}上の言語が
存在する”の否定は“{1}上の任意の言語Lに対し
Lを認識するTM M(L)が存在” (背理法の仮定)
2. 仮定のもとで“{0,1}上の任意の言語L’に対し
L’を認識するTM M’(L’)が存在”を示す
3. “どんなTMによっても認識されない{0,1}上の言語
が存在する”ことに矛盾するので仮定は誤り.
“{1}上の任意の言語Lに対し
Lを認識するTM Mが存在”
するなら“{0,1}上の任意の
言語L’に対しL’を認識する
TM M’が存在”を示す
M’は{0,1}上の言語L’を{1}上
の言語 L = {Enc( x) | x ∈ L'}
に変換してMを利用して解く
M’ の動作
入力xをEnc()で符号化
Enc(x)に対するMの動作を
模倣しMが受理/非受理に
応じてM’も受理/非受理
Enc( x) : {0,1}* → {1} *
ε →ε
0 →1
1 → 11
00 → 111
01 → 1111
10 → 11111
11 → 111111
000 → 1111111
Μ
⎧ x ∈ L' ⇔ Enc( x) ∈ L
⎨
⎩ x ∉ L' ⇔ Enc( x) ∉ L
• 総得点は
(?/20点満点)=
(?/7点満点)+(?/6点満点)+(?/6点満点)+1
採点基準
• 方針の正しさ (3点)
• 証明の正しさ (3点)