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

Thí dụ 5.7 : Xét cây dẫn xuất ở Hình 5.1

. Dẫn xuất trái nhất của cây :

S Þ aAS Þ aSbAS Þ aabAS Þ aabbaS Þ aabbaa.

. Dẫn xuất phải nhất tương ứng là :

S Þ aAS Þ aAa Þ aSbAa Þ aSbbaa Þ aabbaa.

Văn phạm mơ hồ

Một văn phạm phi ngữ cảnh G có nhiều hơn một cây dẫn xuất cho cùng một chuỗi w, thì G được gọi là văn phạm mơ hồ (ambiguity). Dĩ nhiên, cũng có thể nói rằng văn phạm G là mơ hồ nếu có một chuỗi w được dẫn ra từ ký hiệu bắt đầu S với hai dẫn xuất trái hoặc hai dẫn xuất phải.

Thí dụ 5.8 : Xét văn phạm G với các luật sinh như sau :

E  E + E  E * E  ( E )  a

Văn phạm này sinh ra các chuỗi biểu thức số học với 2 phép toán + và * . Với chuỗi a + a * a, ta có thể vẽ đến hai cây dẫn xuất khác nhau như sau :

(a) (b)

Hình 5.4 - Các cây dẫn xuất khác nhau cho cùng chuỗi nhập

Điều này có nghĩa là biểu thức a + a * a có thể hiểu theo hai cách khác nhau: thực hiện phép cộng trước hay phép nhân trước ? Để khắc phục sự mơ hồ này, ta có thể :

- Hoặc quy định rằng các phép cộng và nhân luôn luôn được thực hiện theo thứ tự từ trái sang phải (trừ khi gặp ngoặc đơn). Ta viết văn phạm G1 không mơ hồ tương đương như sau :

E  E + T  E * T  T

T  ( E )  a

- Hoặc quy định rằng khi không có dấu ngoặc đơn ngăn cách thì phép nhân luôn luôn được ưu tiên hơn phép cộng. Ta viết văn phạm G2 không mơ hồ tương đương như sau :

E  E + T  T

T  T * F  F

F  ( E )  a

Giản lược các văn phạm phi 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 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 :

1. 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.
2. 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.