Automata đẩy xuống (Push Down Automata): Bài giảng Tin học lý thuyết

Chương 6:

Automata đẩy xuống (Push Down Automata)

Nội dung:

• Khái niệm về PDA

• PDA đơn định và không đơn định

• PDA chấp nhận chuỗi bằng Stack rỗng và PDA chấp

nhận chuỗi bằng trạng thái kết thúc

• Sự tương đương giữa PDA và CFL

PDA

Ta đã biết:

• Lớp ngôn ngữ chính quy được sinh ra từ văn phạm chính quy và được đoán nhận bởi automata hữu hạn • Lớp ngôn ngữ phi ngữ cảnh được sinh ra từ văn phạm phi ngữ cảnh → câu hỏi: CFL có thể được đoán nhận bởi một automata không? automata đó như thế nào?

Mô tả: gồm các thành phần của một automata hữu hạn với sự bổ

sung thêm một ngăn xếp làm việc (Stack)

0 1 1 0 0 1 0 1

Bộ điều khiển

Y B R

PDA

Ví dụ: xét L = {wcwR | w (cid:0)

(0 + 1)*} được sinh ra từ CFG S → 0S0 | 1S1 | c

Ta xây dựng PDA như sau:

• Bộ điều khiển có 2 trạng thái q1 và q2 • Stack có 3 ký hiệu: xanh (B), vàng (Y) và đỏ (R) • Quy tắc thao tác trên automata:

PDA

Các khái niệm:

✔ Phụ thuộc ký hiệu nhập: 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 lựa chọn trạng thái kế tiếp, thay thế ký hiệu trên Stack và di chuyển đầu đọc trên băng nhập. ✔ Không phụ thuộc ký hiệu nhập (ε – dịch chuyển): ký hiệu nhập không được dùng, đầu đọc không di chuyển.

• Phân loại PDA: đơn định (DPDA) và không đơn định (NPDA) • Phép chuyển: có 2 kiểu

✔ Bởi Stack rỗng ✔ Bởi trạng thái kết thúc

• Ngôn ngữ được chấp nhận bởi PDA

Một ngôn ngữ được chấp nhận bởi PDA khi và chỉ khi nó là một ngôn ngữ phi ngữ cảnh.

PDA

Định nghĩa: một PDA M là một hệ thống 7 thành phần

M (Q, Σ, Γ, δ, q0, Z0, F)

{ε}) x Γ → tập con của Q x Γ*

Q : tập các trạng thái kết thúc (nếu PDA chấp nhận

• Q : tập hữu hạn các trạng thái • Σ : bộ chữ cái nhập • Γ : bộ chữ cái Stack • δ : hàm chuyển Q x (Σ (cid:0) • q0 : trạng thái khởi đầu • Z0 : ký hiệu bắt đầu trên Stack • F (cid:0) chuỗi bằng Stack rỗng thì F = Ø)

PDA

Hàm chuyển δ:

• Hàm chuyển phụ thuộc ký hiệu nhập

δ(q, a, Z) = { (p1, γ1), (p2, γ2), ..., (pm, γm) }

• Hàm chuyển không phụ thuộc ký hiệu nhập

δ(q, ε, Z) = { (p1, γ1), (p2, γ2), ..., (pm, γm) }

Ví dụ: PDA chấp nhận wcwR bằng Stack rỗng

6) 1) δ(q1, 0, R) = {(q1, BR)} δ(q1, 1, R) = {(q1, YR)} 2) δ(q1, 0, B) = {(q1, BB)} δ(q1, 1, B) = {(q1, YB)} δ(q1, 0, Y) = {(q1, BY)} δ(q1, 1, Y) = {(q1, YY)} 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, ε)}

PDA

Hình thái (ID): dùng để ghi nhớ trạng thái và nội dung của Stack (q, aw, Zα) ⊢M (p, w, βα) nếu δ(q, a, Z) chứa (p, β)

Ngôn ngữ chấp nhận bởi PDA:

• Ngôn ngữ được chấp nhận bằng trạng thái kết thúc F và γ (cid:0) Γ*}

