0.4 Ôtômát đẩy xuống  (Page 5/8)

2)d(q1, 1, R) = {(q1,YR)}

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

4)d(q1, 0, Y) = {(q1, BY)}

5)d(q1, 1, B) = {(q1, YB)}

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

7)d(q2, 0, B) = {(q2, e)}

8)d(q2, 1, Y) = {(q2, e)}

9)d(q1, e, R) = {(q2, e)}

10)d(q2, e, R) = {(q2, 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 q2 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 wwR 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ữ {wwR w  (0+1)*} bằng Stack rỗng như sau :

Khởi đầu

¯

(q1, 001100, R) ® (q2, 001100, e) : Không chấp nhận

¯

(q1, 01100, BR) ® (q2, 1100, R) ® (q2, 1100, e) : Không chấp nhận

¯

(q1, 1100, BBR)

¯

(q1, 100, YBBR) ® (q2, 00, BBR)

¯ ¯

(q1, 00, YYBBR) (q2, 0, BR)  (q2, e, R)  (q2, e, e) : Chấp nhận

¯

(q1, 0, BYYBBR) ® (q2, e, YYBBR) : Không chấp nhận

¯

(q1, 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, , , , q0, Z0, F) được gọi là đơn định nếu:

1) q  Q và Z  : nếu (q, , Z)   thì (q, a, Z) = , 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ữ wwR đượ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.

Pda và văn phạm phi 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(M2) với PDA M2 thì L là N(M1) với PDA M1 nào đó.

Chứng minh

Ta sẽ xây dựng M1 tương tự như M2 nhưng M1 sẽ xóa rỗng Stack của nó khi M2 đi vào trạng thái kết thúc. Ta dùng một trạng thái qe của M1 để xóa Stack của nó và dùng ký hiệu đánh dấu đáy Stack M1 bằng ký hiệu X0, vì vậy M1 không thể làm rỗng Stack của nó khi M2 chưa đi vào trạng thái kết thúc.

Đặt M2 (Q, , , , q0, Z0, F) là PDA sao cho L = L(M2).