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

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, ) 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, , , , q0, Z0, ). Đặ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 ® [q0, Z0, q] ,q Î Q.

2) [q, A, q m+1] ® a[q1, B1, q2][q2, B2, q3] ... [qm, Bm, qm+1]

q, q1, q2, ..., qm+1  Q, a    {} và A, B1, B2, ..., Bm  

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.

Để 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, , )