Pengertian Algoritma CYK

Dalam ilmu komputer, algoritma Cocke–Younger–Kasami (atau disebut juga algoritma CYK, atau algoritma CKY) adalah algoritma penguraian untuk Context Free Grammar (CFG)/Tata Bahasa Bebas Konteks yang diterbitkan oleh Itiroo Sakai pada tahun 1961.

Algoritma CYK ini dinamai dengan beberapa penemunya, yaitu: John Cocke, Daniel Younger, Tadao Kasami, dan Jacob T. Schwartz. Algoritma CYK ini biasa digunakan dalam parsing bottom-up dan pemrograman dinamis.

Untuk dapat menggunakan algoritma CYK ini dibutuhkan CFG dalam bentuk normal form.

Context Free Grammar (CFG)

Context Free Grammar (CFG) atau Tata Bahasa Bebas Konteks adalah salah satu tata bahasa formal yang digunakan untuk spesifikasi sturuktur sintaks bahasa pemrograman serta basis beragam skemas spesifikasi translasi.

CFG menghasilkan bahasa yang dikenal oleh Non-Deterministic Push Down Automata.

Aturan produksi pada CFG, yaitu simbol sisi kiri hanya boleh memiliki 1 variabel non terminal (variabel) dan sisi kanan tidak memiliki batasan (bisa berisi ɛ, simbol terminal, simbol variabel, atau kombinasi ketiganya). Jika kita tuliskan maka aturan produksi dari Context Free Grammar adalah sebagai berikut:

• α → V
• β → (V + T)*

Contoh Penggunaan Algoritma CYK untuk membuktikan inputan/string \’aaab\’ pada CFG di bawah ini.

• S → AB | b
• A → BA | a
• B → AS | b

Langkah Pertama

Membagi baris sebanyak jumlah simbol terminal penyusun inputan. Karena inputan \’aaab\’ mengandung 4 simbol terminal maka akan ada 4 baris yang dibuat. Baris pertama untuk a, baris kedua untuk a, baris ketiga untuk a, dan baris keempat untuk b.

Langkah Kedua

Membuat pola tabel kosong sesuai dengan jumlah barisnya. Artinya apabila ada 4 baris maka tabelnya adalah 5 x 5.

Langkah Ketiga

Membuat baris pertama yang nantinya kita lambangkan dengan V_ij.

Catatan penting: i merujuk sebagai kolom, sedangkan j merujuk sebagai baris. Jadi, misalnya V₂₁ disebut sebagai kolom 2, baris 1.

Cara membuat baris pertama adalah dengan mencocokan keberadaan setiap simbol terminal pada inputan/string dengan aturan produksi CFG.

Misalnya, untuk terminal a terdapat dalam produksi A → BA | a. Maka himpuan V₁₁ (kolom 1, baris 1) adalah A. Selanjutnya pun juga begitu, dan jika dutuliskan maka baris pertama adalah:

• V₁₁ = {A} -> a terdapat dalam A → BA | a
• V₂₁ = {A} -> a terdapat dalam A → BA | a
• V₃₁ = {A} -> a terdapat dalam A → BA | a
• V₄₁ = {S, B} -> b terdapat dalam S → AB | b dan B → AS | b

Tabel setelah kita ketahui baris pertama.

Langkah Keempat

Membuat baris kedua dengan rumus | V_ik – V_{i+k, j-k} | (k=1).

• V₁₂ = V_ik – V_i+k, _j-k
• V₁₂ = V₁₁ – V_{1+1, 2-1}
• V₁₂ = V₁₁ – V₂₁

Karena sesuai dengan baris pertama, V₁₁ adalah A dan V₂₁ juga adlaah A maka:

• V₁₂ = A – A -> A – A menghasilkan AA
• V₁₂ = AA

Selanjutnya kita cocokan kembali apakah AA terdapat dalam aturan produksi. Karena tidak ada simbol variabel dalam aturan produksi yang menghasilkan AA maka:

• V₁₂ = Ø

Untuk kolom-kolom selanjutnya juga diberlakukan operasi yang sama.

• V₂₂ = V₂₁ – V₃₁
• V₂₂ = A – A
• V₂₂ = AA
• V₂₂ = Ø

• V₃₂ = V₃₁ – V₄₁
• V₃₂ = A – S, B
• V₃₂ = AS, AB

Karena AS dan AB merupakan hasil dari aruran produksi B dan S maka:

• V₃₂ = {S, B}

Untuk V₄₂ kita tiadakan karena V₄₁ – V₅₁ (tidak ada).

Tabel setelah kita ketahui baris kedua.

Langkah Kelima

Membuat baris ketiga dengan rumus | V_ik – V_{i+k, j-k} | (k=1, 2).

• V₁₃ = V₁₁ – V_{1+1, 3-1} & V₁₂ – V_{1+2, 3-2}
• V₁₃ = V₁₁ – V₂₂ & V₁₂ – V₃₁
• V₁₃ = A –  Ø & Ø – A
• V₁₃ = Ø

• V₂₃ = V₂₁ – V₃₂ & V₂₂ – V₄₁
• V₂₃ = A – S, B & Ø – S, B
• V₂₃ = AS, AB
• V₂₃ = {S, B}

Tabel setelah kita ketahui baris ketiga:

Langkah Keenam

Membuat baris keempat dengan rumus | V_ik – V_{i+k, j-k} | (k=1, 2, 3).

• V₁₄ = V₁₁ – V₂₃ & V₁₂ – V₃₂ & V₁₃ – V₄₁
• V₁₄ = A – S, B & Ø – S, B & Ø – S, B
• V₁₄ = AS, AB
• V₁₄ = {S, B}

Tabel setelah kita ketahui baris keempat:

Langkah Ketujuh

Memastikan apabila simbol awal (S) ada pada V_1n . Karena tabel akhir memuat simbol S pada baris terakhirnya maka menurut algoritma CYK, ‘aaab’ terbukti dapat diturunkan.

HASIL AKHIR: