CYK algorithm: Difference between revisions

Revision as of 00:38, 16 February 2015

Revision as of 00:06, 19 February 2015

Line 33:

===As prose===

In informal terms, this algorithm considers every possible subsequence of the sequence of words and sets <math>P[i,j,k]</math> to be true if the subsequence of words startingof fromlength <math>i</math> ofstarting lengthfrom <math>j</math> can be generated from <math>R_k</math>. Once it has considered subsequences of length 1, it goes on to subsequences of length 2, and so on. For subsequences of length 2 and greater, it considers every possible partition of the subsequence into two parts, and checks to see if there is some production <math>P \to Q \; R</math> such that <math>Q</math> matches the first part and <math>R</math> matches the second part. If so, it records <math>P</math> as matching the whole subsequence. Once this process is completed, the sentence is recognized by the grammar if the subsequence containing the entire sentence is matched by the start symbol.

==Example==