スライド

プッシュダウン・オートマトン
直観的な説明
プッシュダウン・オートマトン (PDA)：スタック付の
"-NFA。
- 入力の他にスタックの先頭を読む
- 状態を遷移させると同時に、スタックの先頭を除いて
0 個以上の記号を押し込む
1
例：Lwwr
-
= fwwR j w 2 f0; 1gg を認識する PDA。
1111 の受理を考えよう
2
形式的な定義
PDA は P
= (Q; ; ; Æ; q0; Z0; F ) で与えられる。こ
こで、
Q：状態の有限集合
- ：入力記号の有限集合
-
- ：スタック記号の有限集合
Q
- Æ : Q [ f"g ! 2
：推移関数
- q0：初期状態
- Z0 2 ：スタックの開始記号
-
F
Q：受理状態の集合
3
例：p.2 の PDA は以下のように表せる
P = (fq0; q1; q2g; f0; 1g; fZ0; 0; 1g; Æ; q0; Z0; fq2g)
ここで、Æ は以下の通り
"
0
1
Z0 f(q1; Z0)g f(q0; 0Z0)g f(q0; 1Z0)g
q0 0 f(q1; 0)g f(q0; 00)g f(q0; 10)g
1 f(q1; 1)g f(q0; 01)g f(q0; 11)g
Z0 f(q2; Z0)g
;
;
q1 0
;
f(q1; ")g
;
1
;
;
f(q1; ")g
Z0
;
;
;
q2 0
;
;
;
1
;
;
;
4
時点表示：PDA の動作を表す方法
- 途中の状況を時点表示 (q; w; ) で表す。
q:状態、w:残りの入力系列、 :スタックの内容
- 1 ステップの動きを時点表示の列で表現する
(p; ) 2 Æ(q; a; X ) のとき、
(q; aw; X ) ` (p; w; )
0 ステップ以上を、` で表す
5
例：次の PDA
に 1111 を入力したときの動作：
(q0; 1111; Z0) ` (q1; "; 1111Z0)
(q0; 1111; Z0) ` (q1; "; 11Z0)
(q0; 1111; Z0) ` (q2; "; Z0)
(q0; 1111; Z0) ` (q2; 11; Z0)
(q0; 1111; Z0) ` (q2; 1111; Z0)
6
7
時点表示の列に関する 3 つの性質 (定理 6.5、定理 6.6)
- PDA の動作を表す時点表示の列に対して、入力に余
分な入力列を追加してもその PDA の動作を表す
- PDA の動作を表す時点表示の列に対して、スタック
に余分な記号列を追加してもその PDA の動作を表
す
- PDA の動作を表す時点表示の列に消費されない入力
があるとき、その入力を削除してもその PDA の動作
を表す
8
PDA が表す言語
最終状態による受理
- PDA
P = (Q; ; ; Æ; q0; Z0; F )
が最終状態によ
り受理する言語
L(P ) = fw j (q0; w; Z0) ` (q; "; ); q 2 F g
空スタックによる受理
- PDA
P = (Q; ; ; Æ; q0; Z0; F )
が空スタックに
より受理する言語
N (P ) = fw j (q0; w; Z0) ` (q; "; ")g
9
空スタック受理から最終状態受理
= (Q; ; ; ÆN ; q0; Z0; F ) とするとき、
N (PN ) = L(PF ) を満たす PDA PF が存在する
略証：以下のように PN から PF を構成する
PF = (Q [ fp0; pf g; ; [ fX0g; ÆF ; p0; X0; fpf g)
定理 6.9：PN
10
最終状態受理から空スタック受理
= (Q; ; ; ÆF ; q0; Z0; F ) とすると
き、L(PF ) = N (PN ) を満たす PDA PN が存在する
略証：以下のように PF から PN を構成する
PN = (Q [ fp0; pg; ; [ fX0g; ÆN ; p0; X0; ;)
定理 6.10：PF
11
PDA と CFG の等価性
PDA と CFG の等価性を示そう
12
CFG から PDA(空スタック受理) へ
変換の基本的アイデア
- スタック上で最左導出を模倣する
(q; w; A) ` (q; w; )
()
A ) - 入力記号とスタックの先頭の記号を打ち消す
(q; aw; a) ` (q; w; )
- 入力を読み切ったときにスタックが空になる
(q; w; S ) ` (q; "; ")
()
S)
w
左
13
G = (V; T; Q; S ) に対して、L(G) =
N (P ) を満たす PDA P が存在する
略証：以下のように G から P を構成する
P = (fqg; T; V [ T; Æ; q; S; ;)
定理 6.13：CFG
- 各変数について、
Æ(q; "; A) = f(q; ) j A ! 2 Qg
- 各終端記号について、
Æ(q; a; a) = f(q; ")g
14
例：次の CFG を PDA に変換
S
!
0S 1 j "
PDA の遷移関数は、
Æ(q; "; S ) = f(q; 0S 1); (q; ")g;
Æ(q; 0; 0) = f(q; ")g
Æ(q; 1; 1) = f(q; ")g
導出と遷移の対応は、
(q; 0011; S )
) 0S 1
`(q; 0011; 0S 1)
`(q; 011; S 1)
)00S 11
`(q; 011; 0S 11)
`(q; 11; S 11)
)0011
`(q; 11; 11)
`(q; 1; 1)
`(q; "; ")
S
15
PDA(空スタック受理) から CFG へ
変換の基本的アイデア
-
(p; wu; X) ` (q; u; ) ならば、変数 [pXq℄ が w を
生成するように CFG を構成
16
= (Q; ; ; Æ; q0; Z0) に対して、
L(G) = N (P ) を満たす CFG G が存在する
略証：以下のように P から G を構成する
G = (fS g [ f[pXq℄ j p; q 2 Q; X 2 g; ; R; S )
規則 R は以下の規則からなる
- 各状態 p について、 S ! [q0Z0p℄
定理 6.14：PDAP
17
略証 (続き)
- 各状態 q 、各 a
2
[ f"g、各スタック記号 X
につ
いて、
(r; ") 2 Æ(q; a; X ) に対して、
[q; X; r℄ ! a
(r; Y1 Yk ) 2 Æ (q; a; X ) (k > 0) に対して
すべての状態 r1 rk の組合せについて、
[q; X; rk℄ ! a[rY1r1℄[r1Y2r2℄ [rk 1Ykrk℄
18
例：次の PDA を CFG に変換
Æ(q0; 1; Z0)
Æ(q0; 1; 1)
Æ(q1; 1; 1)
Æ(q1; "; Z0)
S
!
[q0Z0q1℄ !
[q01q1℄ !
[q1Z0q1℄ !
[q11q1℄ !
= f(q0; 1Z0); (q1; Z0)g
= f(q0; 11); (q1; 1)g
= f(q1; ")g
= f(q1; ")g
[q0Z0q0℄ j [q0Z0q1℄
1[q01q1℄[q1Z0q1℄ j 1[q1Z0q1℄ j 1[q01q1℄[q11q1℄ j 1[q11q1℄ j "
1
遷移と導出の対応は、
(q0; 111; Z0)
`(q0; 11; 1Z0)
`(q1; 1; 1Z0)
`(q1; "; Z0)
`(q1; "; ")
S
[q0Z0q1℄
)1[q01q1℄[q1Z0q1℄
)11[q11q1℄[q1Z0q1℄
)111[q1Z0q1℄
)111
)
19

Download Report