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

Ta còn có G’ không có chứa luật sinh đơn vị (theo chứng minh trên) nên G cũng sẽ không chứa luật sinh đơn vị (do G  G’).

Việc áp dụng bổ đề 1, bổ đề 2 để loại các ký hiệu vô ích không đưa ra thêm luật sinh nào chứng tỏ G không chứa ký hiệu vô ích.

Vậy, kết quả ta được một văn phạm thỏa điều kiện định lý.

Thí dụ 5.11 : Loại bỏ các luật sinh đơn vị trong văn phạm sau :

E ® E + T | T

T ® T * F | F

F ® ( E ) | a

Gọi tập A = {B  A  * B}, xét các biến trong văn phạm, ta có :

 E = { E, T, F } T = { T, F } F = { F }

Vậy tập luật sinh mới, theo định lý sẽ chứa các luật sinh không là luật sinh đơn vị trong P, bổ sung thêm các luật sinh mới thay cho luật sinh đơn vị như sau :

E ® E + T | T * F | ( E ) | a

T ® T * F | ( E ) | a

F ® ( E ) | a

Chuẩn hóa văn phạm phi ngữ cảnh

Phần này sẽ giới thiệu hai định lý dùng chuẩn hóa CFG về một trong hai dạng chuẩn Chomsky và Greibach.

Dạng chuẩn chomsky - cnf (chomsky normal form)

ĐỊNH LÝ 5.5 : (Dạng chuẩn Chomsky, hay CNF )

Một ngôn ngữ phi ngữ cảnh bất kỳ không chứa  đều được sinh ra bằng một văn phạm nào đó mà các luật sinh có dạng A  BC hoặc A  a, với A, B, C là biến còn a là ký hiệu kết thúc.

Chứng minh

Đặt G là CFG sinh ra CFL không chứa . CFG tương đương có dạng chuẩn Chomsky có thể xây dựng từ G theo giải thuật sau :

Bước 1 : Thay thế tất cả các luật sinh có độ dài vế phải bằng 1 (luật sinh đơn vị dạng A  B, với A, B là biến )

Theo định lý 4.4, ta có thể tìm được CFG tương đương G1(V, T, P, S) không có luật sinh đơn vị và luật sinh . Vậy nếu luật sinh mà vế phải chỉ có một ký hiệu thì đó phải là ký hiệu kết thúc và luật sinh này là luật sinh có dạng đúng trong định lý.

Bước 2 : Thay thế các luật sinh có độ dài vế phải>1 và có chứa ký hiệu kết thúc.

Xét luật sinh trong P có dạng A  X1X2 ... Xm (m>1). Nếu Xi là ký hiệu kết thúc a thì ta đưa thêm một biến mới Ca và luật sinh mới Ca  a. Thay thế Xi bởi Ca, gọi tập các biến mới là V’ và tập luật sinh mới là P’.

Xét CFG G2 (V’, T, P’, S). Nếu   G1  thì  *G2 . Vậy L(G1)  L(G2). Ta chứng minh quy nạp theo số bước dẫn xuất rằng nếu A *G2 w, với A  V và w  T* thì A *G1 w.

Kết quả hiển nhiên với 1 bước dẫn xuất.

Giả sử kết quả đúng tới k bước dẫn xuất.

Xét A *G2 w bằng k +1 bước dẫn xuất.

Bước đầu tiên có dạng A  B1B2 ... Bm (m>1). Ta có thể viết w = w1w2 ...wm trong đó Bi *G2 wi, 1  i  m. Nếu Bi là ký hiệu kết thúc ai nào đó thì wi là ai. Theo cách xây dựng P’ ta có luật sinh A  X1X2 ... Xm của P trong đó Xi = Bi nếu Bi V và Xi = ai nếu Bi V’- V. Với Bi  V, ta đã biết rằng có dẫn xuất Bi *G1 wi bằng ít hơn k bước, do vậy theo giả thiết quy nạp Xi *G1 wi. Vậy A *G1 w.

Ta đã có kết quả là một CFL bất kỳ được sinh ra từ một CFG mà mỗi luật sinh có dạng A  a hoặc A  B1B2 ... Bm (m  2) với A, B1, ... ,Bm là các biến và a là ký hiệu kết thúc. Ta sửa G2 bằng cách thêm vào P’ một số luật sinh.

Bước 3 : Thay thế các luật sinh có độ dài vế phải>2 ký hiệu chưa kết thúc.

Xét luật sinh trong P’có dạng A  B1B2 ... Bm (m>2) . Ta thay bằng tập hợp các luật sinh : A  B1D1

D1 ® B2D2