Giản lược và các văn phạm ngữ cảnh
Thường thì một văn phạm phi ngữ cảnh có thể còn chứa đựng một vài yếu tố thừa, vô ích. Chẳng hạn như theo các đặc tính trên, có những ký hiệu không thực sự tham gia vào quá trình dẫn xuất ra câu, hoặc sẽ có những luật sinh dạng A → B làm ...
Thường thì một văn phạm phi ngữ cảnh có thể còn chứa đựng một vài yếu tố thừa, vô ích. Chẳng hạn như theo các đặc tính trên, có những ký hiệu không thực sự tham gia vào quá trình dẫn xuất ra câu, hoặc sẽ có những luật sinh dạng A → B làm kéo dài chuỗi dẫn xuất một cách không cần thiết. Vì vậy, việc giản lược văn phạm phi ngữ cảnh là nhằm loại bỏ những yếu tố vô ích đó mà không làm giảm bớt khả năng sản sinh ngôn ngữ của văn phạm.
Nếu L là một CFL, nó có thể tạo ra văn phạm CFG với các đặc tính sau :
- Mỗi biến và mỗi ký hiệu kết thúc của G đều xuất hiện trong dẫn xuất của một số chuỗi trong L.
- Không có luật sinh nào dạng A → B, mà trong đó A, B đều là biến.
Hơn nữa, nếu ε ∉ L thì không cần luật sinh A → ε. Thực tế, nếu ε ∉ L, ta có mọi luật sinh trong G đều có một trong hai dạng :
A → BC hoặc A → aα (α là chuỗi các biến hoặc ε)
A → a
Hai dạng đặc biệt này gọi là dạng chuẩn Chomsky và dạng chuẩn Greibach.
Các ký hiệu vô ích
Một ký hiệu X gọi là có ích nếu có một dẫn xuất S ⇒* αXβ ⇒* w với các chuỗi α, β bất kỳ và w ∈ T *. Ngược lại X gọi là vô ích.
Vậy, có 2 đặc điểm cho ký hiệu có ích:
- X phải dẫn ra một chuỗi ký hiệu kết thúc.
- X phải nằm trong dẫn xuất từ S.
Tuy nhiên 2 dấu hiệu trên không đủ để đảm bảo X có ích vì X có thể nằm trong dạng câu chứa một biến nhưng từ đó không có ký hiệu kết thúc được sinh ra.
BỔ ĐỀ 1: (Dùng loại bỏ các biến không dẫn ra chuỗi ký hiệu kết thúc)
Cho CFG G (V, T, P, S) với L(G) ≠ ∅, có một CFG G’ (V’, T’, P’, S) tương đương sao cho mỗi A ∈ V’ tồn tại w ∈ T* để A ⇒* w.
Chứng minh
Mỗi biến A với luật sinh A → w trong P thì rõ ràng A ∈ V’. Nếu A → X1X2 ... Xn là một luật sinh, trong đó mỗi Xi hoặc là ký hiệu kết thúc hoặc là một biến đã có sẵn trong V’ thì một chuỗi các ký hiệu kết thúc có thể được dẫn ra từ A bằng dẫn xuất bắt đầu A ⇒ X1X2 ... Xn, vì vậy A ∈ V’. Tập V’ có thể tính được bằng cách lặp lại giải thuật trên. 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.
Giải thuật tìm V' như sau:
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 ⇒ X 1 X 2 ... X n ⇒ * w bằng k bước thì ta có thể viết w = w 1 w 2 ... w n , trong đó X i ⇒ * w i , 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 X i này được thêm vào V’. Khi X i 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
