Ngôn ngữ hình thức

3.5. Automat đẩy xuống (Push down Automata)

Như đã biết, ngôn ngữ chính quy được sinh từ văn phạm chính quy, đồng thời cũng được đoán nhận bởi các automat hữu hạn (đơn định hoặc không đơn định). Trong phần này sẽ biết thêm một điều tương tự là ngôn ngữ phi ngữ cảnh được sinh ra từ văn phạm phi ngữ cảnh và được đoán nhận bởi một loại automat khác - gọi là automat đẩy xuống (PDA). Có một điều khác biệt là chỉ có dạng automat đẩy xuống không đơn định (NPDA) mới có thể đủ mạnh để đoán nhận lớp ngôn ngữ phi ngữ cảnh, còn dạng đơn định (DPDA) chỉ cho phép đoán nhận một tập con thực sự của lớp ngôn ngữ này. Tuy nhiên, tập con đó cũng đã bao gồm phần lớn các ngôn ngữ lập trình bậc cao.

3.5.1. Mô tả PDA

Automat đẩy xuống thực chất là một automat với sự điều khiển cả hai: băng vào và Stack (bộ đẩy xuống).Về cơ bản, Automat đẩy xuống giữ tất cả các thành phần của một automat 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ộ nhớ phụ, nhờ đó mà khả năng ghi nhớ của automat đượ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 automat đẩy xuống có thể đoán nhận cả các biểu thức

R * R

không chính quy. Chẳng hạn tập hợp L = {wcw | w  (0+1) } (với w

là xâu đảo

ngược của xâu 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 đoán nhận bởi bất kỳ một automat hữu hạn nào.

Về mặt trực quan Automat Push down (Automat đẩy xuống) có thể coi là một hệ thống mô tả như sau:

Có một băng vào (kênh vào), băng này gồm nhiều ô hay ngăn, mỗi ngăn chứa một ký tự của bảng chữ cái nào đó gọi là bảng chữ cái vào. Các ký tự vào được xếp bắt đầu từ ngăn bên trái nhất, băng vào được coi như dài vô hạn về bên phải.

Có bộ điều khiển, gồm một số hữu hạn trạng thái.

Có một đầu đọc, đầu đọc này dò đọc trên băng vào. Mỗi lần đầu đọc chỉ đọc một ký tự trong một ngăn của băng vào. Sau mỗi lần đọc một ký tự vào nó dịch chuyển sang bên phải một ngăn hoặc đứng yên.

Có một bộ nhớ phụ, gọi là băng đẩy xuống, còn gọi là Stack. Băng đẩy xuống cũng gồm nhiều ngăn, mỗi ngăn chứa một ký tự của bảng chữ cái nào đó gọi là bảng chữ cái đẩy xuống (Push down Alphabet). Băng đẩy xuống hoạt động theo nguyên tắc vào sau ra trước (Last in First out). Ký tự đưa vào hoặc lấy ra bao giờ cũng ở đỉnh của Stack. Hình 3.5 mô tả các bộ phận của Automat Pushdown.

Có thể bạn quan tâm!

Xem toàn bộ 254 trang tài liệu này.

Hình 3.5 Mô tả một PDA

3.5.2. Định nghĩa Automat đẩy xuống

Automat đẩy xuống có một bộ điều khiển hữu hạn và một Stack. Stack chứa một xâu các ký tự thuộc một bảng chữ cái nào đó. Ký tự bên trái nhất của xâu xem như ký tự tại đỉnh Stack.

PDA được gọi là không đơn định nếu như có nhiều hơn một lựa chọn các phép chuyển trong một lần chuyển nào đó. Ngược lại gọi là PDA đơn định.

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

- Kiểu thứ nhất phụ thuộc vào ký tự vào, tức là với một trạng thái, một ký tự tại đỉnh Stack và một ký tự vào; PDA sẽ lựa chọn trạng thái kế tiếp và một xâu các ký tự thay thế trên Stack, đầu đọc dịch đi sang phải một ký tự.

- Kiểu thứ hai không phụ thuộc vào ký tự vào, gọi là ε - dịch chuyển: tương tự như kiểu thứ nhất, chỉ khác là ký tự vào 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 vào để sắp xếp lại các ký tự trong ngăn xếp.

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

- Ngôn ngữ được đoán nhận bởi Stack rỗng: gồm tất cả các xâu vào mà sau một dãy các phép chuyển trạng thái làm cho automat dẫn tới Stack rỗng.

- Ngôn ngữ được đoán 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ữ đoán nhận bởi automat có thể định nghĩa gồm tất cả các xâu vào mà có một dãy các phép chuyển làm cho automat 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ự đoán nhận xâu này là tương đương nhau trong mọi trường hợp, có nghĩa là nếu một ngôn ngữ được đoán nhận bởi Stack rỗng của một PDA nào đó thì nó cũng sẽ được đoán 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 đoán nhận xâu 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 đoán nhận xâu bằng Stack rỗng. Nguyên lý này được phát biểu như sau: Một ngôn ngữ được đoán 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:

1) Định nghĩa