L (M) = {w | (q0, w, Z0) ⊢* (p, ε, γ) với p (cid:0) • Ngôn ngữ được chấp nhận bởi Stack rỗng

Q} N (M) = {w | (q0, w, Z0) ⊢* (p, ε, ε) với p (cid:0)

Ví dụ: PDA chấp nhận wcwR bằng Stack rỗng với chuỗi nhập 001c100

⊢

⊢ (q1, 1c100, BBR) ⊢ ⊢ (q2, 00, BBR)

(q1, 001c100, R) ⊢ (q1, 01c100, BR) ⊢ (q2, 100, YBBR) (q1, c100, YBBR) (q2, 0, BR) ⊢ (q2, ε, R) ⊢ (q2, ε, ε) : Chấp nhận

PDA không đơn định (NPDA)

Ví dụ: thiết kế PDA chấp nhận {wwR | w (cid:0)

✔ 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

• M({q1, q2}, {0, 1}, {R, B, Y}, δ, q1, R, Ø):

(0 + 1)*} bằng Stack rỗng • Không có ký hiệu c để biết thời điểm chuyển từ trạng thái q1 sang q2 • Bắt buộc phải đoán thử (khi thấy 2 ký hiệu liên tiếp giống nhau)

, 1, Y) = {(q 1

, ε)} , YY),(q 2 1

2) 3)

, BB), (q 1

2

4) 5)

δ(q1, 0, R) = {(q1, BR)} 6) δ(q δ(q1, 1, R) = {(q1,YR)} δ(q , 0, B) = {(q 1 δ(q1, 0, Y) = {(q1, BY)} δ(q1, 1, B) = {(q1, YB)}

7) δ(q2, 0, B) = {(q2, ε)} , ε)} 8) δ(q2, 1, Y) = {(q2, ε)} 9) δ(q1, ε, R) = {(q2, ε)} 10) δ(q2, ε, R) = {(q2, ε)}

PDA không đơn định (NPDA)

Ví dụ: các phép chuyển hình thái của PDA chấp nhận chuỗi 001100

(0 + 1)*} bằng Stack rỗng

, 001100, R)

ấ

, 01100, BR) (cid:0)

, 1100, R) (cid:0)

, 1100, (cid:0) ) : Không ch p nh n ậ

, 1100, BBR)

, 00, BBR)

thuộc ngôn ngữ {wwR | w (cid:0) ở ầ Kh i đ u

ấ

, 0, BR) (cid:0)

, (cid:0) , R) (cid:0)

, (cid:0) , (cid:0) ) : Ch p nh n ậ

ấ

, 0, BYYBBR) (cid:0)

, (cid:0) , YYBBR) : Không ch p nh n ậ

ấ

