スタック長の 特徴付けによる 言語の非DCFL性 証明

Presentation on theme: "スタック長の 特徴付けによる 言語の非DCFL性 証明"— Presentation transcript:

1 スタック長の 特徴付けによる 言語の非DCFL性 証明
上里 友弥 　南出 靖彦 筑波大学 IPSJ PRO 98

2 または 決定性プッシュダウンオートマトン はいかにして スタックを用い マッチングを行うか

3 Σ 入力記号の集合 δ 遷移関数 F Γスタック記号の集合 δ q0 q0 * qa qb qok Q 状態集合 F 最終状態の集合 ε ∈
決定性プッシュダウンオートマトン Q 状態集合 F 最終状態の集合 初期計算状況 Σ 入力記号の集合 Γスタック記号の集合 δ 遷移関数 ⊥ q0 aabb を入力とする計算 ⊥ q0 * qa qb qok ε ∈ F a δ b

4 A B q δ : Q × Γ (Σ Q × Γ*) ∪ (ε Q × {ε}) 決定性プッシュダウンオートマトン ⊥ 計算状況 で
・ ・ ・ B q で 入力を読んで遷移するか 入力を読まずに遷移するか を決定する

5 p1 A q p2 A B A B p3 A B C δ : Q × Γ (Σ Q × Γ*) ∪ (ε Q × {ε})
決定性プッシュダウンオートマトン δ : Q × Γ (Σ Q × Γ*) ∪ (ε Q × {ε}) 入力σを消費する遷移 pop p1 ⊥ A ・ ・ ・ local q p2 ⊥ A B ⊥ A B ・ ・ ・ ・ ・ ・ push p3 ⊥ A B C ・ ・ ・

6 ε A B q p δ : Q × Γ (Σ Q × Γ*) ∪ (ε Q × {ε}) ⊥ 決定性プッシュダウンオートマトン
・ ・ ・ (入力を消費しない)遷移 A B pop q p ε ※　DPDAを知っている人向けの注意書き 　 遷移関数をこの形に制限しても良いというのは 　 フォークロア的に知られてはいましたが 　 今回はこれも明示的に示しました

7 * * * q0 qa qa qb qok∈F a a b ⊥ ⊥ ⊥ ⊥ ⊥ 定義 語wを受理する( M(w) = true ).
wを全て読んだのちに F を訪れる． 定義 言語Lを受理する. w ∈ L iff wを受理する． 例 {an bn | n ≧ 1}はDPDAで受理できる． ★ a a b b * * * ⊥ ⊥ ⊥ ⊥ ⊥ q0 qa qa qb qok∈F

8 { an bn }∪{ an b2n }はDCFLではない
スタックの 高さ ✗ an bn bn スタックが殆ど 空になってしまう 読んだ文字数 （経過時間）

9 an bn b bn-1 マッチング Match[x,y] 任意のn について xn, xn y, xn y2, ... は受理されないが
ここまでは 受理しない ここで 初めて受理 マッチング Match[x,y] 任意のn について 　xn, xn y, xn y2, ... は受理されないが 　xn yn は受理される ならば，マッチングをしているという． ただし，x, yは 空でない文字列

10 ✔ 発表の流れ 定義 決定性プッシュダウンオートマトンと そのクラスDCFLとは何かを復習 マッチングを形式的に定義
{ an bn } ∪ { an b2n } がDCFLでないことを示す マッチングをすると 　スタックが殆ど空になる直感がある 入力の周期性とスタック中の周期性 マッチングにはスタックの全体が必要 殆ど空になることが形式化し証明 ✔ ✓

11 q A B ⊥ 周期的な入力と周期的なスタック cn cm β cn cm cn cn cn ε遷移のないDPDAで γ β β β α
・ ・ ・ A ⊥ B q cn cm β ε遷移のないDPDAで 文字 cが無限に長くやってくる計算を考えると， 計算に周期性があらわれる！ γ β β β α cn cm cn cn cn

12 α,β, γは w にだけ依存する wm wn 補題 : 周期的な入力と周期的なスタック と考えて良い γ β α 任意のDPDAで
計算に周期性があらわれる！ α,β, γは w にだけ依存する と考えて良い α β γ wm wn

13 an 👀👀 γ β α ⊥ マッチングするには何が必要か？ bnとマッチングするには anを復元するには この辺りまでは みなくてはならない
スタックをどこまでポップしなければ ならないだろうか？ anを復元するには 少なくともどこまでみなければ ならない？ α ・ ・ ・ γ β ⊥ an この辺りまでは みなくてはならない 👀👀

14 αまでみない場合に 何が起こるか？ γ β ・ ・ ・ an bn を受理！ β β α β ⊥ α ⊥ ⊥ an bn

15 bn an am α γ β α β γ β β β α ⊥ ⊥ ⊥ ⊥ an+m bn を誤認 αまでみない場合に 何が起こるか？
・ ・ ・ γ β ⊥ bn α β ⊥ γ β an+m bn を誤認 ・ ・ ・ β β α ⊥ ⊥ an am

16 an 👀👀 γ β α ⊥ 定理 : マッチングはそこそこ大変 bn を読んでいる間に，スタックの 高さが定数 Ha,b 以下になる．
マッチング Match[a,b] を行っ ているならば， bn を読んでいる間に，スタックの 高さが定数 Ha,b 以下になる． α ・ ・ ・ γ β ⊥ an 👀👀

17 an bn いつ Ha,b とするのか? Ha,b ??? 定理により，Ha,b 以下にはなることが分かったが，
受理するまでどれぐらいの位置で そのようにするかを考えたい． an bn Ha,b ??? 受理!

18 an bn 定理 : マッチング成功直前で Ha,b とする Ha,b Ra,b aとbにだけ依存する 定数 Ra,bが存在し，
受理!

19 定理 : マッチング成功時で高々 Ha,b + Ra,b
aとbにだけ依存する 定数 Ha,b , Ra,bが存在し， Ha,bとなるのは 入力の残りがRa,bになってからである，ので… an bn Ha,b Ra,b 受理! Ra,b

20 { an bn }∪{ an b2n }はDCFLではない
✗ ≤ Ha,b+ Ra,b bs を読んでからはじめて受理 bt を読んでからはじめて受理 とする計算状況 及び s < tが存在 これは明らかに矛盾．

21 関連研究 { an bn , an b2n | n ≧ 1 }の非DCFL性を 周期的な入力は周期的なスタックを生成する
Ginsburg & Greibach : Deterministic context free languages, 1966. { an bn , an b2n | n ≧ 1 }の非DCFL性を 　 類似した方法で証明している マッチングでは本質的にスタックを空にする Li & Vitányi : A New Approach to Formal Language Theory by Kolmogorov Complexity, 1995. Glier : Kolmogorov Complexity and Deterministic Context-Free Languages, 2003. DCFL版のポンピング補題 Harrison : Introduction to Formal Language Theory, 1978. Yu : A Pumping Lemma for Deterministic Context-free Languages, 1989.

22 { w wR | w ∈ {a,b}* , wRはwの反転} [5.2]
帰納的可算言語 {ap | pは素数} {an bn cn | n ≧ 1} [5.4] {an bn2 | n ≧ 1} 文脈自由言語 {an bn,an b2n | n ≧ 1} [5.1] { w wR | w ∈ {a,b}* , wRはwの反転} [5.2] { x # y xR z | x,y,z ∈ {a,b}* } [5.6] 決定性文脈自由言語

23 まとめ 直感 証明したこと 周期的な入力は周期的なスタックを生成 一度はスタック全体を読むことになる 受理直前にスタックが殆ど空にする
入力の中で個数の 　比較をしているよう 　な場合には， 受理段階での 　スタックの高さは 　殆ど空になる． マッチングをしていると， 受理段階でのスタックの 　高さは， 一様に定数H + R以下になる 周期的な入力は周期的なスタックを生成 一度はスタック全体を読むことになる 受理直前にスタックが殆ど空にする

24 今後の課題 {an bn cn | n ≧ 1} 非決定性プッシュダウンオートマトンに対しても同様の議論 ができないか？
　 は同じような原因でダメであるように思えるが…？ 決定性2階プッシュダウンオートマトンに対しても同様の議論 は可能か？ Parsing Expression Grammar などの 本質的にスタックを用い ていそうな体系に対しても同様の議論は可能か？

25 フォーマルなステートメント群

26 DCFL版ポンピング補題 (iteration theorem)

27 { an bn cn | n ≧ 1} はDCFLではない
? スタックの 高さ スタックが殆ど 空になってしまう an bn cn 読んだ文字数 （経過時間）

28 an bn Fしない b bn-1 改訂マッチング Match[x, y, E] 任意のn について
ここまでは Fしない ここで 初めてF 改訂マッチング Match[x, y, E] 任意のn について 　xn, xn y, xn y2, ... では E を訪ねないが 　xn yn では E を訪ねる ならば，マッチングをしているという． ただし，x, yは 空でない文字列

29 an bn を読んだことが分かるか? { an bn cn | n ≧ 1} を受理するDPDA M （が存在したとすると）
到達可能性解析 !! an bn を読んだときに 特殊な状態を訪れるDPDA M’を 構成することができる！

30 （後ろ向き）到達可能性解析 w2 wi ∈ L c2 w1 c1 F w3 c3 wn cn Pre(F,L) がregular set

31 Pre( F , c* ) を監視する an bn を読んだことが分かるか?
{ an bn cn | n ≧ 1} を受理するDPDA M （が存在したとすると） Pre( F , c* ) を監視する an bn を読んだときに 特殊な状態を訪れるDPDA M’を 構成することができる！