α, β,.. Xâu ký hiệu ngăn xếp
2/11/2014 Lý thuyết ngôn ngữ - Chương V Trang 8/20
Kiểu thứnhấtphụthuộc vào ký hiệu nhập, tức là với một trạng thái, một ký hiệu tạiđỉnh Stack và một ký hiệu nhập;
PDA sẽlựa chọn trạng thái kếtiếp và một chuỗi các ký hiệu thay thếtrên Stack,đầuđọc dịchđi sang phải một ký hiệu.
Kiểu thứhaikhông phụthuộc vào ký hiệu nhập, gọi làε- dịch chuyển : tương tựnhưkiểu thứnhất, chỉngoại trừlà ký hiệu nhập khôngđược dùng vàđầuđọc không dịch chuyển sau khi chuyển trạng thái. Thực chất, bước chuyểnđặc biệt này là một sựtạm ngừng quan sát trên băng nhậpđểsắp xếp lại các ký hiệu trong ngăn xếp.
Phép chuyển sẽ có hai kiểu:
2/11/2014 Lý thuyết ngôn ngữ - Chương V Trang 9/20
Initial Stack Symbol Stack
$
Stack
z bottom special symbol stack
head top
Appears at time 0
2/11/2014 Lý thuyết ngôn ngữ - Chương V Trang 10/20
The States
q 1 a, b → c q 2 Input
symbol Pop symbol
Push symbol
2/11/2014 Lý thuyết ngôn ngữ - Chương V Trang 11/20
Hàm chuyển của PDA
Hàm chuyển phụthuộc ký hiệu nhập
δ(q, a, Z) = {(p1,γ1), (p2,γ2), ..., (pm,γm)} nghĩa là PDA đangởtrạng thái q với ký hiệu nhập a và ký hiệu Zở đỉnh stack thì nó chuyểnđến trạng thái pinàođó, thay kí tự ở stack Z bằngγivà dịch chuyểnđầuđọcđi một ký hiệu.
Với xâu γtrong ngăn xếp ta quiước ký hiệu bên trái nhất củaγnằmở đỉnh và ký hiệu bên phải nhất nằmở đáy ngăn xếp.
2/11/2014 Lý thuyết ngôn ngữ - Chương V Trang 12/20
Hàm chuyển không phụthuộc ký hiệu nhập
δ(q,ε, Z) = {(p1,γ1), (p2,γ2), ..., (pm,γm)}
nghĩa là PDAđangởtrạng thái q với ký hiệu nhậpεvà ký hiệu Zở đỉnh stack thì nó chuyểnđến trạng thái pinàođó, thay kí tự ởstack Z bằngγi
Trong trường hợp nàyđầuđọc không dịch chuyển.
2/11/2014 Lý thuyết ngôn ngữ - Chương V Trang 13/20
Hình thái (ID : Instantaneous Descriptions)
Đểdễmô tảhoạtđộng của PDA, ta xét khái niệm hình thái.
Hình thái dùngđểlưu giữtrạng thái của PDA
ID là một bộba (q, w,γ), trongđó q là trạng thái, w là chuỗi nhập vàγlà chuỗi các ký hiệu Stack.
Nếu M (Q,Σ,Γ,δ, q0, Z0, F) là một PDA, ta nói :
(q, aw, Zα) ⊢(p, w,βα) nếu δ(q, a, Z) chứa (p,β)
Lưu ý: a có thểlà một ký hiệu trong input hoặcε
2/11/2014 Lý thuyết ngôn ngữ - Chương V Trang 14/20
The States
q 1 a, b → c q 2 Input
symbol
Pop symbol
Push symbol
2/11/2014 Lý thuyết ngôn ngữ - Chương V Trang 15/20
Ngôn ngữ chấp nhận bởi PDA
Với PDA M (Q,Σ,Γ,δ, q0, Z0, F), tađịnh nghĩa : a. Ngôn ngữ được chấp nhận bởi trạng thái kết thúc là:
L (M) = {w|(q0, w, Z0)⊢* (p,ε,γ) với p∈F vàγ ∈ Γ*}
b. Ngôn ngữ được chấp nhận bởi Stack rỗng là:
N(M) = {w|(q0, w, Z0)⊢* (p,ε,ε) với p∈Q}.
Khi có sựchấp nhận bằng Stack rỗng thì tập trạng thái kết thúc là không còn cần thiết vì vậy ta ký hiệu tập trạng thái kết thúc F là∅.
2/11/2014 Lý thuyết ngôn ngữ - Chương V Trang 16/20
Ví dụ: PDA đơn định (DPDA)
Cho PDA được chấp nhận bởi stack rỗng như sau:
M ({q1, q2}, {0, 1, c}, {R, B, Y}, δ, q1, R, ∅)
7) δ(q1, c, R) = {(q2, R)}
8) δ(q1, c, B) = {(q2, B)}
9) δ(q1, c, Y) = {(q2, Y)}
10) δ(q2, 0, B) = {(q2, ε)}
11) δ(q2, 1, Y) = {(q2, ε)}
12) δ(q2, ε, R) = {(q2, ε)}
1) δ(q1, 0, R) = {(q1, BR)}
2) δ(q1, 1, R) = {(q1, YR)}
3) δ(q1, 0, B) = {(q1, BB)}
4) δ(q1, 1, B) = {(q1, YB)}
5) δ(q1, 0, Y) = {(q1, BY)}
6) δ(q1, 1, Y) = {(q1, YY)}
2/11/2014 Lý thuyết ngôn ngữ - Chương V Trang 17/20
Các phép chuyển hình thái của PDA chấp nhận chuỗi 001c100 thuộc ngôn ngữ {wcwR|w ∈(0+1)*} bằng Stack rỗng như sau :
(q1, 001c100, R) ⊢(q1, 01c100, BR) ⊢(q1, 1c100, BBR) ⊢(q1, c100, YBBR) ⊢(q2, 100, YBBR) ⊢(q2, 00, BBR) ⊢(q2, 0, BR)
⊢(q2, ε, R) ⊢(q2, ε, ε) : Chấp nhận
2/11/2014 Lý thuyết ngôn ngữ - Chương V Trang 18/20
2/11/2014 Lý thuyết ngôn ngữ - Chương V Trang 19/20 N PDA không đơn định chấp nhận ngôn ngữ {wwR|w ∈(0+1)*} bằng
Stack rỗng
2/11/2014 Lý thuyết ngôn ngữ - Chương V Trang 20/20
Các phép chuyển hình thái của NPDA chấp nhận chuỗi 001100 thuộc ngôn ngữ {wwR|w ∈(0+1)*} bằng Stack rỗng như sau :
2/11/2014 Lý thuyết ngôn ngữ - Chương V Trang 21/20
2/11/2014 Lý thuyết ngôn ngữ - Chương V Trang 22/20
II. PDA VÀ VĂN PHẠM PHI NGỮ CẢNH
Định lý:
Đối với mọi ngôn ngữ phi ngữ cảnh L thì tồn tại một otomat đẩy xuống không đơn định M đoán nhận L.
Chứng minh
Xây dựng NPDA M (Q, Σ, Γ, δ, p, S, q) tương đương với CFG = (Σ, ∆, P, S)
Q = {p, q}
Σgiống với CFG
Γ= Σ ∪∆
p là trạng thái khởi đầu
S là ký hiệu khởi đầu của stack
q là trạng thái kết thúc.
2/11/2014 Lý thuyết ngôn ngữ - Chương V Trang 23/20
Hàm chuyển δcủa M được định nghĩa như sau:
δ(p, ε, S) = (q, S)
δ(q, a, a) =(q, ε) với mọi a thuộc Σ
δ(q, ε, A) =(q,x) với mỗi luật sinh A →x trong tập luật sinh của G
Nghĩa là PDA sẽ hoạt động như sau:
Khởi đầu bằng thao tác đưa S vào stack và chuyển từ trạng thái p sang q
Tiếp theo:
Nếu ở đỉnh stack là một ký hiệu chưa kết thúc A thì thay nó bằng vế phải của luật sinh A →x
Nếu ở đỉnh stack là một ký hiệu kết thúc a và ký hiệu vào cũng là a thì xóa a khỏi stack
2/11/2014 Lý thuyết ngôn ngữ - Chương V Trang 24/20
Ví dụ
Xét CFG G({a,b,c},S,S,P) với
p = {S →aSa, S →bSb, S →c }
Xây dựng PDA đoán nhận CFG nói trên Giải
M (Q, ΣΣΣ, ΓΣΓΓ, δΓδδδ, q0, Z0, F)
với Q = {p,q} {tập trạng thái}
Σ= {a,b,c} {Bảng chữ cái của xâu nhập)
Γ= {a,b,c,S} {Bảng chữ cái của stack}
q0 = p {trạng thái khởi đầu của PDA}
Z0 = S {trạng thái khởi đầu của stack}
F = q {trạng thái kết thúc PDA}