Giáo trình Tin học lý thuyết - Chương 6: Ôtômát đẩy xuống

 nó, thì M2 khi chuyển tương tự như M1 sẽ xóa toàn bộ Stack của nó trừ ký 
hiệu X0 nằm dưới đáy Stack. Quy tắc 3 làm cho M2 sau đó khi gặp X0 xuất hiện thì đi 
vào trạng thái kết thúc và chấp nhận input x. 
Chứng minh L(M2) = N(M1) cũng tương tự như định lý 6.1 
2.2. Tương đương giữa PDA và CFL 
ĐỊNH LÝ 6.3: Nếu L là ngôn ngữ phi ngữ cảnh thì tồn tại PDA M sao cho L = 
N(M). 
Chứng minh 
Giả sử ε không thuộc L(G) (có thể sửa đổi lý luận cho trường hợp ngôn ngữ L(G) có 
chứa ε). Đặt G (V, T, P, S) là văn phạm phi ngữ cảnh có dạng chuẩn Greibach sinh ra 
L. Đặt M ({q}, T, V, δ, q, S, ∅), trong đó δ(q, a, A) chứa (q, γ) khi và chỉ khi A → aγ 
là một luật sinh trong P. 
PDA M mô phỏng chuỗi dẫn xuất trái của G. Vì G là dạng chuẩn Greibach nên mỗi 
dạng câu trong dẫn xuất trái gồm một chuỗi các ký hiệu kết thúc x sau đó là một 
chuỗi các biến α. M lưu trữ phần hậu tố α của dạng câu bên trái trên Stack của nó sau 
khi xử lý phần tiền tố x. 
Chương VI : Ôtômát đẩy xuống 
 104
Một cách hình thức ta chỉ ra rằng : 
S ⇒* xα bằng dẫn xuất trái khi và chỉ khi (q, x, S) ⊢*M (q, ε, α) (1) 
Trước tiên, chúng ta giả sử (q, x, S) ⊢i (q, ε, α) và sẽ chỉ ra bằng quy nạp theo số lần 
i rằng S ⇒* xα. 
Với i = 0, điều đó hiển nhiên đúng vì x = ε và α = S. 
Giả sử i ≥ 1 và đặt x = ya. 
Xét bước chuyển hình thái trước bước cuối : 
(q, ya, S) ⊢i -1 (q, a, β) ⊢ (q, ε, α) (2) 
Nếu loại bỏ ký hiệu a ở cuối chuỗi input trong hình thái đầu tiên của (2), ta có: 
(q, y, S) ⊢i -1 (q, ε, β) (vì a không ảnh hưởng đến các phép chuyển của M). 
Theo giả thiết quy nạp S ⇒* yβ. Phép chuyển (q, a, β) ⊢ (q, ε, α) sẽ suy ra β = 
Aγ, với A ∈ V và A → aη là một luật sinh trong G và α = ηγ. 
Vậy S ⇒* yβ ⇒ yaηγ = xα 
Ta đã chứng minh xong "nếu" của giả thiết (1) 
Ngược lại, ta giả sử S ⇒i xα bằng dẫn xuất trái. Ta sẽ chứng minh quy nạp theo số 
bước dẫn xuất i rằng: (q, x, S) ⊢* (q, ε, α) 
Với i = 0: phép chuyển hiển nhiên đúng 
Xét i ≥ 1 và giả sử S ⇒i -1 yAγ ⇒ yaηγ, trong đó x = ya và α = ηγ. Theo giả 
thiết quy nạp : (q, y, S) ⊢* (q, ε, Aγ). Vậy (q, ya, S) ⊢* (q, a, Aγ) 
Vì A → aη là một luật sinh nên δ(q, a, A) chứa (q, η). Vậy : 
(q, x, S) ⊢* (q, a, Aγ) ⊢* (q, ε, α) 
Hay phần "chỉ nếu" của giả thiết (1) cũng đã được chứng minh xong. 
Để kết thúc việc chứng minh, ta chú ý rằng giả thiết (1) với α = ε thì S ⇒* x nếu và 
chỉ nếu (q, x, S) ⊢* (q, ε, ε). Tức là x ∈ L(G) khi và chỉ khi x ∈ N(M). 
Thí dụ 6.3 : Xây dựng NPDA chấp nhận ngôn ngữ sinh bởi CFG G có các luật sinh 
như sau : 
S → aAA 
A → aS | bS | a 
 Ta có : CFG G ( {S, A}, {a, b}, P, S ) 
 NPDA tương đương M ({q}, {a, b}, {S, A}, δ, q, S, ∅) với δ như sau : 
 1) δ (q, a, S) = {(q, AA)} 
 2) δ (q, a, A) = {(q, S), (q, ε)} 
 3) δ (q, b, A) = {(q, ε)} 