Một automat đẩy xuống M là một hệ thống M = <Q, Σ, Γ, δ, q , Z , F). Trong đó:

0 0

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

2. Σ là bảng chữ cái gọi là bảng chữ cái nhập (vào).

3. Γ là bảng chữ cái gọi là bảng chữ cái Stack.

4. δ: hàm chuyển ánh xạ từ Q × (Σ {ε}) × Γ → Q × Γ .

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

6. Z0 là một chữ cái riêng của Stack gọi là ký tự bắt đầu trên Stack.

7. 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ế đoán nhận ngôn ngữ bằng Stack rỗng thì tập hợp F = ∅)

Trừ khi ta dùng các ký tự khác, ta quy ước dùng chữ cái nhỏ ở đầu bảng chữ cái để chỉ các ký tự vào, các chữ cái nhỏ cuối bảng chữ cái để chỉ các xâu vào. Các chữ cái in hoa và chữ Hy lạp chỉ ký tự và xâu ký tự trên Stack.

2) Sự dịch chuyển

a) Hàm chuyển phụ thuộc ký tự vào

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

Trong đó: q và pi với 1 ≤ i ≤ m, là các trạng thái thuộc tập Q, a  Σ, Z là một

ký trên đỉnh Stack và γ  Γ với 1 ≤ i ≤ m.

Nghĩa là PDA đang ở trạng thái q nhìn thấy ký tự vào a và ký tự Z tại đỉnh Stack thì nó chuyển sang một trạng thái pi nào đó, thay Z bằng γi và dịch chuyển đầu đọc đi một ký tự. Ta quy ước rằng ký tự bên trái nhất của γi sẽ là ký tự được thay cao nhất trên Stack (nghĩa là nó nằm tại đỉnh Stack mới) và ký tự bên phải nhất của γi là ký tự được thay thấp nhất trong Stack. Chú ý rằng không được phép chọn pi và γj với i ≠ j tại một bước chuyển nào đó.

b) Hàm chuyển không phụ thuộc ký tự vào

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

Trong đó: q là trạng thái mà PDA đang giữ, độc lập với ký tự vào, PDA đi vào trạng thái pi thay Z bởi γi với 1 ≤ i ≤ m. Trong trường hợp này đầu đọc không dịch chuyển.

Ví dụ: PDA đoán nhận ngôn ngữ {wcwR |w  (0+1)*} bằng Stack rỗng.

M = <Q, Σ, Γ, δ, q0, Z0, F). Trong đó: Q = {q1, q2};

Σ = {0, 1, c};

Γ = {R, B, Y};

q0= q1; Z0= R; F = ∅.

δ:

1. δ(q , 0, R) = {(q , BR)};

1 1

2. δ(q , 1, R) = {(q , YR)};

1 1

3. δ(q , 0, B) = {(q , BB)};

1 1

4. δ(q , 1, B) = {(q , YB)};

1 1

5. δ(q , 0, Y) = {(q , BY)};

1 1

6. δ(q , 1, Y) = {(q , YY)};

1 1

7. δ(q , c, R) = {(q , R)};

1 2

8. δ(q , c, B) = {(q , B)};

1 2

9. δ(q , c, Y) = {(q , Y)};

1 2

10. δ(q , 0, B) = {(q , ε)};

2 2

11. δ(q , 1, Y) = {(q , ε)};

2 2

12. δ(q , ε, R) = {(q , ε)}.

2 2

