CYK algorithm: Difference between revisions

Revision as of 10:00, 24 June 2015

Revision as of 18:36, 22 July 2015

Line 53:

\end{array}</math>

Now the sentence ''she eats a fish with a fork'' is analyzed using the CYK algorithm. In the following table, in <math>P[i,j,k]</math>, <math>i</math> is the number of the columnrow (starting at the leftbottom at 1), and <math>j</math> is the number of the row column (starting at the bottomleft at 1).

{| class="wikitable"

Line 76:

For readability, the CYK table for ''P'' is represented here as a 2-dimensional matrix ''M'' containing a set of non-terminal symbols, such that R_k is in ''M[i,j]'' if, and only if, ''P[i,j,k]''.

In the above example, since a start symbol ''S'' is in ''M[1,7,1]'', the sentence can be generated by the grammar.

==Extensions==