Otomat đẩy xuống ( PDA : PUSHDOWN AUTOMATA)

Nội dung chính:

Trong chương này, chúng ta khảo sát một dạng mô hình ôtômát khác, có khả năng nhận diện được lớp ngôn ngữ mà văn phạm phi ngữ cảnh sinh ra - ôtômát đẩy xuống (PDA) - với sự bổ sung thêm của Stack đóng vai trò như một bộ giữ nhớ trong quá trình ôtômát thực hiện các phép chuyển để nhận dạng ngôn ngữ. Tiếp theo đó, mối quan hệ tương đương giữa hai cơ chế - ôtômát đẩy xuống và CFG- dùng biểu diễn cho lớp văn phạm phi ngữ cảnh cũng sẽ được nêu ra và chứng minh chặt chẽ.

Mục tiêu cần đạt :

Cuối chương này, sinh viên có thể:

Thiết kế PDA chấp nhận một ngôn ngữ phi ngữ cảnh cho trước bằng Stack rỗng hay trạng thái kết thúc.

Chuyển một PDA chấp nhận ngôn ngữ bằng trạng thái kết thúc sang PDA chấp nhận ngôn ngữ bằng Stack rỗng và ngược lại.

Xây dựng NPDA chấp nhận ngôn ngữ sinh ra từ một CFG.

Viết văn phạm phi ngữ cảnh sinh ra lớp ngôn ngữ được chấp nhận bởi một NPDA cho trước.

Kiến thức cơ bản:

Để tiếp thu tốt nội dung của chương này, sinh viên cần nắm vững các tính chất của lớp ngôn ngữ phi ngữ cảnh; cơ chế đoán nhận ngôn ngữ của dạng máy trừu tượng ôtômát và các thành phần bắt buộc của chúng; …

Tài liệu tham khảo :

V.J. Rayward-Smith – A First course in Formal Language Theory (Second Editor) – McGraw-Hill Book Company Europe – 1995 (Chapter 6 : Pushdown Automata )

John E. Hopcroft, Jeffrey D.Ullman – Introduction to Automata Theory, Languages and Computation – Addison – Wesley Publishing Company, Inc – 1979 (Chapter 5 : Pushdown Automata )

Hồ Văn Quân – Giáo trình lý thuyết ôtômát và ngôn ngữ hình thức – Nhà xuất bản Đại học quốc gia Tp. Hồ Chí Minh – 2002.

Copy right by David Matuszek - NPDAs and CFGs:

http://www.netaxs.com/people/nerp/automata/npda-cfg0.html

Mô tả PDA

Ôtômát đẩy xuống thực chất là một ôtômát với sự điều khiển cả hai: băng nhập và Stack (bộ đẩy xuống). Về cơ bản, nó vẫn giữ tất cả các thành phần của một ôtômát hữu hạn, với sự bổ sung thêm một ngăn xếp làm việc (Stack) đóng vai trò như một bộ giữ nhớ, nhờ đó mà khả năng ghi nhớ của ôtômát được tăng thêm. Stack xem như là một chồng đĩa, vì vậy cái đặt vào sau sẽ lấy ra trước (LIFO).

Với sự mở rộng này ôtômát đẩy xuống có thể chấp nhận cả các biểu thức không chính quy. Chẳng hạn tập hợp L = {wcw^R | w ∈ (0+1)^*} (với w^R là chuỗi đảo ngược của chuỗi w) là một ngôn ngữ phi ngữ cảnh sinh bởi văn phạm S → 0S0 | 1S1 | c và nó không thể được chấp nhận bởi bất kỳ một ôtômát hữu hạn nào.

Hình 6.1 - Mô tả một PDA

Để chấp nhận ngôn ngữ L như trên ta dùng bộ điều khiển có hai trạng thái q₁, q₂ và một Stack trên đó ta đặt các đĩa xanh (B), vàng (Y), đỏ (R). Thiết bị sẽ thao tác theo các quy tắc sau đây:

1) Máy sẽ bắt đầu với một đĩa đỏ ở trên Stack và bộ điều khiển ở trạng thái q₁.

2) Nếu 0 được đưa vào thiết bị thì ta đặt một đĩa xanh vào Stack. Nếu đưa 1 vào thiết bị ở trạng thái q₁ thì ta đặt một đĩa vàng vào Stack. Cả hai trường hợp thiết bị không thay đổi trạng thái.

