CYK algorithm: Difference between revisions

Revision as of 02:07, 16 November 2004

Revision as of 20:37, 17 December 2004

Line 1:

[[pl:Algorytm CYK]]

The '''Cocke-Younger-Kasami (CYK) algorithm''' determines whether a

[[string (computer science)|string]] can be generated by a given [[context-free grammar]] and, if so, how it can be generated. This is known as ''parsing'' the string. The algorithm is an example of [[dynamic programming]].

The standard version of CYK recognizes languages defined by context-free grammars written in [[Chomsky normal form]] (CNF). Since any context-free grammar can be converted to CNF without too much difficulty, CYK can be used to recognize any context-free language. It is also possible to extend the CYK algorithm to handle some context-free grammars which are not written in CNF; this may be done to improve performance, although at the cost of making the algorithm harder to understand.

Line 31 ⟶ 29:

It is also possible to extend the CYK algorithm to parse [[Stochastic context-free grammar]]s (SCFGs), where probabilities are stored in the table P instead of booleans.

[[pl:Algorytm CYK]]

[[Category:Parsing algorithms]]