3) Hình trạng (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 trạng. Hình trạng là một bộ ba (q, w, γ), trong đó q là trạng thái, w là xâu vào và γ là xâu các ký tự nằm trong Stack.

Nếu M = <Q, Σ, Γ, δ, q0, Z0, F> là một PDA, ta nói: (q, aw, Zα) ⊢M (p, w, βα) nếu δ(q, a, Z) chứa (p, β) Ở đây, a có thể là một ký tự trong xâu vào hoặc ε.

M M

Ta dùng ký hiệu ⊢* cho bao đóng phản xạ và bắc cầu của ⊢ , tức là: I ⊢*

K đối với mỗi ID I và I ⊢MJ và J ⊢*K thì I ⊢* 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 ký hiệu ⊢M, ⊢iM

và ⊢ M có thể được bỏ qua khi M đã được xác định.

Chẳng hạn, với PDA mô tả như trên, ta có (q , BY)  δ(q , 0, Y), suy ra rằng

1 1

⊢

(q , 011, YYR) (q , 11, BYYR).

1 1

3.5.3. Ngôn ngữ đoán nhận bởi PDA

Cho PDA M = <Q, Σ, Γ, δ, q0, Z0, F>.

- Ngôn ngữ được đoán nhận bởi PDA M bằng trạng thái kết thúc là:

L (M) = {w | (q , w, Z ) ⊢* (p, ε, γ) với p  F và γ  Γ }

0 0

- Ngôn ngữ được đoán nhận bởi PDA M bằng Stack rỗng là:

⊢

L(M) = {w | (q , w, Z ) * (p, ε, ε) với p  Q}.

0 0

Khi có sự đoán nhận ngôn ngữ 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à ∅.

Ví dụ:

Các phép chuyển hình trạng của PDA M đơn định được cho trong ví dụ trên

R *

đoán nhận xâu 001c100 thuộc ngôn ngữ {wcw |w  (0+1) } bằng Stack rỗng như

⊢ ⊢ ⊢

(q , 001c100, R) (q , 01c110, BR) (q , 1c110, BBR) (q , c100, YBBR)

1 1 1 1

⊢ ⊢ ⊢ ⊢ ⊢

(q , 100, YBBR) (q , 00, BBR) (q , 0, BR) (q , ε, R) (q , ε, ε): Đoán

2 2 2 2 2

nhận.

Nhận xét:

R *

Trong ví dụ thiết kế PDA đoán nhận ngôn ngữ {wcw |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ý tự trên băng vào, với một ký tự 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à automat đẩy xuống đơn định - DPDA.

Ví dụ:

PDA M không đơn định đoán nhận ngôn ngữ {ww

|w  (0+1) } bằng Stack rỗng.

M = <{q1, q2}, {0, 1}, {R, B, Y}, δ, q1, R, ∅>: 1. δ(q1, 0, R) = {(q1, BR)};

2. δ(q1, 1, R) = {(q1,YR)};

3. δ(q1, 0, B) = {(q1, BB), (q2, ε)};

4. δ(q1, 0, Y) = {(q1, BY)};

5. δ(q1, 1, B) = {(q1, YB)};

6. δ(q1, 1, Y) = {(q1, YY),(q2, ε)};

7. δ(q2, 0, B) = {(q2, ε)};

8. δ(q2, 1, Y) = {(q2, ε)};

9. δ(q1, ε, R) = {(q2, ε)};

10. δ(q2, ε, R) = {(q2, ε)}.

Cũng như NFA, một PDA không đơn định (NPDA) M đoán nhận một xâu vào nếu có một dãy 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ỏ xâu vào. Một xâu vào 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).

Ví dụ:

Các phép chuyển hình trạng (hình thái) của PDA đoán nhận xâu 001100 thuộc ngôn ngữ {wwR |w  (0+1)*} bằng Stack rỗng như sau:

(q1, 001100, R) ⊢ (q2, 001100, ε): Không đoán nhận

┬

(q1, 01100, BR) ⊢ (q2, 1100, R) ⊢ (q2, 1100, ε): Không đoán nhận

┬

(q1, 1100, BBR)

┬

(q1,100, YBBR) ⊢ (q2,00, BBR) ⊢ (q2, 0, BR) ⊢ (q2, ε, R) ⊢ (q2, ε, ε): Đoán nhận

┬

(q1, 00, YYBBR)

┬

(q1, 0, BYYBBR) ⊢ (q2, ε, YYBBR): Không đoán nhận

┬

(q1, ε, BBYYBBR): Không đoán nhận

Như vậy, để đoán nhận xâu 001100 thuộc ngôn ngữ {wwR |w  (0+1)*} bằng Stack rỗng, PDA thực hiện dãy các phép chuyển hình trạng:

(q1, 001100, R) ⊢ (q1, 01100, BR) ⊢ (q1, 1100, BBR) ⊢ (q1,100, YBBR) ⊢

(q2,00, BBR) ⊢ (q2, 0, BR) ⊢ (q2, ε, R) ⊢ (q2, ε, ε): Đoán nhận

Một PDA M = <Q, Σ, Γ, δ, q0, Z0, F> được gọi là đơn định nếu:

1. Với q  Q và Z  Γ: nếu δ(q, ε, Z) ≠ ∅ thì δ(q, a, Z) = ∅ với 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ý tự vào (ε - dịch chuyển) và phép chuyển trên một ký tự của xâu vào. Đ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ư automat 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 automat hữu hạn, dạng đơn định và không đơn định là tương đương nhau về phương diện đoán nhận ngôn ngữ. Tuy nhiên, điều này không đúng với automat đẩ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ữ wwR được đoán nhận bởi một PDA không đơn định nhưng không được đoán nhận bởi bất kỳ một PDA đơn định nào.

Ví dụ:

1. Cho Automat pushdown M = < Q, , , , q0 , Z0 , F >; Trong đó: Q = {q0, q1};

= {a, b};

 = {Z0 , X}; F =  ;

: (q0 , a, Z0 ) = {(q0, X)};