Context-free grammars (CFG) là tập hợp các quy tắc nhằm mô tả tất cả các chuỗi câu có thể hình thành trong một ngôn ngữ nhất định. Nói một cách khác, CFG mô tả quan điểm cho rằng các câu văn trong một ngôn ngữ bất kỳ đều được tạo ra bởi một tập hợp các quy tắc và các câu văn sai ngữ pháp không thể được tạo ra bởi tập hợp quy tắc này. Từ ‘Context Free’ có nghĩa là các từ trong câu được tạo ra không phụ thuộc vào ngữ cảnh và không có mối liên hệ với môi trường xung quanh.

Các quy tắc trong CFG được dùng để thiết lập sự ràng buộc giữa các symbols của CFG. Các symbols này được chia thành hai loại: terminal và non-terminal. Terminal là các symbols tương ứng với các từ vựng của ngôn ngữ còn non-terminal là các symbols được tạo thành từ các terminal (xem ví dụ bên dưới).

Ta xét một ví dụ về CFG với 10 quy tắc như sau:

 

S -> NP + VP

VP -> V +NP

NP -> DET + NP

NP -> N

NP -> ADJ + N

N -> ‘Tom’

N -> ‘boy’

V -> ‘is’

ADJ -> ‘pretty’

DET -> ‘a’

 

Trong ví dụ trên các từ ‘Tom’,‘boy’, ‘is’, ‘pretty’, ‘a’ là các terminal còn S (Sentence), NP (Noun Phrase), VP (Verb Phrase), V(Verb), DET(Determiner), N(Noun) và ADJ(Adjective) là các non-terminal. Lưu ý: bên phải mũi tên có thể là 1 hoặc nhiều terminal và non-terminal nhưng bên trái của mũi tên thì chỉ có thể có 1 non-terminal. Ngoài ra, các terminal chỉ có thể xuất hiện ở bên phải dấu mũi tên.

Với CFG như trên ta có thể tạo ra các câu đúng ngữ pháp là : ‘Tom is a boy” hoặc “Tom is a pretty boy” hoặc “Tom is pretty boy”, … Tuy nhiên các câu như “Tom pretty is”, “boy is a”, “pretty a boy”,… là các câu không đúng ngữ pháp và không thể được tạo ra từ CFG trên.

Các bạn lưu ý rằng “boy is Tom” cũng là một câu đúng ngữ pháp, phù hợp với CFG ở ví dụ trên nhưng câu này lại không đúng về mặt ngữ nghĩa. Qua đó ta thấy rằng CFG có thể tạo ra các câu đúng với cấu trúc cú pháp nhưng có thể không phù hợp về mặt ngữ nghĩa. Ngoài ra, độ chính xác của câu văn sẽ phụ thuộc vào mức độ phức tạp và độ hoàn chỉnh của CFG mà chúng ta định nghĩa.

Tháng Mười Hai 10, 2018
ITechSeeker