0.3 Văn phạm phi ngữ cảnh  (Page 6/17)

Giải thuật tìm V' như sau:

Begin

(1) OLDV:= Æ;

(2) NEWV:= {A  A  w với w  T *};

(3) While OLDV ¹ NEWV do

begin

(4) OLDV := NEWV;

(5) NEWV := OLDV  {A  A   với   (T  OLDV)*}

end;

(6) V' := NEWV;

end;

Rõ ràng rằng nếu biến A được thêm vào V’ tại bước (2) hoặc (5) thì A sẽ dẫn ra được chuỗi ký hiệu kết thúc. Ta chứng minh rằng nếu A dẫn ra được một chuỗi ký hiệu kết thúc thì A được thêm vào tập NEWV.

Dùng chứng minh quy nạp theo độ dài của dẫn xuất A * w.

Nếu độ dài bằng 1 thì A   là một luật sinh trong P. Vậy A được đưa vào V’ tại bước (2).

Giả sử kết quả đúng tới k -1 bước dẫn xuất ( k>1)

Nếu A  X1X2 ... Xn * w bằng k bước thì ta có thể viết w = w1w2 ... wn, trong đó Xi * wi, với 1  i  n bằng ít hơn k bước dẫn xuất. Theo giả thiết quy nạp thì các biến Xi này được thêm vào V’. Khi Xi cuối cùng được thêm vào V’ thì vòng lặp (3) vẫn tiếp tục lặp một lần nữa và A sẽ được thêm vào V’ tại (5).

Ta chứng minh L(G’) = L(G) :

Chọn V’ là tập hợp tại (6) và P' là tập tất cả các luật sinh mà các ký hiệu của nó thuộc (V’  T) thì chắc chắn rằng có tồn tại văn phạm G’ (V’, T, P’, S) thoả mãn tính chất: nếu A  V’ thì A * w với w nào đó thuộc T *. Hơn nữa, mỗi luật sinh của P’ đều là luật sinh của P nên ta có L(G’)  L(G).

Ngược lại giả sử một từ w  L(G) - L(G’) thì một dẫn xuất bất kỳ của w phải liên quan đến các biến thuộc V – V’ hoặc luật sinh thuộc P – P’ (các dẫn xuất này đưa ra các biến thuộc V – V’), nhưng do không có biến nào trong V – V’ dẫn đến chuỗi kết thúc, điều này dẫn đến mâu thuẫn.

Vậy L(G’) = L(G).

Hay có thể nói 2 ngôn ngữ được cho từ 2 văn phạm G và G’ là tương đương nhau, hay nói cách khác: nếu có một văn phạm G thì luôn luôn có một văn phạm G’ tương ứng mà trong đó mỗi biến của G’ đều cho ra ký hiệu kết thúc.

BỔ ĐỀ 2: (Dùng loại bỏ các biến không được dẫn ra từ ký hiệu bắt đầu văn phạm)

Nếu G (V, T, P, S) là CFG thì ta có thể tìm được CFG G’ (V’, T’, P’, S) tương đương sao cho mỗi X  V’  T’ tồn tại ,   (V’  T’)* để S * X.

Chứng minh

Tập V’  T’ gồm các ký hiệu xuất hiện trong dạng câu của G được xây dựng bởi giải thuật lặp như sau :

. Đặt V’ = {S}; T’ = ;

. Nếu A  V’ và A  1| 2 | ... | n là các luật sinh trong P thì thêm tất cả các biến của 1, 2, ... , n vào V’ và các ký hiệu kết thúc của 1, 2 ,..., n vào T’.

. Lặp lại giải thuật cho đến khi không còn biến hoặc ký hiệu kết thúc nào được thêm vào nữa.

Dễ thấy, X  V’  T’ thì tồn tại ,   (V’  T’)* để S * X, trong đó P’ là tập hợp tất cả các luật sinh của P chỉ chứa các ký hiệu thuộc (V’  T’).

Ta dễ dàng chứng minh L(G’) = L(G) .

ĐỊNH LÝ 5.2: Mỗi ngôn ngữ phi ngữ cảnh (CFL) không rỗng được sinh ra từ một văn phạm phi ngữ cảnh (CFG) không có ký hiệu vô ích.

Chứng minh

Đặt L = L(G) là CFL không rỗng.

Đặt G1 là kết quả của việc áp dụng bổ đề 1 vào G và G2 là kết quả của việc áp dụng bổ đề 2 vào G1.

Giả sử G2 có ký hiệu vô ích là X. Theo bổ đề 2 ta có S *G2 X. Vì tất cả các ký hiệu trong G2 đều có trong G1 nên theo bổ đề 1: S *G1 X *G1 w với w là chuỗi ký hiệu kết thúc. Vì vậy không có ký hiệu nào trong dẫn xuất X *G1 w bị loại bỏ bởi bổ đề 2, vậy X dẫn ra ký hiệu kết thúc trong G2 . Suy ra X là ký hiệu có ích (mâu thuẫn).