Algoritmul Cocke -Younger- Kasami , algoritmul CYK sau CKY , este un algoritm care vă permite să determinați dacă este posibil să afișați un anumit șir într-o anumită gramatică fără context și, dacă da, să furnizați rezultatul acestuia. Cu alte cuvinte, este un algoritm de analiză a șirurilor . Algoritmul implementează analiza de jos în sus și se bazează pe metoda de programare dinamică . descoperitorii săi: John Cock, Daniel Younger, Tadao Kasami și Jacob T. Schwartz. Au folosit analiza de jos în sus și programare dinamică.
Versiunea standard a CYK funcționează numai cu gramatici fără context date în formă normală (CNF). Cu toate acestea, orice gramatică fără context poate fi convertită (după conversie) într-o gramatică CNF care exprimă aceeași limbă ( Sipser 1997 ).
Este unul dintre cei mai eficienți algoritmi de analiză în ceea ce privește complexitatea asimptotică în cel mai rău caz , deși există și alți algoritmi cu timpi medii de execuție mai buni în multe scenarii practice [1] .
Algoritmul funcționează astfel: la primul pas, se scrie un cuvânt pe prima linie și fiecare caracter neterminal este adăugat la linie, sub care sunt afișate caracterele terminale. După aceea, pentru fiecare celulă din grilă, este necesar să mergeți vertical de sus în jos la celula bifată, iar a doua celulă în sus în diagonală. Pentru fiecare astfel de pas, celulele sunt combinate și verificate pentru a găsi combinația în gramatică. Dacă este găsit, non-terminalul din stânga este adăugat la celula grilei. Dacă după toți pașii, caracterul inițial este conținut în ultima linie, cuvântul poate fi obținut din gramatica dată [2] .
Algoritmul de programare dinamică necesită ca gramatica fără context să fie convertită în Chomsky Normal Form (CNF) deoarece verifică dacă secvența curentă poate fi împărțită în două secvențe mai mici. Orice gramatică fără context care nu produce un șir gol poate fi reprezentată în CNF folosind regulile de producție [3] .
În pseudocod , algoritmul arată astfel:
Algoritmul CYK: dat un șir S de n caractere: a 1 ... a n . dată o gramatică care conţine r simboluri neterminale R 1 ... R r . Conține un subset R s de caractere inițiale. def tablou P [ n , n , r ] de valori booleene inițializate la False. pentru fiecare i = 1 : n pentru fiecare producție R j -> a i atribuiți P [ 1 , i , j ] = Adevărat pentru fiecare i = 2 : n este lungimea intervalului pentru fiecare j = 1 : n - i +1 - - începutul intervalului pentru fiecare k = 1 : i -1 este împărțirea intervalului pentru fiecare producție R A -> R B R C dacă P [ k , j , B ] și P [ i - k , j + k , C ] apoi atribuiți P [ i , j , A ] = Adevărat dacă pentru unele x din mulțimea s P [n, 1 , x ] = Adevărat, unde s sunt toți indici ai lui R s, atunci returnarea S aparține limbajului altfel return S nu aparține limbii| Limbi formale și gramatici formale | |
|---|---|
| Concepte generale | |
| Tip 0 | |
| Tipul 1 |
|
| Tipul 2 | |
| Tip 3 | |
| analizare | |