Thuật toán CYK

CYK viết tắt của từ Cocke-Younger-Kasami, 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 phạm 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ụ: