Redigerer CYK-algoritmen

'''Cocke-Younger-Kasami-algoritmen''', vanligvis omtalt som '''CYK-algoritmen''', er en [[algoritme]] som bestemmer hvorvidt en [[Streng (informatikk)|streng]] kan genereres av en gitt [[kontekstfri grammatikk]] og, i så fall, hvordan den kan genereres. Dette kalles å [[Parsing|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 <math>\Theta(n^3 \cdot |G|)</math>, 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==
Den opprinnelige CYK-algoritmen kan beskrives med følgende [[pseudokode]]:

 '''La''' innputt være en streng ''S'' bestående av ''n'' tegn: ''a''<sub>1</sub> ... ''a''<sub>''n''</sub>.
 '''La''' grammatikken inneholde ''r'' ikke-terminalsymboler ''R''<sub>1</sub> ... ''R''<sub>''r''</sub>.
 Denne grammatikken inneholder delmengden ''R''<sub>''s''</sub>, 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 ''R''<sub>''j''</sub> → ''a''<sub>''i''</sub>, '''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 ''R''<sub>''A''</sub> → ''R''<sub>''B''</sub> ''R''<sub>''C''</sub>
         '''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 ''R''<sub>''s''</sub>)
   '''Så''' er ''S'' medlem av språket
 '''Ellers''' er ''S'' ikke medlem av språket

==Eksterne lenker==
* [https://web.archive.org/web/20091019113531/http://homepages.uni-tuebingen.de/student/martin.lazarov/demos/cky.html CYK-parsing-demo i JavaScript] {{Språkikon|en|Engelsk}}
* [https://web.archive.org/web/20090401210244/http://www.informatik.uni-leipzig.de/alg/lehre/ss08/AUTO-SPRACHEN/Java-Applets/CYK-Algorithmus.html Interaktivt program fra Universitetet i Leipzig som demonstrerer CYK-algoritmen] {{Språkikon|de|Tysk}}
{{Autoritetsdata}}

[[Kategori:Algoritmer]]