Die Wikipedia Artikel zum Cocke-Younger-Kasami-Algorithmu kann man vergessen. Man kapiert nichts. Hab auf youtube ein 15min Video [1] von Benny Neugebauer dazu gefunden. Wunderbar, alles gleich verstanden :)
\nHab ihn mal schnell in C++ implementiert. Hier die Hauptschleife:<\/p>\n
\r\n \/*\r\n F\u00fcr j = 2 ... n\r\n F\u00fcr i = 1 ... n - j + 1\r\n F\u00fcr k = 1 ... j - 1\r\n Setze V_{i,j} := V_{i,j} + { l | \\exists B,C in N ((l -> BC) in P and B in V_{i,k} and C in V_{i + k, j - k}) \\}\r\n\r\n Falls S \\in V_{1,n}, stoppe und gib \"w wird von G erzeugt\" aus\r\n Stoppe und gib \"w wird nicht von G erzeugt\" aus\r\n *\/\r\n for(size_t row=1; row < n; row++) {\r\n\/\/ cout << \"row \" << row << \"\\n\";\r\n for(size_t col=0; col < n-row; col++) {\r\n\/\/ cout << \"col \" << col << \"\\n\";\r\n for(size_t k=0; k < row; k++) {\r\n const auto &e1 = V.at(k, col);\r\n const auto &e2 = V.at(row-k-1, col+k+1);\r\n\r\n for(size_t i=0; i < e1.size(); i++) {\r\n for(size_t j=0; j < e2.size(); j++) {\r\n\/\/ cout << \"Check \" << e1.at(i) << \" \" << e2.at(j) << \"\\n\";\r\n const Production::String toTest({e1.at(i), e2.at(j)});\r\n for(const Production& p : P) {\r\n if(p.right == toTest) {\r\n \/\/ uniq append\r\n if(contains(V.at(row, col), p.left) == false) {\r\n V.at(row, col).push_back(p.left);\r\n }\r\n }\r\n }\r\n }\r\n }\r\n }\r\n }\r\n }\r\n<\/code><\/pre>\nF\u00fcr jeden Matrixeintrag in der oberen linken Dreiecksmatrix:
\nF\u00fcr jeden Eintrag oberhalt in der Spalte und Diagonal nach oben:
\nSchaue nach ob die Konkatenation der beiden Eintr\u00e4ge in der rechten Seite der Produktionsregeln vorkommen:
\nJa) Linke Seite der Produktion in die Matrix eintragen.<\/p>\n
Steht am Ende in der letzten Zeile, erste Spalte das Startsymbol, dann kann das Wort erkannt werden.<\/p>\n