G I N G V I Ê N : T S . H À C H Í T R U N Gả
B M Ô N : K H M Tộ
k h o a c n t t , h v k t q s
Đ t : 0 1 6 8 . 5 5 8 . 2 1 . 0 2
E M A I L : H C T 2 0 0 9 @ Y A H O O . C O M
Lý thuy t automata và ế
ngôn ng hình th cữ ứ
Languague
Grammar
Automat
a
1
©copyright by PhD. C.T.Ha, Le Quy Don Technical
University
Bài 6. Automata đ y xu ngẩ ố
(Pushdown automata)
M C ĐÍCH:Ụ

Thi t k PDA ch p nh n CFG b ng stack r ng ho c b ng ế ế ấ ậ ằ ỗ ặ ằ
tr ng thái k t thúc;ạ ế

Bi n đ i t ng đ ng gi a PDA ch p nh n ngôn ng ế ổ ươ ươ ữ ấ ậ ữ
b ng tr ng thái k t thúc sang PDA ch p nh n b ng stack ằ ạ ế ấ ậ ằ
r ng. ỗ

Bi n đ i t ng đ ng gi a NPDA và CFG.ế ổ ươ ươ ữ
YÊU C U:Ầ

Sinh viên c th hóa các thu t toán b ng ch ng trình ụ ể ậ ằ ươ ở
nhà.
2

Automata và ngôn ng hình th c - ©copyright by PhD. C.T.Ha, Le Quy Don Technical ữ ứ
University
6.1. Khái ni m v Pushdown Automataệ ề

Ta đã bi t: ế L p RL đ c sinh ra t RG và đ c đoán nh n b i FA; CFL ớ ượ ừ ượ ậ ở
đ c sinh ra t CFG.ượ ừ

Câu h i: ỏ Li u có th đ c đoán nh n CFL b i m t FA? N u có thì ệ ể ượ ậ ở ộ ế
automata đó nh th nào?ư ế

Ví d 6.1: ụ Automata đoán nh n ngôn ng d ng:ậ ữ ạ
{0n1n}; S 0S1 | ε→

Ví d 6.2: ụ Automata đoán nh n ngôn ng d ng:ậ ữ ạ
{wcwR | w (0+1)*}; S 0S0 | 1S1 | c∈ →

Ví d 6.3: ụ Automata đoán nh n ngôn ng d ng:ậ ữ ạ
{wwR | w (0+1)*}; S 0S0 | 1S1 | ε∈ →

Ví d 6.4: ụ {a2nbn}; S aaSb | ε→
6/27/14
5
Automata và ngôn ng hình th c - ©copyright by PhD. C.T.Ha, Le Quy Don Technical ữ ứ
University
6.1. Khái ni m v Pushdown Automataệ ề
6/27/14
6

Ví d 6.5: ụ L={0n1n}= {ε, 01, 0011, 000111, …}, thi t k ế ế
DFA đoán nh n ngôn ng trên ???ậ ữ

6.2.1. Bi n đ i t ng đ ng t d ng 2 sang d ng 1ế ổ ươ ươ ừ ạ ạ
6.2.2. Bi n đ i t ng đ ng t d ng 1 sang d ng 2ế ổ ươ ươ ừ ạ ạ
6.3. S t ng đ ng gi a PDA và CFGự ươ ươ ữ
6.3.1. Bi n đ i t ng đ ng t CFG sang PDAế ổ ươ ươ ừ
6.3.2. Bi n đ i t ng đ ng t PDA sang CFGế ổ ươ ươ ừ
6/27/14
7
Automata và ngôn ng hình th c - ©copyright by PhD. C.T.Ha, Le Quy Don Technical ữ ứ
University
6.1.1. PDA và các khái ni m liên quanệ

