CYK-algoritmi
CYK-algoritmin (Cocke-Younger-Kasami -algoritmi) avulla voidaan selvittää kuuluuko jokin mielivaltainen merkkijono kieleen L. CYK-algoritmi toimii kieliopeille, jotka ovat Chomskyn normaalimuodossa.
Esimerkki
[muokkaa | muokkaa wikitekstiä]
Tarkastellaan esimerkiksi merkkijonoa "aabba" ja kielioppia
S → AQ
Q → RT | AT
T → BA | RR | BT
R → AB | TT | BT
A → a
B → b
CYK-algoritmi perustuu taulukointiin siten, että taulukon ensimmäiselle riville asetetaan merkkijono, jonka kuuluvuus johonkin kieleen halutaan selvittää. Taulukon toiselle riville laitetaan ne välikkeet, joista saadaan muodostettua yläpuolella olevat merkit. Jos esimerkiksi kirjaimen 'a' saisi muodostettua kahdella eri välikkeellä, tulisi molemmat merkitä taulukkoon, mutta tässä esimerkissä muodostus on yksikäsitteistä.
Kolmas rivi täytetään siten, että selvitetään millä välikkeillä voidaan muodostaa ylhäällä ja oikealla yläviistossa olevien välikkeiden yhdistelmä. Tässä esimerkiksi AA:ta ei voida muodostaa, joten rivin kolme ensimmäiseen sarakkeeseen tulee tyhjä joukko. AB ja BA ovat muodostettavissa ja niitä vastaavat välikkeet merkitään myös taulukkoon.
Neljännen rivin ensimmäinen sarake kuvaa sitä pystytäänkö merkkijono "aab" muodostamaan kieliopilla, toinen sarake kuvaa "abb":n kuuluvuutta kieleen jne. Tämä on selvitettävissä esimerkiksi siten, että kuljetaan taulukossa tutkittavasta ruudusta ylöspäin toiselle riville asti ja samalla yksi oikealle yläviistoon. Sitten tutkitaan voidaanko näistä ruuduista löytyvien välikkeiden mielivaltainen kombinaatio (kuitenkin niin, että taulukossa vasemmanpuoleinen välike luetaan ensin) muodostaa jollain toisella välikkeellä. Esimerkiksi tutkittaessa neljännen rivin kolmatta saraketta, katsotaan ensin toisen rivin kolmatta saraketta (B) ja kolmannen rivin neljättä saraketta (T). Näistä muodostuva BT on T:n ja R:n produktio, joten merkitään ruutuun T,R. Vielä pitää kuitenkin edetä ja tarkastella myös kolmannen rivin kolmatta saraketta ja toisen rivin viidettä saraketta (edetään alaspäin ja oikealle yläviistoon). Näistä löytyy tyhjä joukko sekä A, joten uusia välikemahdollisuuksia ei saada.
CYK-algoritmi etenee vastaavasti, kunnes päästään ensimmäisen sarakkeen viimeiselle riville. Jos kyseisessä ruudussa on S, kuuluu merkkijono kieleen L, eli se voidaan muodostaa annetulla kieliopilla lähtien lähtösymbolista. Muutoin merkkijono ei kuulu kieleen. Tarkasteltavien välikekombinaatioiden määrä kasvaa aina seuraavalle riville mentäessä yhdellä. Taulukon perusteella voimme myös päätellä helposti esimerkiksi sen, että merkkijonoa "aabb" ei voida muodostaa mitenkään kieliopin avulla ja merkkijono "abba" voitaisiin muodostaa, jos Q olisi lähtösymboli.