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

Vậy văn phạm G2 không có ký hiệu vô ích nào.

Thí dụ 5.9 : Xét văn phạm có các luật sinh sau :

S ® AB | a

A ® a

Áp dụng bổ đề 1, ta thấy không có ký hiệu kết thúc được nào dẫn ra từ B nên ta loại bỏ B và luật sinh S  AB. Tiếp tục, áp dụng bổ đề 2 cho văn phạm :

S ® a

A ® a

Ta thấy chỉ có S xuất hiện trong dạng câu. Vậy ({S}, {a}, {S ® a}, S) là văn phạm tương đương với văn phạm đã cho và không có ký hiệu vô ích.

Câu hỏi :

?

Bạn hãy cho nhận xét về thứ tự áp dụng Bổ đề 1 và Bổ đề 2 trong quá trình loại bỏ các ký hiệu vô ích trong văn phạm ?

Luật sinh 

Một luật sinh có dạng A   gọi là luật sinh .

Ta xét đến việc loại bỏ các luật sinh này. Nếu   L(G) thì không thể loại được tất cả các luật sinh , nhưng nếu   L(G) thì có thể. Phương pháp loại bỏ dựa trên việc xác định liệu một biến A có dẫn xuất A *  hay không ? Nếu có, ta gọi A là biến rỗng (nullable). Ta có thể thay thế mỗi luật sinh B  X1X2 ... Xn bằng tất cả các luật sinh được định dạng bởi việc xóa bỏ tập hợp con các biến Xi rỗng, nhưng không bao gồm luật sinh B  , ngay cả khi tất cả các Xi đều là biến rỗng.

ĐỊNH LÝ 5.3 : Nếu L = L(G) với CFG G (V, T, P, S) thì L - {  } là L(G’) với CFG G’ không có ký hiệu vô ích và không có luật sinh .

Chứng minh

Ta có thể xác định tập hợp các biến rỗng (nullable) của G bằng giải thuật lặp như sau : Bắt đầu, nếu A   là một luật sinh thì A là biến rỗng. Kế tiếp, nếu B  , trong đó  gồm toàn các ký hiệu là các biến rỗng đã được tìm thấy trước đó thì B cũng là biến rỗng. Lặp lại cho đến khi không còn biến rỗng nào được tìm thấy nữa.

Tập luật sinh P’ được xây dựng như sau : Nếu A  X1X2 ... Xn là một luật sinh trong P thì ta thêm tất cả các luật sinh A  12 ... n vào P’ với điều kiện :

1) Nếu Xi không là biến rỗng thì i = Xi;

2) Nếu Xi là biến rỗng thì i là Xi hoặc ;

3) Không phải tất cả i đều bằng .

Đặt G’’ = (V, T, P’, S). Ta sẽ chứng minh rằng với mọi A  V và w  T *, A *G’’ w nếu và chỉ nếu w   và A *G w.

Nếu: Đặt A  iG w và w  , ta chứng minh quy nạp rằng A *G’’ w.

Nếu i = 1 ta có A  w là một luật sinh trong P, và vì w   nên luật sinh này cũng thuộc P’.

Giả sử kết quả đúng tới i - 1 (i>1)

Xét A G X1X2 ...Xn  i -1G w. Ta viết w = w1w2 ...wn sao cho j, Xj *wj.

Nếu wj   và Xj là biến thì theo giả thiết quy nạp, ta có Xj *G’’ wj (vì dẫn xuất Xj * wj có ít hơn i bước). Nếu wj =  thì Xj là biến rỗng, vậy A  12 ...n là một luật sinh trong P', trong đó j = Xj nếu wj   và j =  nếu wj = .

Vì w   nên không phải tất cả j là . Vậy, ta có dẫn xuất :

A Þ 12 ...n Þ* w12 ...n Þ* w1w23 ...n Þ* ... Þ* w1w2 ...wn = w trong G’’.

Chỉ nếu: Giả sử A  iG’’ w. Chắc chắn rằng w   vì G’’ không có luật sinh . Ta quy nạp theo i rằng A  G w.

Nếu i = 1: Ta thấy A  w là một luật sinh trong P’, do đó cũng phải có luật sinh A  w trong P sao cho bằng việc loại bỏ các ký hiệu rỗng trong , ta có w. Vậy, có tồn tại dẫn xuất A  G  Þ*G w, trong đó  Þ* w liên quan đến các dẫn xuất  từ các biến rỗng của  mà chúng ta đã loại bỏ khỏi w.

Giả sử kết quả đúng tới i - 1 (i>1)