Pengertian
Algoritma CYK adalah algoritma parsing untuk tata bahasa bebas konteks (CFG) yang diterbitkan oleh Itiroo Sakai pada tahun 1961. Algoritma ini dinamai menurut beberapa penemunya: John Cocke, Daniel Younger, Tadao Kasami, dan Jacob T. Schwartz.
Algoritma CYK bekerja dengan cara membangun tabel yang berisi semua kemungkinan CFG yang dapat digunakan untuk menghasilkan string yang diberikan. Tabel ini dibangun secara bottom-up, mulai dari sel-sel paling bawah dan bergerak ke atas.
Prinsip Kerja
Algoritma CYK bekerja dengan cara berikut:
1. Buat tabel berukuran `n x n`, di mana `n` adalah panjang string yang diberikan.
2. Untuk setiap sel di tabel, mulai dari sel paling bawah dan bergerak ke atas:
* Jika sel berisi terminal, maka masukkan terminal tersebut ke dalam sel.
* Jika sel berisi non-terminal, maka periksa apakah ada aturan CFG yang menghasilkan non-terminal tersebut dari dua atau lebih terminal yang ada di sel-sel di bawahnya. Jika ada, masukkan non-terminal tersebut ke dalam sel.
3. Jika sel paling atas tabel berisi start symbol dari CFG, maka string yang diberikan adalah bagian dari bahasa yang dihasilkan oleh CFG. Jika tidak, maka string yang diberikan bukan bagian dari bahasa yang dihasilkan oleh CFG.
Keunggulan dan Kelemahan
* Algoritma CYK sangat efisien, terutama untuk CFG yang dalam bentuk Chomsky Normal Form (CNF).
* Algoritma CYK dapat digunakan untuk parsing string yang panjang.
* Algoritma CYK hanya dapat digunakan untuk CFG.
* Algoritma CYK tidak dapat digunakan untuk parsing string yang ambigu.
Aplikasi
Algoritma CYK digunakan dalam berbagai aplikasi, termasuk:
* Natural language processing
* Compiler construction
* Machine translation
* Speech recognition
Algoritma CYK adalah algoritma parsing yang powerful dan efisien untuk CFG. Algoritma ini digunakan dalam berbagai aplikasi, termasuk natural language processing, compiler construction, machine translation, dan speech recognition.
Apa Itu Algoritma Cyk dalam video berikut
0 Komentar