Content deleted Content added
Fixed matrix indices -- i is length (row), j is starting position (column) |
Solomon7968 (talk | contribs) m link, ce etc. |
||
Line 75:
|}
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<sub>k</sub> 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[7,1]'', the sentence can be generated by the grammar.
Line 92:
===Valiant's algorithm===
The [[Analysis of algorithms|worst case running time]] of CYK is <math>\Theta(n^3 \cdot |G|)</math>, where ''n'' is the length of the parsed string and ''|G|'' is the size of the CNF grammar ''G''. This makes it one of the most efficient algorithms for recognizing general context-free languages in practice. {{harvtxt|Valiant|1975}} gave an extension of the CYK algorithm. His algorithm computes the same parsing table
as the CYK algorithm; yet he showed that [[Matrix multiplication algorithm#Sub-cubic algorithms|algorithms for efficient multiplication]] of [[Boolean matrix|matrices with 0-1-entries]] can be utilized for performing this computation.
Line 108:
*{{cite techreport |last1=Kasami |first1=T. |authorlink1=Tadao Kasami |year=1965 |title=An efficient recognition and syntax-analysis algorithm for context-free languages |number=65-758 |publisher=[[Air Force Cambridge Research Laboratories|AFCRL]]}}
*{{cite journal |last1=Younger |first1=Daniel H. |date=February 1967 |title=Recognition and parsing of context-free languages in time ''n''<sup>3</sup> |journal=[[Information and Computation|Inform. Control]] |volume=10 |issue=2 |pages=189–208 |doi=10.1016/s0019-9958(67)80007-x}}
*{{cite book |last1=Knuth |first1=Donald E. |authorlink1=Donald Knuth |title=[[The Art of Computer Programming]] Volume 2: Seminumerical Algorithms |publisher=Addison-Wesley Professional |edition=3rd |date=November 14, 1997 |isbn=0-201-89684-2 |pages=501 }}
*{{cite journal |last1=Lange |first1=Martin |last2=Leiß |first2=Hans |title=To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm |year=2009 |journal=Informatica Didactica |volume=8 |url=http://www.informatica-didactica.de/cmsmadesimple/index.php?page=LangeLeiss2009}}
*{{cite book |last1=Sipser |first1=Michael |authorlink1=Michael Sipser |title=Introduction to the Theory of Computation |publisher=IPS |year=1997 |edition=1st |page=99 |isbn=0-534-94728-X}}
| |||