(cid:0) (q (cid:0) (q (cid:0) (q (cid:0) , 100, YBBR) (cid:0) (q (q (cid:0) (cid:0) (q , 00, YYBBR) (q (cid:0) (q (cid:0) (q

, (cid:0) , BBYYBBR) : Không ch p nh n ậ

PDA đơn định (DPDA)

Định nghĩa: một PDA M(Q, Σ, Γ, δ, q0, Z0, F) được gọi là đơn định

Γ: nếu δ(q, ε, Z) ≠ Ø thì δ(q, a, Z) = Ø với (cid:0) a (cid:0) Q và Z (cid:0)

Q, Z (cid:0) Γ và a (cid:0) (Σ (cid:0) {ε}) mà δ(q, a, Z) chứa

nếu: • (cid:0) q (cid:0) Σ • Không có q (cid:0) nhiều hơn 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ụ: 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.

Tương đương giữa PDA với Stack rỗng và PDA với trạng thái kết thúc

Định lý 6.1: Nếu một ngôn ngữ phi ngữ cảnh L được chấp nhận bởi một PDA chấp nhận chuỗi bởi trạng thái kết thúc M2 thì L cũng được chấp nhận bởi một PDA chấp nhận chuỗi bởi Stack rỗng M1

Cách xây dựng:

{qe, q0'}, Σ, Γ, δ', q0', X0, Ø)

(Σ (cid:0) {ε})

(Γ (cid:0) {X0})

F và Z (cid:0) (Γ (cid:0) Đặt M2(Q, Σ, Γ, δ, q0, Z0, F) và M1(Q (cid:0) • δ'(q0', ε, X0) = {(q0, Z0X0)} • δ'(q, a, Z) chứa mọi phần tử của δ(q, a, Z) với a (cid:0) • δ'(q, ε, Z) chứa (qe, ε) với (cid:0) q (cid:0) • δ'(qe, ε, Z) chứa (qe, ε) với (cid:0) Z (cid:0) {X0})

Tương đương giữa PDA với Stack rỗng và PDA với trạng thái kết thúc

Định lý 6.2: Nếu một ngôn ngữ phi ngữ cảnh L được chấp nhận bởi một PDA chấp nhận chuỗi bởi Stack rỗng M1 thì L cũng được chấp nhận bởi một PDA chấp nhận chuỗi bởi trạng thái kết thúc M2

Cách xây dựng:

{q0', qf}, Σ, Γ (cid:0) {X0}, δ', q0', X0, {qf})

(Σ (cid:0) {ε})

Q Đặt M1(Q, Σ, Γ, δ, q0, Z0, F) và M2(Q (cid:0) • δ'(q0', ε, X0) = {(q0, Z0X0)} • δ'(q, a, Z) = δ(q, a, Z) với a (cid:0) • δ'(q, ε, X0) chứa (qf, ε) với (cid:0) q (cid:0)

Tương đương giữa PDA và CFL

Định lý 6.3: Nếu L là một ngôn ngữ phi ngữ cảnh thì tồn tại PDA

chấp nhận chuỗi với Stack rỗng M sao cho L = N(M)

Cách xây dựng:

Đặt G(V, T, P, S) thỏa dạng chuẩn Greibach và L(G) không chứa ε Đặt M({q}, T, V, δ, q, S, Ø) là PDA chấp nhận L với Stack rỗng

• δ'(q, a, A) = (q, γ) khi và chỉ khi A → aγ

Ví dụ: S → aAA ; A → aS | bS | a

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, S)}

Tương đương giữa PDA và CFL

Định lý 6.4: Nếu L được chấp nhận bởi một PDA chấp nhận chuỗi

bởi Stack rỗng thì L là ngôn ngữ phi ngữ cảnh

Cách xây dựng:

Đặt PDA M(Q, Σ, Γ, δ, q0, Z0, Ø) chấp nhận L với Stack rỗng Đặt G(V, T, P, S) là CFG, trong đó:

• V là tập các đối tượng dạng [q, A, p] • S là ký hiệu bắt đầu mới được thêm vào • P là tập các luật sinh dạng 1. S → [q0, Z0, q] với (cid:0) q (cid:0) 2. [q, A, qm+1] → a [q1, B1, q2][q2, B2, q3]...[qm, Bm, qm+1]

sao cho δ(q, a, A) có chứa (q1, B1B2...Bm) Nếu m = 0 thì luật sinh có dạng [q, A, q1] → a

Tương đương giữa PDA và CFL

Ví dụ: xây dựng CFG tương đương sinh ra ngôn ngữ được chấp nhận bởi PDA M({q0, q1}, {0, 1}, {Z0, X}, δ, q0, Z0, Ø) với δ 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, ε)}

Xây dựng: CFG G(V, {0, 1}, P, S) 1. Tập các biến V = [q, A, p] (cid:0) S

= { 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] }

2. Tập các luật sinh P

S → [q0, Z0, q0] | [q0, Z0, q1]

δ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]

Tương đương giữa PDA và CFL

δ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] δ5) [q1, X, q1] → ε δ6) [q1, Z0, q1] → ε δ3) [q0, X, q1] → 1 δ4) [q1, X, q1] → 1

Đặt: [q0, X, q0] = A, [q0, X, q1] = B, ..., [q0, Z0, q0] = E, ..., [q1, Z0, q1] = H

S → 0B B → 0B | 0B1 | 1

Giản lược văn phạm: S → F F → 0BH B → 0BD | 1 D → ε | 1 H → ε