Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


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’を 構成することができる!


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

Similar presentations


Ads by Google