Wiki - KEONHACAI COPA

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


Tham khảo[sửa | sửa mã nguồn]

Wiki - Keonhacai copa chuyên cung cấp kiến thức thể thao, keonhacai tỷ lệ kèo, bóng đá, khoa học, kiến thức hằng ngày được chúng tôi cập nhật mỗi ngày mà bạn có thể tìm kiếm tại đây có nguồn bài viết: https://vi.wikipedia.org/wiki/Thu%E1%BA%ADt_to%C3%A1n_CYK