Talk:CYK algorithm

From Wikipedia, the free encyclopedia

anyone please help is there any proper algorithm to show that how the string is enabled . Example: given a string,the algortithm could give how it comes from the start S, show how many ways it can be ,or even give the shortest way.

---

It sounds like you're asking about parse trees... the page mentions that the algorithm is easy to modify to find a parse tree (or several). This would show you how to construct the string from the rules. I *think* that with Chomsky normal form, all derivations are the same length, but I'm not really an expert...

This page is great. However - it would incredible with a few examples to lead readers through the process.

[edit] Another article on CYK

There is another, almost empty article on the CYK parser: http://en.wikipedia.org/wiki/CYK_%28algorithm%29 The two should be merged (the former should be deleted.)

Done. Ceroklis 10:01, 26 September 2007 (UTC)

[edit] What does C stand for in CYK?

So far, I have come across three different names for letter C:

• Cook
• Cocke
• Coke

Which one is correct?

Cocke, according to the Jurafsky and Martin book. Ealdent 15:26, 23 October 2007 (UTC)

[edit] Mistake in the Algorithm?

I'm almost sure there is a mistake in the algorithm, but I'll write it here first just in case...
The line:
"Let the grammar contain r terminal and nonterminal symbols R1 ... Rr."
should be:
"Let the grammar contain r nonterminal symbols R1 ... Rr."
There is no need to consider the terminals also.
Sararkd (talk) 02:37, 18 January 2008 (UTC)