Xem mã nguồn của Thuật toán CYK

{{Dead end|date=tháng 7 2018}}

{{chú thích trong bài}}

{{wikify}}   
'''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ụ:

<!--Hình thiếu thông tin về bản quyền [[Hình:CYK.jpg]] -->

==Tham khảo==
{{tham khảo}}
{{sơ khai}}

[[Thể loại:Thuật toán]]