Microsoft PowerPoint - 09pda.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - 09pda.ppt"

れんましのしま
4 years ago
Views:

1 6. プッシュダウンオートマトン : 6.2. PDAの言語 6.3. PDA と CFG の等価性 (6.4. 決定性プッシュダウンオートマトン ) 1/26

2 プッシュダウンオートマトン (PDA)= オートマトン + プッシュダウンスタックプッシュダウンスタック食堂のお盆 ( 最近見ない ) コインケースいわゆる stack 入出 LIFO: Last In First Out 2/26

3 直感的な説明 PDA とは ε-nfa が stack を一つ持った機械モデル入力有限状態を持つ制御部分 (ε-nfa) 受理 / 拒否 LIFO 型の記憶装置 ( 記憶領域には限りがない ) 3/26

4 直感的な説明入力 PDA とは ε-nfa が stack を一つ持った機械モデル有限制御部 LIFO 型出力受理条件 : 1. 受理状態 2. スタックが空動作プロセス : 1. 入力を1 文字読む ε- 動作のときは0 文字 2. 入力 x とスタックの一番上の文字 y に応じて状態遷移する 3. スタックを操作する : 1. 一番上の文字を取り出して捨てる 2. 一番上の文字を書き換える 3. 2に加えていくつかの文字を記憶 4. 入力が終わって受理条件を満たしていたら受理入力が残っているならステップ1へ 4/26

5 直感的な説明例 ) L = { ww R w {0,1}* } を受理する PDA 入力 ε q 0 q 1 ε q 2 0,1 0,1 入力が終了し同時にスタックが空なら受理入力文字をスタックに積む入力文字とスタックの先頭の文字が同じなら先頭の文字をスタックから破棄 5/26

6 直感的な説明例 ) L = { ww R w {0,1}* } を受理する PDA 入力 ε ε 入力が終わり q 0 q 1 q 2 スタックも空になるので受理 ε 0,1 0,1 L の要素なら受理条件を満たす状態遷移が存在する L の要素でないならどんな遷移をしても受理条件を満たせない 6/26

7 PDA の形式的定義 PDA P=(Q, Σ, Γ, δ, q 0, Z 0, F) 有限制御部 Q: 状態の有限集合 Σ: 入力アルファベット Γ Z 0 q 0 : q 0 Q を満たす初期状態 F: F Q を満たす受理状態 Γ: スタックアルファベット ; スタックに記憶する文字集合 Z 0 : Z 0 Γを満たす開始記号 ; スタックには最初にこの文字が1つ入っているとする ( スタックの [ 底 ] を判定するための便宜上の文字 ) Σ 7/26

8 PDA の形式的定義 PDA P = ( Q, Σ, Γ, δ, q 0, Z 0, F ) 関数 δ: Q Σ Γ 2 Q Γ* δは現在の状態入力 1 文字スタックのトップの文字 X が与えられ次の状態 Xを置き換える文字列 Y を返す関数入力 1 文字はεも可 Yは右が可 : Σ δは非決定的なので同じ入力に対する行き先が複数ありえる有限制御部 Z 0 Γ Y =ε; X の破棄 Y が 1 文字 ; X の置換 Y が 2 文字以上 ; 置換 + 追加 8/26

9 PDA の形式的な定義例 ) L = { ww R w {0,1}* } を受理する PDA P 入力 ε q 0 q 1 ε q 2 0,1 0,1 Z 0 P = ({q 0,q 1,q 2 }, {0,1}, {0,1,Z 0 }, δ, q 0, Z 0, {q 2 }) 9/26

10 PDA の形式的な定義例 ) L = { ww R w {0,1}* } を受理する PDA P ε q 0 q 1 0,1 0,1 Z 0 ε q 2 q 0 に関する δ 入力をスタックに積む δ ( q0,0, Z0) = {( q0,0 Z0)}, δ ( q0,1, Z0) = {( q0,1 Z0)} δ( q0,0,0) = {( q0,00)}, δ( q0,1,0) = {( q0,10)} δ( q, 0,1) = {( q, 01)}, δ( q,1,1) = {( q,11)} ε 動作で q 1 に遷移 δ ( q, ε, Z ) = {( q, Z )}, δ( q, ε,0) = {( q,0)}, δ( q, ε,1) = {( q,1)} P = ({q 0,q 1,q 2 }, {0,1}, {0,1,Z 0 }, δ, q 0, Z 0, {q 2 }) 10/26

11 PDA の形式的な定義例 ) L = { ww R w {0,1}* } を受理する PDA P ε q 0 q 1 0,1 0,1 Z 0 ε q 2 q 1 に関するδ 入力とスタックのトップを比較 δ ( q1,0,0) = {( q1, ε )} δ ( q,1,1) = {( q, ε )} 1 1 入力とスタックのトップがどちらも空になったらε 動作でq 2 に遷移 δ ( q, ε, Z ) = {( q, Z )} P = ({q 0,q 1,q 2 }, {0,1}, {0,1,Z 0 }, δ, q 0, Z 0, {q 2 }) 11/26

12 PDA の図による表現関数 δ を辺のラベルで表現する a, X/α q 0 q 1 δ( q 0,a, X ) = {, ( q 1,α ), } の図示 12/26

13 PDA の図による表現例 ) L = { ww R w {0,1}* } を受理する PDA P の δ ε, Z 0 /Z 0 ε, 0/0 q 0 ε, 1/1 q 1 ε, Z 0 /Z 0 q 2 0,Z 0 /0Z 0 1,Z 0 /1Z 0 0,0/00 1,0/10 0,1/01 1,1/11 0,0/ε 1,1/ε 13/26

14 PDA の状況の関係オートマトンは状態だけで特定できた PDAでは状態 + スタックの文字列でないと状態が特定できない δ ^記法は適切でない PDAの状況とは (q,w,γ) ただし q Q: 状態 w Σ*: 残りの入力 γ Γ*: スタックの文字列この 3 つにより PDA の状態を特定できる状況は時点表示,ID(Instantaneous Description) とも言う 14/26

15 PDA の状況の関係 PDA P = ( Q, Σ, Γ, δ, q 0, Z 0, F ) において δ(q,a,x) が (p,α) を含むなら w Σ*, β Γ* に対して ( q, aw, Xβ) (p,w,αβ) P PDA の 1 ステップを表現と書く (Pがわかっているならと書く) 0ステップ以上の一般の動作を表現するときは * を使う : 1. 状況 I に対し I * I 2. 状況 I,J,Kに対し I J & J K * なら I K * 15/26

16 PDA の状況の関係例 ) L = { ww R w {0,1}* } を受理する PDA ε q 0 q 1 0,1 0,1 ε q 2 入力に対する状況の遷移 : (q 0, , Z 0 ) (q 0, 01101, 1Z 0 ) (q 0, , Z 0 ) (q 1, , Z 0 ) Z 0 (q 0, , Z 0 ) (q 0, 01101, 1Z 0 ) (q 1, , Z 0 ) 16/26

17 ε q 0 q 1 ε q PDA の状況の関係例 ) L = { ww R w {0,1}* } を受理する PDA 入力に対する状況の遷移 : (q 0, , Z 0 ) (q 1, 101, 101Z 0 ) (q 1, , Z 0 ) (q 0, 01101, 1Z 0 ) (q 1, 01, 01Z 0 ) 0,1 0,1 Z 0 (q 0, 01, 1101Z 0 ) (q 1, 01, 1101Z 0 ) (q 0, 1, 01101Z 0 ) (q 1, 01101, 1Z 0 ) (q 0, 1101, 01Z 0 ) (q 1, 1, 1Z 0 ) (q 1, 1, 01101Z 0 ) (q 1, 1101, 01Z 0 ) (q 0, 101, 101Z 0 ) (q 1, ε, Z 0 ) (q 0, ε, Z 0 ) (q 2, ε, Z 0 ) (q 1, ε, Z 0 ) 17/26

18 PDA の状況の関係 [ 定理 ] PDA P の計算プロセスを考えると (q,x,α) *(p,y,β) なら (q,xw,αγ) *(p,yw,βγ) [ 定理 ] PDA P の計算プロセスを考えると (q,xw,α) * (p,yw,β) なら (q,x,αγ) *(p,y,βγ) * * (q,x,αγ) (p,y,βγ) なら (q,x,α) (p,y,β) ではない 18/26

19 6.2. PDA の言語 PDA の受理状態 : 1. 入力を読み終わったときに受理状態にある 2. 入力を読み終わったときにスタックが空与えられたPDA P = ( Q, Σ, Γ, δ, q 0, Z 0, F ) に対して L (P) = { w ある q f F に対し (q 0,w,Z 0 ) (q * f,ε,α)} N(P) = { w ある q Q に対し (q 0,w,Z 0 ) (q,ε,ε)} * N(P) を考えるときは F は関係ないので 6つ組 (Q,Σ,Γ,δ,q 0,Z 0 ) で記述することもある日本語テキストのN(P) の定義では q F となっているが間違い (258ページ) 19/26