Ví d 6.5: ụ v ki m tra cân b ng ề ể ằ
c a chu i đóng m ngo c s d ng ủ ỗ ở ặ ử ụ
stack:
while (input symbol is “[”) {
<push “[” onto the stack>;
while (input symbol is “]”) &&
(top of stack is “[”)
<pop>;
}
if (all of input read) && (top of stack
is “ ”)
<accept>.

Xét chu i nh p vào “[ [ ] [ ] ]”:ỗ ậ
Образец текста
Второй уровень
Третий уровень
Четвертый уровень
Пятый уровень

vào và đ nh stack, PDA s l a ch n tr ng thái k ti p và m t chu i ký hi u ỉ ẽ ự ọ ạ ế ế ộ ỗ ệ
thay th trên stack, đ u đ c d ch sang ph i 1 ký hi u;ế ầ ọ ị ả ệ

D ng 2ạ : không ph thu c vào ký hi u nh p (d ch chuy n ε). Đ u đ c đ ng ụ ộ ệ ậ ị ể ầ ọ ứ
im. Ngăn x p bi n đ i.ế ế ổ

Có 2 cách đ nh nghĩa ị ngôn ng ch p nh n b i PDA:ữ ấ ậ ở

Ngôn ng ch p nh n b i stack r ngữ ấ ậ ở ỗ : G m các chu i nh p mà sau b c ồ ỗ ậ ướ
chuy n cu i cùng stack tr v tr ng thái r ng;ể ố ở ề ạ ỗ

Ngôn ng ch p nh n b i tr ng thái k t thúc: ữ ấ ậ ở ạ ế G m các chu i nh p mà sau ồ ỗ ậ
b c chuy n cu i cùng r i vào m t trong các tr ng thái k t thúc;ướ ể ố ơ ộ ạ ế
6/27/14
10
Automata và ngôn ng hình th c - ©copyright by PhD. C.T.Ha, Le Quy Don Technical ữ ứ
University
6.1.1. PDA và các khái ni m liên quanệ
6/27/14
11
Automata và ngôn ng hình th c - ©copyright by PhD. C.T.Ha, Le Quy Don Technical ữ ứ
University

Mô hình máy PDA:
6.1.1. PDA và các khái ni m liên quanệ

Ví d 6.6: ụ xét L = {wcwR | w ∈ (0 + 1)*} đ c sinh ra t CFG:ượ ừ
S 0S0 | 1S1 | c→
Ta xây d ng PDA nh sau:ự ư


Thao tác trên automata v i chu i 1011c1101 ??? ớ ỗ
6.1.1. PDA và các khái ni m liên quanệ
●
ĐN 6.1: m t PDA A là m t h th ng 7 thành ph n:ộ ộ ệ ố ầ
A (Q, Σ, Γ, δ, q0, Z0, F)

Q : t p h u h n các tr ng thái;ậ ữ ạ ạ

Σ : b ch cái nh p (ộ ữ ậ tape or input alphabet);

Γ : b ch cái stack (ộ ữ stack alphabet);

δ : hàm chuy n Q x (Σ ể ∪ {ε}) x Γ t p con c a Q x Γ*;→ ậ ủ

q0 : tr ng thái kh i đ u;ạ ở ầ

Z0 : ký hi u b t đ u trên stack;ệ ắ ầ

F ⊆ Q : t p các tr ng thái k t thúc (n u PDA ch p nh n chu i b ng ậ ạ ế ế ấ ậ ỗ ằ
Stack r ng thì F = Ø).ỗ
6/27/14
14
Automata và ngôn ng hình th c - ©copyright by PhD. C.T.Ha, Le Quy Don Technical ữ ứ
University
6.1.1. PDA và các khái ni m liên quanệ
●
ĐN 6.2: Hàm chuy n ể δ ph thu c ký hi u nh pụ ộ ệ ậ :
δ(q, a, z) = { (p1, γ1), (p2, γ2), , (pm, γm) },
6/27/14
15

16
Automata và ngôn ng hình th c - ©copyright by PhD. C.T.Ha, Le Quy Don Technical ữ ứ
University
trong đó:

tr ng thái hi n th i là q;ạ ệ ờ

ký hi u trên đ nh hi n th i c a ệ ỉ ệ ờ ủ
stack là z;

tr ng thái chuy n t i là pi , 1 ạ ể ớ ≤ i ≤
m;

Thay th z b ng γi trên đ nh stack;ế ằ ỉ

Không có ký hi u đ c vào, không ệ ọ
d ch chuy n đ u đ c.ị ể ầ ọ
q
p1
p2
pm
ε, z γ1→
ε, z γ2→
ε, z γm→
6.1.1. PDA và các khái ni m liên quanệ
●
Ví d 6.6: ụ PDA ch p nh n wcwR b ng Stack r ngấ ậ ằ ỗ
1) δ(q1, 0, R) = {(q1, BR)} 7) δ(q1, c, R) = {(q2, R)}
2) δ(q1, 1, R) = {(q1, YR)} 8) δ(q1, c, B) = {(q2, B)}
3) δ(q1, 0, B) = {(q1, BB)} 9) δ(q1, c, Y) = {(q2, Y)}

6.1. Khái ni m v Pushdown Automata (PDA)ệ ề
6.1.1. PDA và các khái ni m liên quanệ
6.1.2. PDA không đ n đ nh (NPDA)ơ ị
6.1.3. PDA đ n đ nh (DPDA)ơ ị
6.2. S t ng đ ng gi a 2 d ng PDAự ươ ươ ữ ạ
6.2.1. Bi n đ i t ng đ ng t d ng 2 sang d ng 1ế ổ ươ ươ ừ ạ ạ
6.2.2. Bi n đ i t ng đ ng t d ng 1 sang d ng 2ế ổ ươ ươ ừ ạ ạ
6.3. S t ng đ ng gi a PDA và CFGự ươ ươ ữ
6.3.1. Bi n đ i t ng đ ng t CFG sang PDAế ổ ươ ươ ừ
6.3.2. Bi n đ i t ng đ ng t PDA sang CFGế ổ ươ ươ ừ
6/27/14
19
Automata và ngôn ng hình th c - ©copyright by PhD. C.T.Ha, Le Quy Don Technical ữ ứ
University
6.1.2. PDA không đ n đ nh (NPDA)ơ ị

Ví d 6.7:ụ thi t k PDA ch p nh n ngông ng trong vd ế ế ấ ậ ữ
6.3:
{wwR | w ∈ (0 + 1)*} b ng Stack r ngằ ỗ

Nh n xét: ậ do không có ký hi u c đ bi t th i đi m chuy n ệ ể ế ờ ể ể
t tr ng thái q1 sang q2, d n đ n b t bu c ph i đoán th ừ ạ ẫ ế ắ ộ ả ử
(khi th y 2 ký hi u liên ti p gi ng nhau)ấ ệ ế ố

N u ký hi u thu c chu i xuôi: gi nguyên tr ng thái q1 ế ệ ộ ỗ ữ ạ
và push vào stack;

N u ký hi u thu c chu i ng c: chuy n sang tr ng thái ế ệ ộ ỗ ượ ể ạ
q2 và pop kh i Stackỏ
6/27/14

↓
(q1, 0, BYYBBR) → (q2, ε, YYBBR) : reject!
↓
(q1, ε, BBYYBBR): reject!
6/27/14
22
Automata và ngôn ng hình th c - ©copyright by PhD. C.T.Ha, Le Quy Don Technical ữ ứ
University
6.1.2. PDA không đ n đ nh (NPDA)ơ ị
6/27/14
23

NPDA đoán nh n ngôn ng {wwR | w ậ ữ ∈ (0 + 1)*} :
q0
q1 q2
Start
ε, ε  ε
0, ε  0
1, ε  1
0,0 ε
1,1  ε
ε, $  ε
Automata và ngôn ng hình th c - ©copyright by PhD. C.T.Ha, Le Quy Don Technical ữ ứ
University
q1
q2
0, B  ε
1, Y  ε
0, R  BR
1, R  YR

m t ph n t .ộ ầ ử

Chú ý: đ i v i PDA thì d ng đ n đ nh và không đ n đ nh là ố ớ ạ ơ ị ơ ị không
t ng đ ng nhauươ ươ .

Ví d 6.7ụ : wwR đ c ch p nh n b i PDA không đ n đ nh, nh ng ượ ấ ậ ở ơ ị ư
không đ c ch p nh n b i b t kỳ m t PDA đ n đ nh nào.ượ ấ ậ ở ấ ộ ơ ị
6/27/14
25
Automata và ngôn ng hình th c - ©copyright by PhD. C.T.Ha, Le Quy Don Technical ữ ứ
University