PDA và văn phạm ngữ cảnh

Tương đương của việc chấp nhận chuỗi bởi trạng thái kết thúc và bởi Stack rỗng

ĐỊNH LÝ 6.1 : Nếu L là L(M 2 ) với PDA M 2 thì L là N(M 1 ) với PDA M 1 nào đó.

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, ∅ size 12{ emptyset } {}), 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.

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, ∅ size 12{ emptyset } {}) với δ như sau :

1) d (q, a, S) = {(q, AA)}

2) d (q, a, A) = {(q, S), (q, e)}

3) d (q, b, A) = {(q, e)}

ĐỊ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, Σ, Γ, δ, q₀, Z₀, ∅ size 12{ emptyset } {}). Đặt G (V, Σ, P, S) là CFG, trong đó :

. 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 ® [q₀, Z₀, q] ,∀q Î Q.

2) [q, A, q _m+1] ® a[q₁, B₁, q₂][q₂, B₂, q₃] ... [q_m, B_m, q_m+1]

∀q, q₁, q₂, ..., q_m+1 ∈ Q, a ∈ Σ  {ε} và A, B₁, B₂, ..., B_m ∈ Γ

sao cho δ(q, a, A) có chứa (q₁, B₁B₂ .. B_m).

Nếu m = 0 thì luật sinh có dạng [q, A, q₁] → 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 ( {q₀, q₁}, {0, 1}, {Z₀, X}, d, q₀­, Z₀, ∅ size 12{ emptyset } {} )

với d được cho như sau :

1) d (q₀, 0, Z₀) = {(q₀, XZ₀)}

2) d (q₀, 0, X) = {(q₀, XX)}

3) d (q₀, 1, X) = {(q₁, ε)}

4) d (q₁, 1, X) = {(q₁, ε)}

5) d (q₁, ε, x) = {(q₁, ε)}

6) d (q₁, ε, Z₀) = {(q₁, ε)}

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, [q₀, X, q₀], [q₀, X, q₁], [q₁, X, q₀], [q₁, X, q₁],

[q₀, Z₀, q₀], [q₀, Z₀, q₁], [q₁, Z₀, q₀], [q₁, Z₀, q₁] }

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 ® [q₀, Z₀, q₀] | [q₀, Z₀, q₁]

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 :

d₁) [q₀, Z₀, q₀] ® 0 [q₀, X, q₀][q₀, Z₀, q₀]

| 0 [q₀, X, q₁][q₁, Z₀, q₀]

[q₀, Z₀, q₁] ® 0 [q₀, X, q₀][q₀, Z₀, q₁]

| 0 [q₀, X, q₁][q₁, Z₀, q₁]

d₂) [q₀, X, q₀] ® 0 [q₀, X, q₀][q₀, X, q₀]

| 0 [q₀, X, q₁][q₁, X, q₀]

[q₀, X, q₁] ® 0 [q₀, X, q₀][q₀, X, q₁]

| 0 [q₀, X, q₁][q₁, X, q₁]

d₃) [q₀, X, q₁] ® 1

d₄) [q₁, Z₀, q₁] ® ε

d₅) [q₁, X, q₁] ® ε

d₆) [q₁, X, q₁] ® 1

Nhận xét rằng không có luật sinh nào cho các biến [q₁, X, q₀] và [q₁, Z₀, q₀]. Vì tất cả các luật sinh cho biến [q₀, X, q₀] và [q₀, Z₀, q₀] đều có chứa [q₁, X, q₀] hoặc [q₀, Z₀, q₀] ở 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 [q₀, X, q₀] hoặc [q₀, Z₀, q₀]. 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 ® [q₀, Z₀, q₁]

[q₀, Z₀, q₁] ® 0 [q₀, X, q₁][q₁, Z₀, q₁]

[q₀, X, q₁] ® 0 [q₀, X, q₁][q₁, X, q₁]

[q₀, X, q₁] ® 1

[q₁, Z₀, q₁] ® ε

[q₁, X, q₁] ® ε

[q₁, X, q₁] ® 1

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 (Q_M, Σ, Γ, δ_M, q₀, Z₀, F_M) và đặt R là L(A) với DFA A (Q_A, å, d_A, p₀, F_A). 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.

Hình 6.6 - Chạy một FA và PDA song song

Một cách hình thức, đặt M’ (Q_A × Q_M, Σ, Γ, δ, [p₀, q₀], Z₀, F_A × F_M), trong đó hàm chuyển δ được xác định như sau :

δ ([p, q], a, X) chứa ([p’, q’], ) ⇔ d_A(p, a) = p’ và d_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 : ( [p 0 , q 0 ] , w, Z 0 ) ⊢ i M ’ ([p, q], ε ,  ) ⇔ (q 0 , w, Z 0 ) ⊢ i M (q, ε ,  ) và d (p 0 , w) = p (1)

Với i = 0: thì (1) hiển nhiên đúng vì p = p 0 , q = q 0 ,  = Z 0 và w = ε .

Giả sử (1) đúng tới i - 1 (i > 0).

Xét ([p 0 , q 0 ], xa, Z 0 ) ⊢ i -1 M ’ ([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, d A (p 0 , x) = p’ và (q 0 , x, Z 0 ) ⊢ i -1 M (q’, ε , β ).

Theo định nghĩa của d , thực tế ([p’, q’], a, β ) ⊢ M ‘ ([p, q], ε ,  ) nên có thể suy ra d A (p’, a) = p và (q’, a, β ) ⊢ M (q, ε ,  ). Vậy d A (p 0 , w) = p và (q 0 , w, Z 0 ) ⊢ * M (q, ε ,  ).

Tương tự, ta có thể chứng minh rằng : Nếu (q 0 , w, Z 0 ) ⊢ i M (q, ε ,  ) và d A (p 0 , w) = p thì ([p 0 , q 0 ], w, Z 0 ) ⊢ * 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 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.