A Cocke -Younger- Kasami algoritmus , a CYK vagy CKY algoritmus egy olyan algoritmus , amely lehetővé teszi annak meghatározását, hogy lehetséges-e egy adott karakterlánc megjelenítése egy adott környezetfüggetlen nyelvtanban , és ha igen, akkor adja meg a kimenetét. Más szavakkal, ez egy karakterlánc- elemző algoritmus . Az algoritmus alulról felfelé irányuló elemzést valósít meg, és a dinamikus programozási módszeren alapul . felfedezői: John Cock, Daniel Younger, Tadao Kasami és Jacob T. Schwartz. Alulról építkező elemzést és dinamikus programozást alkalmaztak.
A CYK szabványos verziója csak a normál formában (CNF) megadott környezetfüggetlen nyelvtanokkal működik. Azonban bármilyen környezetfüggetlen nyelvtan átalakítható (konverzió után) ugyanazt a nyelvet kifejező CNF nyelvtanná ( Sipser 1997 ).
Ez az egyik leghatékonyabb elemző algoritmus a legrosszabb eset aszimptotikus összetettsége szempontjából , bár sok gyakorlati forgatókönyvben vannak más algoritmusok is, amelyek jobb átlagos végrehajtási idővel rendelkeznek [1] .
Az algoritmus a következőképpen működik: az első lépésben egy szót írunk az első sorba, és minden nem terminális karaktert hozzáadunk ahhoz a sorhoz, amely alatt a terminál karakterek megjelennek. Ezt követően a rács minden egyes cellájánál függőlegesen felülről lefelé kell menni a bejelölt cellához, a második cellát pedig átlósan felfelé. Minden ilyen lépésnél a cellákat egyesítik és ellenőrzik, hogy megtalálják a kombinációt a nyelvtanban. Ha megtalálja, a bal oldali nem terminál hozzáadódik a rácscellához. Ha minden lépés után az utolsó sorban van a kezdőkarakter, akkor a szó az adott nyelvtanból nyerhető [2] .
A dinamikus programozási algoritmus megköveteli, hogy a kontextusmentes nyelvtant Chomsky Normal Form-má (CNF) kell konvertálni, mert ellenőrzi, hogy az aktuális sorozat felosztható -e két kisebb sorozatra. Minden olyan környezetfüggetlen nyelvtan, amely nem állít elő üres karakterláncot, leképezhető a CNF-ben termelési szabályok segítségével [3] .
A pszeudokódban az algoritmus így néz ki:
CYK algoritmus: adott egy n karakterből álló S karakterlánc : a 1 ... a n . adott egy r nem terminális szimbólumot tartalmazó nyelvtan R 1 ... R r .A kezdeti karakterek R részhalmazát tartalmazza . def tömb P [ n , n , r ] logikai értékek hamisra inicializálva. minden i = 1 esetén: n minden produkcióhoz R j -> a i hozzárendeli P [ 1 , i , j ] = igaz minden i = 2 esetén : n az intervallum hossza minden j = 1 esetén : n - i +1 - - az intervallum eleje minden k = 1 esetén: i -1 az intervallum partíciója minden egyes produkcióhoz R A -> R B R C , ha P [ k , j , B ] és P [ i - k , j + k , C ] , majd hozzárendeljük P [ i , j , A ] = igaz , ha az s halmazból néhány x esetén P [n, 1 , x ] = Igaz, ahol s az R s összes indexe , akkor S visszatérés a nyelvhez tartozik különben visszatér S nem tartozik a nyelvhez| Formális nyelvek és formális nyelvtanok | |
|---|---|
| Általános fogalmak | |
| Típus 0 | |
| 1. típus |
|
| 2. típus | |
| 3. típus |
|
| elemzése | |