CYKalgoritmus

The CYK algorithm, named after its creators John Cocke, Daniel Younger, and Tadao Kasami, is a parsing algorithm used in computer science to determine if a given string can be generated by a specific context-free grammar. It is a dynamic programming algorithm that works by filling a table of possible grammatical constituents for all substrings of the input string. The algorithm is particularly efficient for grammars that are in Chomsky normal form, a standardized form of context-free grammars where each production rule is either of the form A -> BC or A -> a, where A, B, and C are non-terminal symbols and 'a' is a terminal symbol.

The CYK algorithm constructs a table where rows represent the length of substrings and columns represent the starting position of substrings. For a string of length n, the table will have dimensions n x n. The algorithm begins by filling the bottom row of the table with the direct productions of the terminals in the input string. Then, it iteratively builds up the table by considering longer and longer substrings. For each substring, it checks if any non-terminal symbol can derive that substring based on the grammar rules and the already computed entries in the table. 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 considered to be in the language generated by that grammar. Otherwise, the string is not in the language. The time complexity of the CYK algorithm for a grammar in Chomsky normal form is O(n^3 * |G|), where n is the length of the input string and |G| is the size of the grammar.