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

...

Dm - 3 ® Bm - 2Dm - 2

Dm - 2 ® Bm - 1Bm

Đặt V’’ là tập các biến mới, P’’ là tập các luật sinh mới và văn phạm mới G3 (V’’, T, P’’, S). Ta có G3 chứa các luật sinh thoả mãn định lý.

Hơn nữa, nếu A *G2  thì A *G3 , vậy L(G2)  L(G3). Ngược lại cũng đúng tức là, L(G3)  L(G2). Chúng ta cũng đã có L(G2)  L(G1) và L(G1)  L(G2). Vậy G3 là văn phạm thoả mãn dạng chuẩn CNF.

Thí dụ 5.12 : Tìm văn phạm có dạng CNF tương đương văn phạm sau :

S ® A | ABA

A ® aA | a | B

B ® bB | b

Bước 1 : Thay thế các luật sinh có độ dài vế phải = 1 (luật sinh đơn vị)

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

 S = { S, A, B }

 A = { A, B}

 B = { B }

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 :

S ® aA | a | bB | b | ABA

A ® aA | a | bB | b

B ® bB | b

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.

Ta thấy, a và b đều xuất hiện ở vế phải một số luật sinh, do đó ta tạo thêm 2 biến mới Ca, Cb và 2 luật sinh mới Ca ® a và Cb ® b.

Văn phạm tương đương có tập luật sinh như sau :

S ® CaA | a | CbB | b | ABA

A ® CaA | a | CbB | b

B ® CbB | b

Ca ® a

Cb ® b

Bước 3 : Thay thế các luật sinh có độ dài vế phải>2

Chỉ còn duy nhất một luật sinh cần xét ở bước này : S ® ABA và tập luật sinh mới được thay thế có dạng như sau :

S ® CaA | a | CbB| b | AD1

A ® CaA | a | CbB| b

B ® CbB| b

Ca ® a

Cb ® b

D1 ® BA

Cuối cùng, ta sẽ thu được văn phạm có dạng chuẩn Chomsky như trên tương đương với văn phạm đã cho.

Dạng chuẩn greibach gnf (greibach normal form)

Ta gọi luật sinh với biến A ở bên trái là A - luật sinh.

BỔ ĐỀ 3 : (Dùng thay thế các luật sinh trực tiếp)

Cho G (V, T, P, S) là một CFG, đặt A ® 1B2 là luật sinh trong P và B ® 1 | 2 | ... | r là các B - luật sinh; văn phạm G1 (V, T, P1, S) thu được từ G bằng cách loại bỏ luật sinh A ® 1B2 và thêm vào luật sinh A ® 112 | 122 | ... | 1r2 thì L(G) = L(G1)

Chứng minh

. Hiển nhiên L(G1)  L(G) vì nếu A ® 1i2 được dùng trong dẫn xuất của G1 thì ta dùng A G 1B2 G 1i2

. Để chỉ ra L(G)  L(G1) ta cần chú ý rằng A ® 1B2 là luật sinh trong P - P1 (có trong G và không có trong G1). Bất cứ khi nào luật sinh A ® 1B2 được dùng trong dẫn xuất của G thì phải viết lại tại bước sau đó dùng luật sinh dạng B ® i. Hai bước dẫn xuất này có thể được thay thế bằng một bước dẫn xuất duy nhất, hay :

A ® 1B2A G1 1i2

B ® i

Vậy L(G) = L(G1)

BỔ ĐỀ 4 : (Dùng loại bỏ luật sinh dạng đệ quy trái trong văn phạm)

Đặt G (V, T, P, S) là CFG; A ® A1 | A2 | ... | Ar là tập các A - luật sinh có A là ký hiệu trái nhất của vế phải (luật sinh đệ quy trái). Đặt A ® 1 | 2 | ... | s là các A - luật sinh còn lại; G1 (V  {B}, T, P1, S) là CFG được tạo thành bằng cách thêm biến mới B vào V và thay các A - luật sinh bằng các luật sinh dạng:

1) A ® i

A ® i B với 1  i  s

2) B ® i

B ® i B với 1  i  r

thì L(G) = L(G1).

Chứng minh

Trong một chuỗi dẫn xuất trái, một chuỗi luật sinh dạng A ® Ai phải kết thúc bằng A ® j. Tức là: