内容復習 CFG との等価性 PDA 非文脈自由言語まとめ内容復習 CFG との等価性 PDA 非文脈自由言語まとめ内容計算基礎論プッシュダウン・オートマトン (Pushdown Automaton) 第2回 ∼ 第4回 FA と正規表現は，本質的に等価な言語の記憶法 {0n1n|n ≤ 0} のような幾つかの単純な言語を記述不可能 . 第5回 . 宮野英次 [email protected] 今回 . より強力なプッシュダウン・オートマトン (pushdown automaton) 2009 年内容復習 CFG との等価性 PDA より強力な言語記述法: 文脈自由文法 (context-free grammar) 非文脈自由言語まとめ内容復習復習: 文脈自由文法 CFG との等価性 PDA 非文脈自由言語復習: 生成文字列文法以下の方法で生成された文字列全体を文法が生成する言語生成規則 (production) または書き換え規則 (substitution rule) の集まりからなる書き換え規則は矢印により分離された文字と文字列文字は変数と呼ばれる文字列は，変数と終端記号と呼ばれる特別な文字からなる . . . 1 開始変数を書き下す 2 書き下された変数とその変数で始まる規則を探す． 3 書き下された変数を規則の右辺で置き換える 4 変数がなくなるまでステップ 2 および 3 を繰り返す変数文字は，多くの場合大文字終端記号は，多くの場合小文字，数，特別な文字 . . ある変数が開始変数 (第 1 規則の左辺の変数とする) 文法 G1 A → 0A1 A→B B→] 文法 G1 は 3 つの規則 G1 の変数は A と B ．A は開始変数 G1 の終端記号は，0, 1, ] . . . 文法 G1 の場合 (A → 0A1, A → B, B → ]) 例えば，文字列 000]111 などを生成導出列 (derivationa) A ⇒ 0A1 ⇒ 00A11 ⇒ 000A111 ⇒ 000B111 ⇒ 000]111 まとめ内容復習 PDA CFG との等価性非文脈自由言語まとめ内容復習復習: 有限オートマトン CFG との等価性 PDA 非文脈自由言語まとめ復習: 有限オートマトン No temporary memory Finite Automaton (FA) state control temporary memory a a b b input input memory CPU 制御部 (state control) は有限の状態と遷移関数をもつ output memory 有限オートマトンの能力の限界は，直接的には，内部の記憶状態が有限個にとどまっていることに起因 program memory Automaton ⇒ 状態を無限個にすれば能力はあがりそうだが．．．どうする? ⇒ スタックを補助記憶として導入例: 自動販売機，自動ドア内容復習 PDA CFG との等価性非文脈自由言語プッシュダウン・オートマトンまとめ内容復習 CFG との等価性 PDA 非文脈自由言語プッシュダウン・オートマトン pushdown automaton (PDA) Stack 非決定性有限オートマトンに，プッシュダウン・スタックを追加 Stack input memory CPU output memory program memory state control a a b b x y z input stack Pushudown Automaton スタック: Last In, First Out (LIFO)，領域は無制限例: コンパイラ非決定性は本質的 (決定性 PDA は能力が劣る) まとめ内容復習 CFG との等価性 PDA 非文脈自由言語まとめ内容復習言語 {0n1n|n ≥ 0} を認識する PDA 非文脈自由言語 input アルファベット (入力，スタック) 0 0 0 1 1 1 push 0 0 入力アルファベットを Σ として，Σε = Σ ∪ {ε} スタック・アルファベットを Γ として，Γε = Γ ∪ {ε} stack 遷移関数の定義域 (何も読まずに動作することがある) 入力を読む Q × Σε × Γε 0 のときは，それをスタック上にプッシュそれぞれの 1 のときは，0 をスタックからポップ遷移関数はスタックへの書き込みも行うスタックが空になり，ちょうどそのときに入力が終わるならば受理遷移関数 δ は，Q × Γε の要素を返すスタックが空になるが，1 の列が残っているか，1 の列が終了したがスタックが 0 の列を含んでいる場合には拒否非決定性遷移関数 δ は，δ : Q × Σε × Γε → 2Q×Γε 1 の列の後に 0 が現れたら，その時点で入力を拒否 PDA CFG との等価性非文脈自由言語まとめ内容復習 PDA の形式的な定義 PDA CFG との等価性非文脈自由言語 PDA の計算の形式的定義入力定義 2.13 w = w1 w2 · · · wm，wi ∈ Σε プッシュダウン・オートマトンは 6 個組 (Q, Σ, Γ, δ, q0 , F )．ここで，Q, Σ, Γ, F はすべて有限集合 . M は w を受理 (accept) 以下の 3 条件を満たす状態の列 r0 , r1 , · · · , rm ∈ Q と文字列 s0 , s1 , · · · , sm ∈ Γ∗ が存在するならば，M は w を受理 1 Q は状態の集合 2 Σ は入力アルファベット 3 Γ はスタック・アルファベット 1 4 δ : Q × Σε × Γε → P(Q × Γε) は遷移関数 2 5 q0 ∈ Q は開始状態 6 F ⊆ Q は受理状態 . 3 . . まとめ PDA = NFA + スタック M1 復習 CFG との等価性 PDA の形式的な定義の準備 PDA M1 内容 PDA . r0 = q0 かつ，s0 = ε (空スタックで開始状態から始動) i = 0, · · · , m − 1 について，(ri+1 , b) ∈ δ(ri, wi+1 , a) ここで，a, b ∈ Γε と t ∈ Γ∗ について，si = at と si+1 = bt (状態，スタック，入力文字により正しく動作) rm ∈ F (入力の最後で受理状態) まとめ内容復習 CFG との等価性 PDA 非文脈自由言語まとめ内容復習 CFG との等価性 PDA PDA の例例 2.14 言語 {0n1n|n ≥ 0} を認識する PDA M1 M1 = ({q1 , q2 , q3 , q4 }, {0, 1}, {0, $}, {q1 , q4 }) M1 = ({q1 , q2 , q3 , q4 }, {0, 1}, {0, $}, {q1 , q4 }) 0 0 ∅ ∅ ∅ ∅ $ ∅ ∅ ∅ ∅ ε ∅ {(q2 , 0)} ∅ ∅ 1 0 ∅ {(q3 , ε)} {(q3 , ε)} ∅ $ ∅ ∅ ∅ ∅ ε ∅ ∅ ∅ ∅ 0 ∅ ∅ ∅ ∅ ε $ ∅ ∅ {(q4 , ε)} ∅ q1 ε {(q2 , $)} ∅ ∅ ∅ q4 復習 CFG との等価性 PDA 非文脈自由言語まとめ内容復習 PDA の例 , $ q2 $ q2 0, 0 PDA ,$ q3 1, 0 $ CFG との等価性非文脈自由言語文脈自由文法との等価性例: 2.18 言語 {ww R|w ∈ {0, 1}∗} を認識する PDA M3 q1 , 1, 0 $: スタック上の特別な文字内容文脈自由文法とプッシュダウン・オートマトンは，その記述能力において等価である 0, 0 1, 1 文脈自由言語とは，文脈自由文法によって生成できる言語定理 2.20 q4 ,$ q3 まとめ PDA の例例 2.14 言語 {0n1n|n ≥ 0} を認識する PDA M1 入力 stack q1 q2 q3 q4 非文脈自由言語 0, 0 1, 1 あるプッシュダウン・オートマトンがある言語を認識するとき，かつそのときに限り，その言語は文脈自由言語であるまとめ内容復習 PDA CFG との等価性非文脈自由言語まとめ内容復習 CFG との等価性 PDA CFL → PDA 非文脈自由言語まとめ証明のアイデアある文脈自由言語を考えるその CFG G による導出の過程 S ⇒ 0S1 ⇒ 00S11 ⇒ · · · ⇒ w ∈ A G と等価な PDA P に変換する方法を示す補題 2.21 PDA P は，入力 w に対する導出列が存在するかどうかをチェック G が w を生成するならば，その入力を受理するように設計ある言語が文脈自由であるならば，その言語を認識するプッシュダウン・オートマトンが存在する . 導出の各々のステップは，変数と終端記号からなる中間文字列書き換えが複数可能なときは，非決定性を用いて，正しい書き換えの列を推測する文字列の導出が完了したとき P が入力として受け取った文字列と導出列が一致するかどうかを調べる中間文字列の一部 (最左の変数の右側のみ) をスタック上に保持する . 内容復習 PDA CFG との等価性 . 非文脈自由言語まとめ内容復習 01A1A0 2 2 . . 3 まとめ 1 A 0 $ 補題 2.27 あるプッシュダウン・オートマトンがある言語を認識するならば，その言語は文脈自由である印となる文字 $ と開始変数をスタックに置く以下を繰り返す 1 非文脈自由言語 A 0 1 1 0 0 1 1 CFG との等価性 PDA → CFL PDA P の動作 state control PDA スタックの先頭が変数 A ならば，非決定的に A に対する規則を 1 つ選択し，規則に従い A を書き換えるスタックの先頭が終端記号 a ならば，入力から次の文字を読み，a と比較する．一致するならば，繰り返す．一致しないならば，非決定性のこの計算枝では拒否する．スタックの先頭が文字 $ ならば受理状態に入る．このとき，すべての入力文字が読み出されていたならば，これは受理を意味する . . 内容復習 CFG との等価性 PDA 非文脈自由言語まとめ内容復習証明のアイデア Case 1: 最初にプッシュした文字が最後に取り出される a を最初の動作で読み出される入力文字，b を最後の動作で読み出される文字，r を p の直後の状態，s を q の直前の状態とする状態の対 p と q に対し，文法では変数 Apq を準備 Apq から，状態 p でスタックが空の状況から，状態 q でスタックが空の状況へ P を遷移させるすべての文字列を生成するように文法 G を構成する規則: Apq → aArsb 状態が p のときに上の文字列が与えられると P はスタックの内容に関らず，その文字列を読んで状態 q に遷移する状態 q に遷移したとき，スタックの内容に変化は無い CFG との等価性 PDA まとめ構成のアイデアの続き構成のアイデア復習非文脈自由言語証明のアイデア (続き) 文字列が PDA を開始状態から受理状態へ導くとき，G がその文字列を生成するように構成する内容 CFG との等価性 PDA 非文脈自由言語 Case 2: 途中の状態 r でスタックが空になる規則: Apq → AprArq まとめ内容復習 PDA CFG との等価性正規言語と文脈自由言語正規言語，regular language 有限オートマトンで認識される言語文脈自由言語，context-free language プッシュダウン・オートマトンで認識される言語非文脈自由言語系 2.32 すべての正規言語は文脈自由言語である . Context-Free Language Regular Language . 非文脈自由言語まとめ内容復習 CFG との等価性 PDA 非文脈自由言語まとめ内容復習プッシュダウン・オートマトンの限界 A が文脈自由言語であるとする．A に依存するある数 p (ポンピング長) が存在して，s が少なくとも長さ p である A の任意の文字列であるとき，s は次の条件を満たす 5 つの断片 s = uvxyz に分割できる入力テープの内容を書き換えることができない補助記憶はスタックのみ非文脈自由言語の例: 言語 {anbncn|n 言語 {aibj ck|0 言語 {ww|w ∈ まとめ定理 2.34 (文脈自由言語に対するポンピング補題) . 無限個の可能性を記憶することが難しい非文脈自由言語 CFL に対するポンピング補題 PDA によって認識不可能な言語とは? 以下の強い条件では，処理できないような課題とは? 有限個の状態しか無い CFG との等価性 PDA ≥ 0} ≤ i ≤ j ≤ k} 1 各 i ≥ 0 について，uv ixy iz ∈ A 2 |vy| > 0，すなわち，v 6= ε または y 6= ε 3 |vxy| ≤ p |s| は s の長さ，y i は y を i 個連結したもの，y 0 は ε {0, 1}∗} . . 内容復習 PDA CFG との等価性非文脈自由言語まとめ内容復習 CFG との等価性 PDA 非文脈自由言語まとめ . 非文脈自由言語の例言語 L = {ww | w ∈ {0, 1}∗} は文脈自由言語ではない . 証明． L が CFL であると仮定して，矛盾を導く． . p をポンピング補題により与えられたポンピング長とする s = 0p1p0p1p ∈ L を考える基本方針: |vxy| ≤ p かつ vy 6= ε となるように s = uvxyz と分割する．uxz が L に属さないことを示して矛盾を導くまず，|vxy| ≤ p なので，|uxz| ≥ 3p である．従って， uxz が繰り返し列 tt ならば，t の長さは 3p/2 以上である． vxy が s のどこに位置するかによって場合分けする . .. . 例 2.38 証明 (つづき) . . . . . 1 vxy が最初の 0p に含まれる場合: vy = 0k (0 < k ≤ p) とする．このとき uxz = 0p−k1p0p1p である． |uxz| = 4p − k なので，uxz = tt ならば |t| = 2p − k/2 である．従って，t が最初の 1 のブロックの途中で終わるこ . となく，t は記号 0 で終わる．しかし，uxz は 1 で終わるので，tt と等しいことはあり得ない． s = u v x y z p p p p }| { z }| { z }| { z }| { z · · 0} 0 · · 0} 0 · · 0} 0 · · · 0 1 · · · 1 0 · · · 0 1 · · · 1 s = 0 · · 0} 0 | ·{z | ·{z | ·{z | ·{z u v x y 内容復習 PDA CFG との等価性非文脈自由言語まとめ内容復習証明 (つづき) 2 . 3 内容 4 . . 5 vxy が 1p の最初のブロックに含まれる場合: uxz が L に属さないことは場合 2 の議論の後半と同様である． PDA CFG との等価性非文脈自由言語文脈自由文法生成規則と呼ばれる再帰的な規則によって言語を記述する手段変数の集合，終端記号の集合，開始集合，生成規則の集合文脈自由言語文脈自由文法が生成した文字列の全体すべての正規言語は文脈自由言語であるプッシュダウン・オートマトン非決定性有限オートマトンに，プッシュダウン・スタックを追加文脈自由文法と記述能力が等価非文脈自由言語の存在非文脈自由言語 vxy が最初の 1p と 2 番目の 0p にまたがる場合: vy が実際には 0 を含まないときは，場合 3 の vxy が最初の 1 のブロックに含まれるときと議論は同じである．vy が少なくとも 1 個の 0 を含めば，uxz は 0p で始まり，tt = uxz を満たす t も 0p で始まる．しかし，2 つ目の t に対する 0p は uxz には存在しない．この場合もまた，uxz は L に属さない．他の場合: vxy は s の後半に含まれ，議論は vxy が s の前半に含まれる場合と対称になる．以上より，どの場合も uxz は L に属さず，L は文脈自由言語ではない Q.E.D まとめまとめ . CFG との等価性証明 (つづき) vxy が最初の 0 のブロックと最初の 1 のブロックにまたがる場合: この場合でも，y = ε なら vy = 0k となることはあり得る．そのときは場合 1 と同じ議論で uxz が tt の形にならないことを示せる．vy が 1 個でも 1 を含めば，3p/2 以上の長さを持つ t は，uyz が 1p で終わっていることから，1p で終わらなければならない．しかし，uxz 中の 1p のブロックは最後のブロック以外にないので，t を uxz 中で繰り返すことはできない．復習 PDA . . まとめ