CYK-algoritme

Het Cocke-Younger-Kasami (CYK)-algoritme (soms ook bekend als CKY) bepaalt of een string gegenereerd kan worden door een gegeven contextvrije grammatica en, als dit het geval is, levert het de manier waarop de string gegenereerd kan worden. Dit proces noemt men het parsen of ontleden van de string. Het algoritme is een voorbeeld van . De standaardversie van het CYK-algoritme herkent talen die gedefinieerd zijn door contextvrije grammatica's in Chomsky-normaalvorm. Aangezien elke contextvrije grammatica op eenvoudige wijze in deze normaalvorm om te zetten is, kan het CYK-algoritme gebruikt worden om alle contextvrije talen te herkennen. Het is eveneens mogelijk het CYK-algoritme uit te breiden zodat de gegeven contextvrije grammatica niet noodzakelijk in Chomsky-normaalvorm moet staan. Zo'n uitbreiding maakt het algoritme meer performant, maar ook moeilijker om de werking te begrijpen. In het slechtste geval is de asymptotische tijdscomplexiteit van het CYK-algoritme Θ(n3), waar n de lengte van de geparseerde string is. Dit maakt het een van de meest efficiënte algoritmes voor het herkennen van contextvrije talen qua tijdscomplexiteit. Er zijn echter wel andere algoritmes die nog beter presteren om bepaalde deelgroepen van de contextvrije talen te herkennen. Het algoritme is vernoemd naar John Cocke, en .