20 6.2. PDA の言語 PDA P によって定義される 2 種類の言語 : 1. L(P): 入力を読み終わったときに受理状態 2. N(P): 入力を読み終わったときにスタックが空 P を固定すると一般に L(P) N(P) 例 ) スタックに最後に Z 0 がいつでも残る P に対しては N(P) = Φ [ 定理 ] PDA Q に対して N(Q) = L(P) を満たす PDA P が存在 PDA P に対して L(P) = N(Q) を満たす PDA Q が存在 20/26

21 [ 定理 ] 6.2. PDA の言語 1. PDA Q に対して N(Q) = L(P) を満たす PDA P が存在 2. PDA P に対して L(P) = N(Q) を満たす PDA Q が存在 [ 略証 ] 与えられた Q から条件を満たす P を以下の通り構成アイデア : 最初にスタックの底に特別な記号 X 0 をつむ Q の計算でスタックが空 = Pの計算でスタックのトップがX 0 Q のスタックの底 :Z 0 P のスタックの底 :X 0 ε,x 0 /Z 0 X 0 Q Q の入力が終了かつスタックが空のときのみ P が受理状態でかつ入力が終了 P Q ε,x 0 /ε 21/26

22 [ 定理 ] 6.2. PDA の言語 1. PDA Q に対して N(Q) = L(P) を満たす PDA P が存在 2. PDA P に対して L(P) = N(Q) を満たす PDA Q が存在 [ 略証 ] 与えられた P から条件を満たす Q を以下の通り構成アイデア1: 最初にスタックの底に特別な記号 X 0 をつむ P の計算の模倣中にスタックが空になることはないアイデア2: Pの受理状態からQの受理状態にε 動作で遷移する入力を消費しないことに注意アイデア3: Qの受理状態ではスタックの中身をすべて破棄 22/26

23 [ 定理 ] 6.2. PDA の言語 1. PDA Q に対して N(Q) = L(P) を満たす PDA P が存在 2. PDA P に対して L(P) = N(Q) を満たす PDA Q が存在 [ 略証 ] 与えられた P から条件を満たす Q を以下の通り構成アイデア1: 最初にスタックの底に特別な記号 X 0 をつむ P の計算の模倣中にスタックが空になることはないアイデア2: Pの受理状態からQの受理状態にε 動作で遷移する入力を消費しないことに注意アイデア3: Qの受理状態ではスタックの中身をすべて破棄 Pのスタックの底 :Z 0 Qのスタックの底 :X 0 ε, 任意 /ε ε,x 0 /Z 0 X 0 P Q P P が受理状態でかつ入力が終了のときのみ Q の入力が終了かつスタックが空 23/26

24 6.3. PDA と CFG の等価性 [ 結論 ] PDAで受理できる言語 =CFGで生成できる言語定理 1. 任意のCFG Gに対し L(G)=N(P) を満たす PDA Pが存在する 2. 任意の PDA P に対し N(P)=L(G) を満たす CFG Gが存在する証明は省略 ( 難しくはないが複雑 ) 24/26

25 6.4. 決定性 PDA( 概要 ) 決定性 PDA: PDA において非決定性を取り除いたもの次の状態が一意的に決まる正則言語 DPDA の言語 PDA の言語の関係 : 正則言語 L={ww R w {0,1}*} L={wcw R w {0,1}*} DPDA PDA=CFL DPDA のクラスは実用的クラス ( 例 ;LR(k),YACC) 25/26

26 6. プッシュダウンオートマトン : 演習問題 (8) [ 問 1] 正則言語は文脈自由言語に真に含まれることを証明せよ ( 集合 A が集合 B に真に含まれるとは A B かつ A B が成立するときを言う ) 26/26

オートマトン形式言語及び演習 1. 有限オートマトンとは酒井正彦形式言語言語とは : 文字列の集合例 : 偶数個の 1 の後に 0 を持つ列からなる集合 {0, 110, 11110,

オートマトン形式言語及び演習 1. 有限オートマトンとは酒井正彦形式言語言語とは : 文字列の集合例 : 偶数個の 1 の後に 0 を持つ列からなる集合 {0, 110, 11110, オートマトン形式言語及び演習 1 有限オートマトンとは酒井正彦 wwwtrscssinagoya-uacjp/~sakai/lecture/automata/ 形式言語言語とは : 文字列の集合例 : 偶数個の 1 の後に 0 を持つ列からなる集合 {0, 110, 11110, } 形式言語 : 数学モデルに基づいて定義された言語認識機械 : 文字列が該当言語に属するか? 文字列機械受理