CYK-algoritmen
Cocke-Younger-Kasami-algoritmen, vanligvis omtalt som CYK-algoritmen, er en algoritme som bestemmer hvorvidt en streng kan genereres av en gitt kontekstfri grammatikk og, i så fall, hvordan den kan genereres. Dette kalles å parse en streng. Algoritmen tar i bruk bottom–up-parsing og dynamisk programmering.
Standardversjonen av CYK-algoritmen opererer på kontekstfrie grammatikker gitt på Chomsky normalform (CNF), som en hvilken som helst konteksfri grammatikk kan omgjøres til.
CYK-algoritmen er viktig fordi den beviser at medlemskapsproblemet for kontekstfrie grammatikker er løsbart, og fordi den gjør det på en så effektiv måte. Uttrykt med stor O-notasjon er den lengste mulige kjøretida for CYK-algoritmen , hvor n er lengden av den parsa strengen og |G| størrelsen på CNF-grammatikken G.
Algoritmen ble oppdaga av de tre som den har fått navnet sitt etter, uavhengig av hverandre: Cocke og Schwartz i 1970, Younger i 1967 og Kasami i 1965.
Beskrivelse[rediger | rediger kilde]
Den opprinnelige CYK-algoritmen kan beskrives med følgende pseudokode:
La innputt være en streng S bestående av n tegn: a1 ... an.
La grammatikken inneholde r ikke-terminalsymboler R1 ... Rr.
Denne grammatikken inneholder delmengden Rs, som er mengden startsymboler.
La P[n,n,r] være en array av booleanske verdier. Sett alle elementenes P-verdi til false.
For hver i = 1 til n
For hver enhetsproduksjon Rj → ai, sett P[i,1,j] = true.
For hver i = 2 til n -- Spanlengden
For hver j = 1 til n-i+1 -- Spanstart
For hver k = 1 til i-1 -- Spanoppdeling
For hver produksjon RA → RB RC
Hvis P[j,k,B] og P[j+k,i-k,C] så sett P[j,i,A] = true
Hvis minst én av P[1,n,x] er true (x itereres over settet s, hvor s er alle indeksene for Rs)
Så er S medlem av språket
Ellers er S ikke medlem av språket