ĐỊNH LÝ 6.4 : Nếu L là N(M) với PDA M thì L và ngôn ngữ phi ngữ cảnh. 
Chứng minh 
Gọi PDA M (Q, Σ, Γ, δ, q0, Z0, ∅). Đặt G (V, Σ, P, S) là CFG, trong đó : 
Chương VI : Ôtômát đẩy xuống 
 105
. V là tập các đối tượng dạng [q, A, p] với p, q ∈ Q; A ∈ Γ 
. S là ký hiệu chưa kết thúc mới thêm vào. 
. P là tập các luật sinh có dạng : 
 1) S → [q0, Z0, q] ,∀q ∈ Q. 
 2) [q, A, q m+1] → a[q1, B1, q2][q2, B2, q3] ... [qm, Bm, qm+1] 
 ∀q, q1, q2, ..., qm+1 ∈ Q, a ∈ Σ ∪ {ε} và A, B1, B2, ..., Bm ∈ Γ 
 sao cho δ(q, a, A) có chứa (q1, B1BB2 .. Bm). 
 Nếu m = 0 thì luật sinh có dạng [q, A, q1] → a. 
 Để nắm được chứng minh, cần phải lưu ý rằng các biến và luật sinh trong G được xác 
định sao cho dẫn xuất trái trong G của x mô phỏng PDA khi cho x nhập vào. Cụ thể 
hơn, các biến xuất hiện tại một bước bất kỳ trong G tương đương với các ký hiệu trên 
Stack của M. Nói cách khác [q, A, p] dẫn ra x nếu và chỉ nếu x là nguyên nhân làm M 
xoá rỗng Stack của nó bằng chuỗi các phép chuyển từ trạng thái q đến trạng thái p. 
 Để chứng minh L(G) = N(M), ta quy nạp theo số bước dẫn xuất của G hoặc số bước 
chuyển trạng thái của M rằng [q, A, p] ⇒*G x nếu và chỉ nếu (q, x, A) ⊢*M (p, ε, ε) 
Thí dụ 6.4 : Xây dựng CFG G tương đương sinh ra ngôn ngữ được chấp nhận bởi 
PDA sau : 
 M ( {q0, q1}, {0, 1}, {Z0, X}, δ, q0, Z0, ∅ ) 
với δ được cho như sau : 
1) δ (q0, 0, Z0) = {(q0, XZ0)} 
2) δ (q0, 0, X) = {(q0, XX)} 
3) δ (q0, 1, X) = {(q1, ε)} 
4) δ (q1, 1, X) = {(q1, ε)} 
5) δ (q1, ε, X) = {(q1, ε)} 
6) δ (q1, ε, Z0) = {(q1, ε)} 
Ta xây dựng CFG G (V, {0, 1}, P, S) sinh ra N(M) với các thành phần như sau : 
V = { S, [q0, X, q0], [q0, X, q1], [q1, X, q0], [q1, X, q1], 
 [q0, Z0, q0], [q0, Z0, q1], [q1, Z0, q0], [q1, Z0, q1] } 
Tập luật sinh P chứa các luật sinh có dạng : 
Các luật sinh cho ký hiệu bắt đầu S : S → [q0, Z0, q0] | [q0, Z0, q1] 
Các luật sinh cho các biến khác trong V được xây dựng từ các hàm chuyển của 
PDA như sau : 
δ1) [q0, Z0, q0] → 0 [q0, X, q0][q0, Z0, q0] 
 | 0 [q0, X, q1][q1, Z0, q0] 
 [q0, Z0, q1] → 0 [q0, X, q0][q0, Z0, q1] 
 | 0 [q0, X, q1][q1, Z0, q1] 
δ2) [q0, X, q0] → 0 [q0, X, q0][q0, X, q0] 
 | 0 [q0, X, q1][q1, X, q0] 
[q0, X, q1] → 0 [q0, X, q0][q0, X, q1] 
 | 0 [q0, X, q1][q1, X, q1] 
δ3) [q0, X, q1] → 1 
δ4) [q1, Z0, q1] → ε 
Chương VI : Ôtômát đẩy xuống 
 106
δ5) [q1, X, q1] → ε 
δ6) [q1, X, q1] → 1 
Nhận xét rằng không có luật sinh nào cho các biến [q1, X, q0] và [q1, Z0, q0]. Vì tất cả 
các luật sinh cho biến [q0, X, q0] và [q0, Z0, q0] đều có chứa [q1, X, q0] hoặc [q0, Z0, 
q0] ở vế phải, nên sẽ không thể có chuỗi ký hiệu kết thúc nào có thể được dẫn ra từ 
các biến [q0, X, q0] hoặc [q0, Z0, q0]. Loại bỏ 4 biến này ra khỏi tập biến V và xóa các 
luật sinh có liên quan đến chúng trong tập P, ta thu được văn phạm có dạng như sau: 
 S → [q0, Z0, q1] 
 [q0, Z0, q1] → 0 [q0, X, q1][q1, Z0, q1] 
 [q0, X, q1] → 0 [q0, X, q1][q1, X, q1] 
 [q0, X, q1] → 1 
 [q1, Z0, q1] → ε 
 [q1, X, q1] → ε 
 [q1, X, q1] → 1 
Câu hỏi : 
Sinh viên hãy dùng các kiến thức đã học trong chương trước (ĐỊNH LÝ 5.2) 
để viết một văn phạm tương đương với văn phạm trên không có chứa các ký 
hiệu vô ích ? 
2.3. Quan hệ giữa CFL và tập hợp chính quy 
ĐỊNH LÝ 6.5 :Nếu L là CFL và R là tập chính quy thì L ∩ R là CFL. 
Chứng minh 
Đặt L là L(M) với PDA M (QM, Σ, Γ, δM, q0, Z0, FM) và đặt R là L(A) với DFA 
A (QA, ∑, δA, p0, FA). Ta xây dựng PDA M’ cho L ∩ R bằng cách cho M và A cùng 
“chạy song song”. Tức là với một ký hiệu nhập a thì M và A thực hiện các phép 
chuyển độc lập nhau. M’ chấp nhận input nếu cả M và A cùng chấp nhận. 
 Input của A, M và M’ 
Bộ điều 
khiển của 
A 
Bộ điều 
khiển của 
M 
Bộ điều 
khiển của 
M’ 
Satck của 
 M và M’ 
Chương VI : Ôtômát đẩy xuống 
 107
Hình 6.6 - Chạy một FA và PDA song song 
Một cách hình thức, đặt M’ (QA × QM, Σ, Γ, δ, [p0, q0], Z0, FA × FM), trong đó hàm 
chuyển δ được xác định như sau : 
δ ([p, q], a, X) chứa ([p’, q’], γ) ⇔ δA(p, a) = p’ và δM(q, a, X) chứa (q’, γ). 
Chú ý rằng a có thể bằng ε, khi đó p’ = p. 
Dễ dàng chứng minh quy nạp theo i rằng : ([p0, q0], w, Z0) ⊢iM ’ ([p, q], ε, γ) ⇔ (q0, 
w, Z0) ⊢iM (q, ε, γ) và δ(p0, w) = p (1) 
Với i = 0: thì (1) hiển nhiên đúng vì p = p0, q = q0, γ = Z0 và w = ε. 
Giả sử (1) đúng tới i - 1 (i > 0). 
Xét ([p0, q0], xa, Z0) ⊢i -1M ’ ([p’, q’], a, β) ⊢M ’ ([p, q], ε, γ) , trong đó w = xa 
và a là ε hoặc là một ký hiệu ∈ Σ. 
Theo giả thiết quy nạp, δA(p0, x) = p’ và (q0, x, Z0) ⊢i -1M (q’, ε, β). 
Theo định nghĩa của δ, thực tế ([p’, q’], a, β) ⊢M ‘ ([p, q], ε, γ) nên có thể suy 
ra δA(p’, a) = p và (q’, a, β) ⊢M (q, ε, γ). Vậy δA(p0, w) = p và (q0, w, Z0) ⊢*M (q, ε, γ). 
Tương tự, ta có thể chứng minh rằng : Nếu (q0, w, Z0) ⊢iM (q, ε, γ) và δA(p0, w) = p thì 
([p0, q0], w, Z0) ⊢*M ’ ([p, q], ε, γ) (xem phần này như bài tập). 
Tổng kết chương VI: Đến chương này, chúng ta đã có thể nắm bắt được một vài ý 
tưởng cơ bản liên quan đến các khái niệm về ngôn ngữ chính quy, ngôn ngữ phi ngữ 
cảnh, và mối quan hệ của chúng với các dạng ôtômát hữu hạn và đẩy xuống. Những 
khảo sát chứng tỏ ngôn ngữ chính quy thực sự là một tập hợp con của ngôn ngữ phi 
ngữ cảnh, và do đó, ôtômát đẩy xuống xét về một mặt nào đó có khả năng nhận dạng 
ngôn ngữ mạnh hơn rất nhiều so với ôtômát hữu hạn. Điều này gợi cho chúng ta một 
ý tưởng có thể mở rộng hơn nữa về khả năng đoán nhận ngôn ngữ của cơ chế ôtômát. 
Nếu so sánh ôtômát hữu hạn và ôtômát đẩy xuống, ta thấy rằng bản chất của sự khác 
Chương VI : Ôtômát đẩy xuống 
 108
biệt thể hiện ở bộ lưu trữ tạm thời dùng Stack. Nếu không có bộ lưu trữ, chúng ta có 
dạng ôtômát hữu hạn, nếu bộ lưu trữ là Stack, ta có dạng ôtômát đẩy xuống mạnh 
hơn. Từ suy luận này, chúng ta hoàn toàn có thể mong đợi để định nghĩa ngay cả 
những họ ngôn ngữ rộng lớn hơn nếu có thể cung cấp cho cơ chế ôtômát một bộ nhớ 
với khả năng lưu trữ linh hoạt hơn. Điều này dẫn đến khái niệm cơ bản về máy 
Turing sẽ được giới thiệu trong chương sau, một cơ chế ôtômát có tính máy móc hay 
tính giải thuật. 
BÀI TẬP CHƯƠNG VI 
6.1. Xây dựng PDA chấp nhận các ngôn ngữ : 
 a) {0m 1m 2n | m, n ≥ 1} 
 b) {ak bl cn dm | m = k + l + n} 
 c) {w | w ∈ {a, b}* và #a(w) = #b(w)} 
d) {w | w ∈ {a,b}* và #a(w) = 2#b(w)} 
6.2. Xây dựng PDA tương đương với văn phạm : 
a) S → + SS | *SS | a 
 b) S → aS | bS | aA 
A → bB| b 
B → aC 
C → b 
6.3. Xây dựng văn phạm CFG tương đương với các PDA sau : 
a) M ({q0, q1}, {0, 1}, {Z0, X}, δ, q0, Z0, ∅), trong đó δ được cho như sau: 
δ(q0, 1, Z0) = {(q0, XZ0)} 
δ(q0, 0, X) = {(q0, XX)} 
δ(q0, 1, X) = {(q1, ε)} 
δ(q1, 1, X) = {(q1, ε)} 
δ(q1, ε, X) = {(q1, ε)} 
δ(q1, ε, Z0) = {(q1, ε)} 
b) M ({q0, q1}, {0, 1}, {Z0, X}, δ, q0, Z0, ∅), trong đó δ được cho như sau: 
δ(q0, 1, Z0) = {(q0, XZ0)} 
δ(q0, 1, X) = {(q0, XX)} 
δ(q0, 0, X) = {(q1, X)} 
δ(q0, ε, Z0) = {(q0, ε)} 
δ(q1, 1, X) = {(q1, ε)} 
δ(q1, 0, Z0) = {(q0, Z0)} 
c) M ({q0, q1}, {a, b, c}, {Z0, X}, δ, q0, Z0, ∅), trong đó δ được cho như sau: 
δ(q0, a, Z0) = {(q0, X)} 
δ(q0, a, X) = {(q0, XX)} 
δ(q0, c, X) = {(q1, X)} 
Chương VI : Ôtômát đẩy xuống 
 109
δ(q0, b, Z0) = {(q0, X)} 
δ(q0, b, X) = {(q0, XX)} 
δ(q1, c, X) = {(q1, ε)}