Thuật toán CYK
Bách khoa toàn thư mở Wikipedia
 |
Bài hoặc đoạn này cần được wiki hóa theo các quy cách định dạng và văn phong Wikipedia. Xin hãy giúp phát triển bài này bằng cách liên kết trong đến các mục từ thích hợp khác. |
CYK viết tắt của từ Cocke-Younger-Kasami.CYK là một thuật toán dùng để xác định xem một xâu có được tạo ra (hay đoán nhận) bởi một văn pham phi ngữ cảnh hay không (context-free grammar). Thuật toán này được sử dụng rất nhiều trong phân tích ngôn ngữ tự nhiên.
CYK là thuật toán bottom-up và chi phí là O(n³) trong trường hợp tồi nhất với n là độ dài xâu phân tích.
Giải thuật
Vào: Văn phạm G = ( N , T , S , P ) dạng chuẩn Chomsky, không chứa sản xuất trống, xâu vào w = a1a2 ... an € T+
Ra: Bảng phân tích T đối với w sao cho tij chứa A khi và chỉ khi
A →+ aiai+1 ... ai+j-1
Thuật toán
For i = 1 to n do ti1 = { A|A → ai € P }
For j = 2 to n do
For i = 1 to n – j +1 do
For k = 1 to j - 1 do
tij = { A| A → BC € P, B → tik và C → ti+k,j-k }
Nếu S € t1n thì w € L(G).
Ví dụ:
