CYKalgoritmen

The CYK algorithm, named after its discoverers John Cocke, Daniel Younger, and Tadao Kasami, is a dynamic programming algorithm used for parsing strings of a given context-free grammar. Specifically, it determines if a given string can be generated by a context-free grammar that is in Chomsky normal form. Chomsky normal form requires that all production rules are of the form A -> BC or A -> a, where A, B, and C are non-terminal symbols and 'a' is a terminal symbol.

The algorithm works by filling a triangular table, typically denoted as a 2D array, where the rows represent the length of substrings and the columns represent the starting position of those substrings. The table cell P[i, j] stores the set of non-terminal symbols that can generate the substring of length 'i' starting at position 'j'. The algorithm proceeds in a bottom-up manner. For substrings of length 1, it checks if any production rule directly derives the terminal symbol. For longer substrings, it considers all possible splits into two smaller substrings and checks if any production rule A -> BC can derive the current substring, where B derives the first part and C derives the second part.

If the top-right cell of the table, corresponding to the entire input string, contains the start symbol of the grammar, then the string is derivable from the grammar. Otherwise, it is not. The CYK algorithm has a time complexity of O(n^3 * |G|), where 'n' is the length of the input string and |G| is the size of the grammar. This makes it suitable for relatively short strings or grammars. It is a key algorithm in theoretical computer science and compiler design for parsing and analyzing context-free languages.