3) Nếu c được đưa vào thiết bị ở trạng thái q₁ thì thiết bị đổi trạng thái sang q₂ và không thay đổi Stack.

4) Nếu 0 được đưa vào thiết bị ở trạng thái q₂ và đỉnh Stack là đĩa màu xanh thì đĩa được lấy ra. Nếu 1 đưa vào thiết bị ở trạng thái q₂ và đĩa vàng tại đỉnh Stack thì ta loại bỏ đĩa này. Trạng thái q₂ không thay đổi.

5) Nếu thiết bị ở trạng thái q₂ và đĩa đỏ tại đỉnh Stack ta loại bỏ đĩa này không cần ký hiệu nhập.

6) Ngoài các trường hợp trên thì thiết bị không thay đổi.

Các quy tắc trên được tóm tắt như trong bảng sau:

Hình 6.2 - Mô tả hoạt động của PDA chấp nhận ngôn ngữ {wcw^R |w∈ (0+1)^*}

Một chuỗi được chấp nhận bởi thiết bị nếu nó đã đọc duyệt qua đến hết chuỗi đồng thời với Stack trở về trạng thái rỗng.

Nhận xét: Nhờ Stack có khả năng lưu giữ một số bất kỳ các ký hiệu mà PDA có thể nhớ nửa phần đầu của chuỗi (w) cho tới khi gặp ký hiệu phân cách c, cho dù chuỗi có độ dài lớn đến bao nhiêu. Và sau đó, các ký hiệu này được đem ra để so sánh dần với phần chuỗi ngược còn lại (w^R). Một ôtômát hữu hạn không có được khả năng ghi nhớ đó.

Định nghĩa

Ôtômát đẩy xuống có một bộ điều khiển hữu hạn và một Stack. Stack chứa một chuỗi các ký hiệu thuộc một bộ chữ cái nào đó. Ký hiệu bên trái nhất của chuỗi xem như ký hiệu tại đỉnh Stack. PDA không đơn định nếu như có một số hữu hạn các lựa chọn phép chuyển trong mỗi lần chuyển.

Phép chuyển sẽ có hai kiểu:

- Kiểu thứ nhất phụ 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ứ hai khô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.

Có hai cách để định nghĩa ngôn ngữ chấp nhận bởi ôtômát đẩy xuống:

- Ngôn ngữ được chấp nhận bởi Stack rỗng: gồm tất cả các input mà sau một chuỗi các phép chuyển trạng thái làm cho ôtômát dẫn tới Stack rỗng.

- Ngôn ngữ được chấp nhận bởi trạng thái kết thúc: ta thiết kế một số trạng thái kết thúc, khi đó ngôn ngữ chấp nhận bởi ôtômát có thể định nghĩa gồm tất cả các input mà có một chuỗi các phép chuyển làm cho ôtômát dẫn tới một trong những trạng thái kết thúc.

Ta có thể thấy hai cách định nghĩa cho sự chấp nhận chuỗi này là tương đương nhau trong mọi trường hợp, có nghĩa là nếu một tập hợp được chấp nhận bởi Stack rỗng của một PDA nào đó thì cũng sẽ được chấp nhận bằng trạng thái kết thúc trên một PDA khác, và ngược lại. Thiết kế PDA chấp nhận chuỗi bằng trạng thái kết thúc thường phổ biến hơn, nhưng sẽ dễ dàng hơn để chứng minh nguyên lý cơ bản của PDA khi thiết kế PDA chấp nhận chuỗi bằng Stack rỗng. Nguyên lý này được phát biểu như sau: 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.

Một cách hình thức, ta định nghĩa:

Định nghĩa : Một ôtômát đẩy xuống M là một hệ thống M (Q, Σ, Γ, δ, q₀, Z₀, F), trong đó :

1) Q là tập hữu hạn các trạng thái

2) Σ là bộ chữ cái gọi là bộ chữ cái nhập

3) Γ là bộ chữ cái gọi là bộ chữ cái Stack

4) δ: hàm chuyển ánh xạ từ Q × (Σ size 12{ union } {}{ε}) × Γ → tập con hữu hạn của Q × Γ^*

5) q₀ là trạng thái khởi đầu

5) Z₀ là một chữ cái riêng của Stack gọi là ký hiệu bắt đầu trên Stack

6) F ⊆ Q là tập các trạng thái kết thúc

(Trong trường hợp PDA được thiết kế chấp nhận ngôn ngữ bằng Stack rỗng thì tập hợp F = ∅)

Trừ khi ta dùng các ký hiệu khác, ta quy ước dùng chữ nhỏ gần đầu bảng chữ cái để chỉ các ký hiệu nhập, các chữ nhỏ cuối bảng chữ cái để chỉ các chuỗi nhập. Các chữ hoa và chữ Hy lạp chỉ ký hiệu và chuỗi ký hiệu Stack.

Sự dịch chuyển

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

δ(q, a, Z) = {(p₁, γ size 12{γ} {}₁), (p₂, γ size 12{γ} {}₂), ..., (p_m, γ size 12{γ} {}_m)}

trong đó q và p_i, 1 ≤ i ≤ m, là các trạng thái thuộc tập Q, a ∈ Σ, Z là một ký hiệu Stack và γ size 12{γ} {}_i ∈ Γ^*, 1 ≤ i ≤ m, là PDA ở trạng thái q với ký hiệu nhập a và ký hiệu Z tại đỉnh Stack, nó đi vào một trạng thái p_i nào đó thay Z bằng γ size 12{γ} {}_i và dịch chuyển đầu đọc đi một ký hiệu. Ta quy ước rằng ký hiệu bên trái nhất của γ size 12{γ} {}_i sẽ là ký hiệu được thay cao nhất trên Stack (nghĩa là nó nằm tại đỉnh Stack mới) và ký hiệu bên phải nhất của γ size 12{γ} {}_i là ký hiệu được thay thấp nhất trong Stack. Chú ý rằng không được phép chọn p_i và γ size 12{γ} {}_j với i ≠ j tại một bước chuyển nào đó.

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

δ(q, ε, Z) = {(p₁, γ size 12{γ} {}₁), (p₂, γ size 12{γ} {}₂), ..., (p_m, γ size 12{γ} {}_m)}

trong đó q là trạng thái mà PDA đang giữ, độc lập với ký hiệu nhập, PDA đi vào trạng thái p_i thay Z bởi γ size 12{γ} {}_i với 1 ≤ i ≤ m. Trong trường hợp này đầu đọc không dịch chuyển.

Thí dụ 6.1 : Mô tả dưới đây cho PDA chấp nhận ngôn ngữ {wcw^R | w ∈ (0+1)^*} bằng Stack rỗng.

M ({q₁, q₂}, {0, 1, c}, {R, B, Y}, d, q₁, R, ∅ size 12{ emptyset } {} )

1) d(q₁, 0, R) = {(q₁, BR)}

2) d(q₁, 1, R) = {(q₁, YR)}

3) d(q₁, 0, B) = {(q₁, BB)}

4) d(q₁, 1, B) = {(q₁, YB)}

5) d(q₁, 0, Y) = {(q₁, BY)}

6) d(q₁, 1, Y) = {(q₁, YY)}

7) d(q₁, c, R) = {(q₂, R)}

8) d(q₁, c, B) = {(q₂, B)}

9) d(q₁, c, Y) = {(q₂, Y)}

10) d(q₂, 0, B) = {(q₂, e)}

11) d(q₂, 1, Y) = {(q₂, e)}

12) d(q₂, e, R) = {(q₂, e)}

Hình 6.3 - Mô tả PDA chấp nhận wcw R bằng Stack rỗng

Chú ý rằng mỗi phép chuyển PDA sẽ viết lên đỉnh Stack một chuỗi  có độ dài 2. Chẳng hạn d(q₁, 0, R) = {(q₁, BR)}. Nếu  có độ dài bằng 1 thì PDA đơn giản là thay ký hiệu tại đỉnh Stack và không làm thay đổi độ dài Stack. Nếu  bằng ε thì PDA loại bỏ (Pop) phần tử tại đỉnh Stack. Chẳng hạn d(q₂, e, R) = {(q₂, e)} nghĩa là PDA ở trạng thái q₂ với R ở đỉnh Stack thì PDA xóa R độc lập với ký hiệu nhập, trong trường hợp này đầu đọc không dịch chuyển, điều này có nghĩa là PDA không yêu cầu còn một ký hiệu nào trên chuỗi nhập.

Hình thái (ID : Instantaneous Descriptions)

Để hình thức hóa cấu hình của một PDA với một PDA cụ thể, ta định nghĩa một hình thái (ID). ID phải ghi nhớ trạng thái và nội dung của Stack. 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, Σ, Γ, δ, q₀, Z₀, F) là một PDA, ta nói :

(q, aw, Zα) ⊢M (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 ε. Chẳng hạn với PDA mô tả như trên, ta có (q₁, BY) ∈ d(q₁, 0, Y), suy ra rằng (q₁, 011, YYR) ⊢ (q₁, 11, BYYR).

Ta dùng ký hiệu ⊢^*M cho bao đóng phản xạ và bắt cầu của ⊢M, tức là : I ⊢^* I đối với mỗi ID I, và I ⊢M J và J ⊢^*M K thì I ⊢^*M K. Ta viết I ⊢ⁱ K nếu ID I trở thành K sau chính xác i bước chuyển. Chữ chỉ số dưới M trong các ky 1hiệu ⊢M, ⊢ⁱM và ⊢^*M có thể được bỏ qua khi M đã được xác định.

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

Với PDA M (Q, Σ, Γ, δ, q₀, Z₀, F), ta định nghĩa :

Ngôn ngữ được chấp nhận bởi trạng thái kết thúc là:

L (M) = {w | (q₀, w, Z₀) ⊢^* (p, ε, γ size 12{γ} {}) với p ∈ F và γ size 12{γ} {}∈ Γ^*}

Ngôn ngữ được chấp nhận bởi Stack rỗng là :

N(M) = {w | (q₀, w, Z₀) ⊢^* (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à ∅ size 12{ emptyset } {}.

Thí dụ 6.2 : 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ữ {wcw^R |w ∈ (0+1)^*} bằng Stack rỗng như sau :

(q₁, 001c100, R) ⊢ (q₁, 01c110, YR) ⊢ (q₁, 1c110, YYR) ⊢ (q₁, c100, BYYR) ⊢

(q₂, 100, BYYR) ⊢ (q₂, 00, YYR) ⊢ (q₂, 0, YR) ⊢ (q₂, ε, R) ⊢ (q₂, ε, ε) : Chấp nhận

Nhận xét : Trong ví dụ thiết kế PDA chấp nhận ngôn ngữ {wcw^R |w ∈ (0+1)^*} bằng Stack rỗng như trên, ta thấy các giá trị hàm chuyển của nó luôn là là đơn trị. Tại mỗi thời điểm từ một trạng thái trong bộ điều khiển, có thể đọc vào hoặc không đọc một ký hiệu trên băng nhập, với một ký hiệu tại đỉnh Stack, chỉ có một giá trị xác định bước chuyển kế tiếp. Vì thế, ta gọi dạng PDA này là ôtômát đẩy xuống đơn định - DPDA.

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

Thí dụ 6.3 : Thiết kế PDA chấp nhận ngôn ngữ {ww^R | w ∈ (0+1)^*} bằng Stack rỗng.

Rõ ràng ta thấy khi không có sự hiện diện của ký hiệu c ở giữa chuỗi nhập để xác định thời điểm bộ điều khiển có thể chuyển từ trạng thái q₁ sang trạng thái q_2, thì vấn đề sẽ trở nên phức tạp hơn khi cần phải quyết định đâu là ký hiệu bắt đầu cho chuỗi ngược (w^R) ? Ở mỗi thời điểm mà bộ điều khiển đọc thấy hai ký hiệu liên tiếp giống nhau trong chuỗi nhập thì bắt buộc nó phải đoán thử cả hai khả năng cho ký hiệu thứ hai: hoặc vẫn giữ trạng thái q₁ và Push vào Stack nếu xem ký hiệu này vẫn thuộc chuỗi xuôi (w), hoặc chuyển sang trạng thái q₂ và Pop khỏi Stack nếu xem nó là ký hiệu bắt đầu cho chuỗi ngược (w^R).

Mô tả PDA không đơn định chấp nhận ngôn ngữ {ww^R |w ∈ (0+1)^*} bằng Stack rỗng

M ({q₁, q₂}, {0, 1}, {R, B, Y}, d, q₁, R, ∅ size 12{ emptyset } {} )

1) d(q₁, 0, R) = {(q₁, BR)}

2) d(q₁, 1, R) = {(q₁,YR)}

3) d(q1, 0, B) = {(q1, BB), (q2, e)}

4) d(q₁, 0, Y) = {(q₁, BY)}

5) d(q₁, 1, B) = {(q₁, YB)}

6) d(q1, 1, Y) = {(q1, YY),(q2, e)}

7) d(q₂, 0, B) = {(q₂, e)}

8) d(q₂, 1, Y) = {(q₂, e)}

9) d(q₁, e, R) = {(q₂, e)}

10) d(q₂, e, R) = {(q₂, e)}

Hình 6.4 - Mô tả PDA không đơn định chấp nhận wwR bằng Stack rỗng

Quy tắc (1) đến (3) cho phép M lưu trữ input trên Stack, quy tắc (3) và (6) cho phép M lựa chọn một trong hai phép chuyển. M có thể quyết định (đoán) đã đi đến giữa chuỗi nó chuyển sang phép chuyển thứ 2: M chuyển sang q₂ và thử sự thích hợp của phần chuỗi còn lại với các ký hiệu đang ở trên Stack. Nếu M đoán đúng và nếu chuỗi nhập có dạng ww^R thì M sẽ làm rỗng Stack của nó và chấp nhận chuỗi nhập.

Cũng như NFA một PDA không đơn định (NPDA) M chấp nhận một input nếu có một chuỗi các lựa chọn mà M làm rỗng Stack của nó. Nghĩa là M luôn luôn "đoán đúng", đoán sai không phải là nguyên nhân để loại bỏ input. Một input bị loại bỏ nếu và chỉ nếu không có sự lựa chọn nào để làm rỗng Stack (hay là không thể "đoán đúng" vì không tồn tại cách đúng).

Thí dụ 6.4 : Các phép chuyển hình thái của PDA chấp nhận chuỗi 001100 thuộc ngôn ngữ {ww^R | w ∈ (0+1)^*} bằng Stack rỗng như sau :

Khởi đầu

¯

(q₁, 001100, R) ® (q₂, 001100, e) : Không chấp nhận

¯

(q₁, 01100, BR) ® (q₂, 1100, R) ® (q₂, 1100, e) : Không chấp nhận

¯

(q₁, 1100, BBR)

¯

(q₁, 100, YBBR) ® (q₂, 00, BBR)

¯ ¯

(q₁, 00, YYBBR) (q₂, 0, BR) → (q₂, e, R) → (q₂, e, e) : Chấp nhận

¯

(q₁, 0, BYYBBR) ® (q₂, e, YYBBR) : Không chấp nhận

¯

(q₁, e, BBYYBBR) : Không chấp nhận

Hình 6.5 - Hình thái của PDA với input 001100

PDA đơn định (DPDA)

Một PDA M (Q, Σ, Γ, δ, q₀, Z₀, F) được gọi là đơn định nếu:

1) ∀q ∈ Q và Z ∈ Γ: nếu δ(q, ε, Z) ≠ ∅ size 12{ emptyset } {} thì δ(q, a, Z) = ∅ size 12{ emptyset } {}, ∀a ∈ Σ

2) Không có q ∈Q, Z ∈ Γ và a ∈ (Σ  {ε}) mà δ(q, a, Z) chứa nhiều hơn một phần tử.

Điều kiện 1 không cho phép khả năng chọn lựa giữa phép chuyển không xác định ký hiệu nhập (ε - dịch chuyển) và phép chuyển trên một ký hiệu input. Điều kiện 2 không cho phép chọn lựa một vài phép chuyển nào đó (q, a, Z) hay (q, ε, Z). Không như ôtômát hữu hạn FA, một PDA thì thông thường được xét là không đơn định trừ khi ta có ghi chú cụ thể.

Đối với ôtômát hữu hạn, dạng đơn định và không đơn định là tương đương nhau về phương diện chấp nhận ngôn ngữ. Tuy nhiên, điều này không đúng với ôtômát đẩy xuống, PDA không đơn định và PDA đơn định là không tương đương nhau. Thực tế ngôn ngữ ww^R được chấp nhận bởi một 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.