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

Xét A G’’ X1X2 ... Xn  i - 1G’’ w. Phải có luật sinh A   trong P sao cho X1X2 ... Xn tìm được khi loại bỏ các biến rỗng của . Vậy A Þ*G X1X2 ...Xn (chứng minh tương tự như ở trên). Ta viết w = w1w2 ...wn sao cho j ta có Xj  *G’’ wj (bằng ít hơn i bước). Theo giả thiết quy nạp Xj  *G’’ wj nếu Xj là biến. Nếu Xj là ký hiệu kết thúc thì wj = Xj và Xj  *G wj là hiển nhiên. Vậy A  *G w.

Cuối cùng ta áp dụng bổ đề 2 vào G’’ ta thu được G’ không có ký hiệu vô ích. Vì bổ đề 1 và bổ đề 2 không đưa ra thêm luật sinh mới nào nên G’ không có chứa ký hiệu là biến rỗng hay ký hiệu vô ích.

Hơn nữa S  *G’ w nếu và chỉ nếu S  *G w. Vậy L(G’) = L(G) - {}.

Thí dụ 5.10 : Loại bỏ luật sinh e trong văn phạm sau :

S ® AB

A ® aA | e

B ® bB | e

Trước hết, ta xác định tập các biến rỗng trong văn phạm: A, B là các biến rỗng vì có các luật sinh A ® e và B ® e. S cũng là biến rỗng vì có luật sinh S ® AB với A, B đều là các biến rỗng.

 Tập biến rỗng Nullable = {A, B, S}

Theo quy tắc xây dựng tập luật sinh P’ trong định lý , ta có tập luật sinh mới như sau :

S ® AB | A | B

A ® aA | a

B ® bB | b

Lưu ý rằng văn phạm mới G’ không sản sinh ra , trong khi G lại có sinh ra từ rỗng e. Vậy muốn có một văn phạm thực sự tương đương với văn phạm G thì ta phải bổ sung thêm luật sinh S ® e vào tập luật sinh của G’. Ta có, văn phạm G’ tương đương G.

Luật sinh đơn vị

Một luật sinh có dạng A ® B với A, B đều là biến gọi là luật sinh đơn vị.

ĐỊNH LÝ 5.4 : Mỗi CFL không chứa e được sinh ra bởi CFG không có ký hiệu vô ích, luật sinh e hoặc luật sinh đơn vị .

Chứng minh

Đặt L là CFL không chứa e và L = L(G) với G (V, T, P, S) là một CFG nào đó.

Theo định lý 3 ta có thể giả sử G không có luật sinh e. Xây dựng tập hợp mới P’ gồm các luật sinh từ P như sau:

Đầu tiên đưa các luật sinh không là luật sinh đơn vị vào P’.

Sau đó, nếu có luật sinh đơn vị dạng A * B với A, B  V thì thêm vào P’ tất cả các luật sinh dạng A  , với B  không phải là luật sinh đơn vị của P.

Chú ý rằng ta có thể dễ dàng kiểm tra có hay không A  *G B vì G không có luật sinh e và nếu A  G B1  G B2 ...  G Bm  G B (trong đó một vài biến nào đó có thể xuất hiện 2 lần) thì ta có thể tìm một chuỗi rút ngắn hơn A  *G B, vì vậy ta chỉ xét các luật sinh đơn vị không có biến lặp lại.

Bây giờ ta sửa lại văn phạm G’ (V, T, P’, S). Chắc chắn rằng nếu A   là một luật sinh trong P’ thì A  *G . Vậy nếu có dẫn xuất trong G’ thì có dẫn xuất trong G. Giả sử rằng w  L(G). Xét dẫn xuất trái của w trong G:

S  G 0  G 1  G ...  G n = w.

Nếu 0  i<n thì nếu trong G có i  G i+1 bằng luật sinh không là luật sinh đơn vị thì trong G’ cũng có i  G’ i+1 không là luật sinh đơn vị. Giả sử i  G i+1 bằng luật sinh đơn vị, nhưng bước dẫn xuất trước đó i - 1  i không phải bằng luật sinh đơn vị hoặc i = 0. Và chuỗi dẫn xuất trong G từ i + 1  G i + 2  G ...  G j tất cả đều bằng luật sinh đơn vị, còn từ j  G j+1 không là luật sinh đơn vị thì ta thấy tất cả các i, i+1, …, j sẽ có cùng độ dài và vì chuỗi dẫn xuất là dẫn xuất trái nên các ký hiệu thay thế phải ở cùng một vị trí. Do vậy, tại vị trí này j  G j+1 bằng một luật sinh nào đó thuộc P’- P hay có nghĩa là một luật sinh không thuộc văn phạm G. Điều này sinh ra mâu thuẫn. Vậy L(G) = L(G’).