Microsoft PowerPoint - 13pda-n.ppt [互換モード]

Size: px

Start display at page:

Download "Microsoft PowerPoint - 13pda-n.ppt [互換モード]"

こおがながだき
4 years ago
Views:

1 6. プッシュダウンオートマトン : DAとCFGの等価性 (6.4. 決定性プッシュダウンオートマトン ) 1/27 プッシュダウンオートマトン (DA)= オートマトン + プッシュダウンスタックプッシュダウンスタック食堂のお盆 ( 最近見ない ) コインケースいわゆる stack LIFO: Last In First Out 入出 2/ 直感的な説明 DA とは -NFA が stack を一つ持った機械モデル入力有限状態を持つ制御部分 (-NFA) 受理 / 拒否 LIFO 型の記憶装置 ( 記憶領域には限りがない ) 3/27 受理条件 : 1. 受理状態 2. スタックが空直感的な説明 DA とは -NFA が stack を一つ持った機械モデル動作プロセス : 入力出力 1. 入力を 1 文字読む有限 - 動作のときは0 文字制御部 2. 入力 x とスタックの一番上の文字 y に応じて状態遷移する 3. スタックを操作する : 1. 一番上の文字を取り出して捨てる 2. 一番上の文字を書き換える 3. 2に加えていくつかの文字を記憶 LIFO 型 4. 入力が終わって受理条件を満たしていたら受理入力が残っているならステップ1へ 4/ 直感的な説明例 ) L = { ww R w {0,1}* } を受理する DA 直感的な説明例 ) L = { ww R w {0,1}* } を受理する DA 入力入力文字をスタックに積む入力が終了し同時にスタックが空なら受理入力文字とスタックの先頭の文字が同じなら先頭の文字をスタックから破棄 5/ 入力入力が終わりスタックも空になるので受理 L の要素なら受理条件を満たす状態遷移が存在する L の要素でないならどんな遷移をしても受理条件を満たせない 6/27 1

2 DA の形式的定義 DA =(, Σ, Γ, δ, q 0,, F) : 状態の有限集合有限制御部 Γ Σ: 入力アルファベット q 0 : q 0 を満たす初期状態 F: F を満たす受理状態 Γ: スタックアルファベット ; スタックに記憶する文字集合 : Γを満たす開始記号 ; スタックには最初にこの文字が1つ入っているとする ( スタックの [ 底 ] を判定するための便宜上の文字 ) Σ 7/ DA の形式的定義 DA = (, Σ, Γ, δ, q 0,, F ) 関数 δ: Σ Γ 2 Γ* Σ 有限制御部 δ は現在の状態入力 1 文字スタックのトップの文字 X が与えられ次の状態 Xを置き換える文字列 Y を返す関数入力 1 文字はも可 Y=; Xの破棄 Yは次が可 : Yが1 文字 ; Xの置換 δは非決定的なので Yが2 文字以上 ; 置換 + 追加同じ入力に対する行き先が複数ありえる Γ 8/ DA の形式的な定義例 ) L = { ww R w {0,1}* } を受理する DA 入力 =({q 0,q 1, }, {0,1}, {0,1, }, δ, q 0,, { }) 9/ DAの形式的な定義例 ) L = { ww R w {0,1}* } を受理する DA q 0 に関するδ q 0 q 入力をスタックに積む 1 ( q,0, Z ) {( q,0 Z )}, ( q,1, Z ) {( q,1 Z )} ( q,0,0) {( q,00)}, ( q,1,0) {( q,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)} =({q 0,q 1, }, {0,1}, {0,1, }, δ, q 0,, { }) 10/ DA の形式的な定義例 ) L = { ww R w {0,1}* } を受理する DA q 1 に関するδ 入力とスタックのトップを比較 ( q1,0,0) {( q1, )} ( q,1,1) {( q, )} 1 1 入力とスタックのトップがどちらも空になったら動作でに遷移 ( q1,, Z0) {( q2, Z0)} =({q 0,q 1, }, {0,1}, {0,1, }, δ, q 0,, { }) 11/ DA の図による表現関数 δを辺のラベルで表現する a, X/α δ( q 0,a, X ) = {, ( q 1,α ), } の図示 12/27 2

3 DA の図による表現例 ) L = { ww R w {0,1}* } を受理する DA の δ, /, 0/0, 1/1, / 0, /0 1, /1 0,0/00 1,0/10 0,1/01 1,1/11 0,0/ 1,1/ 13/ DAの状況の関係オートマトンは状態だけで特定できた DAでは状態 + スタックの文字列でないと状態が特定できない δ ^記法は適切でない DAの状況とは (q,w,γ) ただし q : 状態 w Σ*: 残りの入力 γ Γ*: スタックの文字列この 3 つにより DA の状態を特定できる状況は時点表示,ID (Instantaneous Description) とも言う 14/ DAの状況の関係 DA = (, Σ, Γ, δ, q 0,, F ) においてδ(q,a,X) が (p,α) を含むなら w Σ*, β Γ* に対して ( q, aw, Xβ) (p,w,αβ) DA の 1 ステップを表現と書く (がわかっているならと書く ) 0ステップ以上の一般の動作を表現するときはを使う : * 1. 状況 I に対し I * I 2. 状況 I,J,Kに対し I J & J * K なら I * K 15/ DA の状況の関係例 ) L = { ww R w {0,1}* } を受理する DA 入力に対する状況の遷移 : (q 0, , ) (q 0, 01101, 1 ) (q 0, , ) (q 1, , ) (q 0, , ) (q 0, 01101, 1 ) (q 1, , ) 16/ DA の状況の関係例 ) L = { ww R w {0,1}* } を受理する DA 入力に対する状況の遷移 : (q 0, , ) (q 1, , ) (q 0, 01101, 1 ) (q 1, 01101, 1 ) (q 0, 1101, 01 ) (q 1, 1101, 01 ) (q 0, 101, 101 ) (q 0, 01, 1101 ) (q 1, 101, 101 ) (q 1, 01, 1101 ) (q 1, 01, 01 ) (q 0, 1, ) (q 1, 1, 1 ) (q 1, 1, ) (q 1,, ) (q 0,, ) (,, ) (q 1,, ) 17/ DA の状況の関係 DA の計算プロセスを考えると (q,x,α) *(p,y,β) なら (q,xw,αγ) (p,yw,βγ) * DA の計算プロセスを考えると (q,xw,α) *(p,yw,β) なら (q,x,αγ) (p,y,βγ) * (q,x,αγ) (p,y,βγ) * なら (q,x,α) (p,y,β) * ではない 18/27 3

4 DAの受理状態 : 1. 入力を読み終わったときに受理状態にある 2. 入力を読み終わったときにスタックが空与えられたDA = (, Σ, Γ, δ, q 0,, F ) に対して L () = { w ある q f F に対し (q 0,w, ) (q * f,,α)} N() = { w ある q に対し (q 0,w, ) (q,,)} * N() を考えるときは F は関係ないので 6つ組 (,Σ,Γ,δ,q 0, ) で記述することもある日本語テキストのN() の定義では q F となっているが間違い (258ページ) 19/27 DA によって定義される2 種類の言語 : 1. L(): 入力を読み終わったときに受理状態 2. N(): ( ) 入力を読み終わったときにスタックが空例 ) スタックに最後に Z 一般に L() N() 0 がいつでも残るに対しては N() = Φ DA に対して N() = L() を満たす DA が存在 DA に対して L() = N() を満たす DA が存在 20/27 1. DA に対して N() = L() を満たす DA が存在 2. DA に対して L() = N() を満たす DA が存在 [ 略証 ] 与えられたから条件を満たすを以下の通り構成アイデア : 最初にスタックの底に特別な記号 X 0 をつむの計算でスタックが空 = の計算でスタックのトップがX 0 1. DA に対して N() = L() を満たす DA が存在 2. DA に対して L() = N() を満たす DA が存在 [ 略証 ] 与えられたから条件を満たすを以下の通り構成アイデア1: 最初にスタックの底に特別な記号 X 0 をつむの計算の模倣中にスタックが空になることはないアイデア2: の受理状態からの受理状態に動作で遷移する入力を消費しないことに注意アイデア3: の受理状態ではスタックの中身をすべて破棄のスタックの底 : のスタックの底 :X 0,X 0 / X 0 の入力が終了かつスタックが空のときのみが受理状態でかつ入力が終了,X 0 / 21/27 のスタックの底 : のスタックの底 :X 0, 任意 /,X 0 / X 0 が受理状態でかつ入力が終了のときのみの入力が終了かつスタックが空 22/ DA と CFG の等価性主張 : DA で受理できる言語 =CFG で生成できる言語受理条件は [ 入力が終わった時点でスタックが空 ] 定理 1. 任意の CFG G に対し L(G)=N() を満たす DA が存在する 2. 任意の DA に対し N()=L(G) を満たす CFG G が存在する 23/ CFG G に対して L(G)=N() を満たす DA が存在すること任意のCFG Gに対し L(G)=N() を満たす DA が存在する [ 証明のアイデア ] G における最左導出を DA のスタックを使って模倣する G x: 終端記号列 A α: 残り最左の非終端記号 Aαをスタックに積む Aを書き換えながら入力と比較 24/27 4

5 DA に対して N()=L(G) を満たす CFG G が存在すること任意の DA に対し N()=L(G) を満たす CFG G が存在する [ 証明のアイデア ] における [ スタック記号を1つ破棄する ] 動作を文法の1つの導出ルールに対応付けるの [ 状態 p からスタック記号 X を破棄して状態 q に遷移する ] ことを文法 G の非終端記号 [pxq] に対応付けるこれを一つの記号とみなす 25/ 決定性 DA( 概要 ) 決定性 DA=DAにおいて非決定性を取り除いたもの次の状態が一意的に決まる正則言語 DDA の言語 DA の言語の関係 : 正則言語 L={ww R w {0,1}*} L={wcw R w {0,1}*} DDA DA=CFL DDA のクラスは実用的クラス ( 例 ;LR(k),YACC) 26/27 大雑把なまとめ Turing のマシンモデルとChomskyの文法 DFA NFA 正則表現 (Type 3) 決定性 DA DA LBA Turing マシン文脈自由文法 (Type 2) 文脈依存文法 (Type 1) 制限なし (Type 0) 27/27 5

Microsoft PowerPoint - 3.ppt [互換モード]

Microsoft PowerPoint - 3.ppt [互換モード] 3. プッシュダウンオートマトンと文脈自由文法 1 3-1. プッシュダウンオートマトンオートマトンはメモリがほとんど無かったこの制限を除いた機械を考える理想的なスタックを利用できるようなオートマトンをプッシュダウンオートマトン (Push Down Automaton,PDA) という 0 1 入力テープ 1 a 1 1 0 1 スタッb 入力テープを一度走査したあとク2 入力テプを度走査したあと