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ụ: