"O algoritmo Cocke-Younger-Kasami (CYK) determina se uma cadeia de caracteres pode ser gerada por uma determinada gram\u00E1tica livre de contexto e, se ela puder, como ela pode ser gerada. Esse processo \u00E9 conhecido como a an\u00E1lise sint\u00E1tica da cadeia, no caso, ascendente. A vers\u00E3o padr\u00E3o do algoritmo opera em gram\u00E1ticas livres de contexto expressas atrav\u00E9s da Forma Normal de Chomsky (CNF). No pior caso, o algoritmo possui complexidade , em que \u00E9 o comprimento da cadeia de caracteres e o tamanho da gram\u00E1tica CNF . Isso o torna um dos algoritmos mais eficientes no reconhecimento geral de linguagens livres de contexto. Entretanto, algoritmos mais r\u00E1pidos e especializados existem para certos subconjuntos de linguagens livres de contexto."@pt . . . . "El algoritmo de Cocke-Younger-Kasami (CYK) determina si una cadena puede ser generada por una gram\u00E1tica libre de contexto y, si es posible, c\u00F3mo puede ser generada. Este proceso es conocido como an\u00E1lisis sint\u00E1ctico de la cadena. El algoritmo es un ejemplo de programaci\u00F3n din\u00E1mica. La versi\u00F3n est\u00E1ndar de CYK reconoce lenguajes definidos por una gram\u00E1tica libre de contexto escrita en la forma normal de Chomsky (CNF). Cualquier gram\u00E1tica libre de contexto puede ser convertida a CNF sin mucha dificultad, CYK puede usarse para reconocer cualquier lenguaje libre de contexto. Es posible extender el algoritmo CYK para que trabaje sobre algunas gram\u00E1ticas libre de contexto no escritas como CNF. Esto puede hacerse para mejorar la ejecuci\u00F3n, aunque hace el algoritmo m\u00E1s dif\u00EDcil de entender. En el peor caso asint\u00F3tico la complejidad temporal de CYK es de \u0398(n3), donde n es la longitud de la cadena analizada. Esto hace a este algoritmo uno de los m\u00E1s eficientes (en estos t\u00E9rminos) en el reconocimiento de los lenguajes libres de contexto. Sin embargo, existen otros algoritmos con un mejor funcionamiento para ciertos subconjuntos de los lenguajes libres de contexto."@es . . "Algoritmo CYK"@pt . "CYK\u7B97\u6CD5"@zh . "Der Cocke-Younger-Kasami-Algorithmus (CYK-Algorithmus) ist ein Algorithmus aus dem Gebiet der theoretischen Informatik. Mit ihm l\u00E4sst sich feststellen, ob ein Wort zu einer bestimmten kontextfreien Sprache geh\u00F6rt. In der Fachsprache bezeichnet man dies als L\u00F6sen des Wortproblems f\u00FCr kontextfreie Sprachen. Mit Hilfe von Backtracking kann der Parse-Tree bzw. die Parse-Trees eines gegebenen Wortes der Sprache konstruiert werden. Um den Algorithmus anzuwenden, muss zu der vorgegebenen Sprache eine Grammatik in Chomsky-Normalform vorliegen. Der in den 1960er Jahren von , John Cocke, Tadao Kasami, Jacob Schwartz und unabh\u00E4ngig voneinander entwickelte Algorithmus nutzt das Prinzip der dynamischen Programmierung."@de . "1113022326"^^ . . . . . . . . "Cocke-Younger-Kasami-Algorithmus"@de . "CYK\u6CD5\uFF08\u82F1: CYK algorithm\uFF09\u306F\u3001\u3042\u308B\u6587\u5B57\u5217\u304C\u4E0E\u3048\u3089\u308C\u305F\u6587\u8108\u81EA\u7531\u6587\u6CD5\u3067\u751F\u6210\u3067\u304D\u308B\u304B\u3092\u6C7A\u3081\u3001\u751F\u6210\u3067\u304D\u308B\u5834\u5408\u306E\u751F\u6210\u65B9\u6CD5\u3092\u6C42\u3081\u308B\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u3067\u3042\u308B\u3002CYK \u306F Cocke-Younger-Kasami \u306E\u7565\uFF08\u305D\u308C\u305E\u308C\u3001RISC\u306E\u5148\u99C6\u3068\u8A00\u308F\u308C\u308B801\u306A\u3069\u3067\u3082\u77E5\u3089\u308C\u308B\u30B8\u30E7\u30F3\u30FB\u30B3\u30C3\u30AF\u3001Daniel Younger\u3001\u5D69\u5FE0\u96C4\u3067\u3042\u308B\uFF09\u3002\u6587\u8108\u81EA\u7531\u6587\u6CD5\u306E\u69CB\u6587\u89E3\u6790\u624B\u6CD5\u3068\u6349\u3048\u308B\u3053\u3068\u3082\u3067\u304D\u308B\u3002\u3053\u306E\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u306F\u4E00\u7A2E\u306E\u52D5\u7684\u8A08\u753B\u6CD5\u3067\u3042\u308B\u3002 \u6A19\u6E96\u7684\u306ACYK\u6CD5\u306F\u3001\u30C1\u30E7\u30E0\u30B9\u30AD\u30FC\u6A19\u6E96\u5F62\u3067\u66F8\u304B\u308C\u305F\u6587\u8108\u81EA\u7531\u6587\u6CD5\u3067\u5B9A\u7FA9\u3055\u308C\u308B\u8A00\u8A9E\u3092\u8A8D\u8B58\u3059\u308B\u3002\u4EFB\u610F\u306E\u6587\u8108\u81EA\u7531\u6587\u6CD5\u3092\u30C1\u30E7\u30E0\u30B9\u30AD\u30FC\u6A19\u6E96\u5F62\u306B\u66F8\u304D\u63DB\u3048\u308B\u306E\u306F\u305D\u308C\u307B\u3069\u56F0\u96E3\u3067\u306F\u306A\u3044\u306E\u3067\u3001CYK\u6CD5\u306F\u4EFB\u610F\u306E\u6587\u8108\u81EA\u7531\u6587\u6CD5\u306E\u8A8D\u8B58\u306B\u4F7F\u3046\u3053\u3068\u304C\u3067\u304D\u308B\u3002CYK\u6CD5\u3092\u62E1\u5F35\u3057\u3066\u30C1\u30E7\u30E0\u30B9\u30AD\u30FC\u6A19\u6E96\u5F62\u3067\u66F8\u304B\u308C\u3066\u3044\u306A\u3044\u6587\u8108\u81EA\u7531\u6587\u6CD5\u3092\u6271\u3046\u3088\u3046\u306B\u3059\u308B\u3053\u3068\u3082\u53EF\u80FD\u3067\u3042\u308B\u3002\u3053\u308C\u306B\u3088\u308A\u6027\u80FD\u306F\u5411\u4E0A\u3059\u308B\u304C\u3001\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u3092\u7406\u89E3\u3059\u308B\u3053\u3068\u306F\u96E3\u3057\u304F\u306A\u308B\u3002 CYK\u6CD5\u306E\u6700\u60AA\u6642\u9593\u8A08\u7B97\u91CF\u306F \u0398(n3) \u3067\u3042\u308A\u3001n \u306F\u89E3\u6790\u5BFE\u8C61\u306E\u6587\u5B57\u5217\u306E\u9577\u3055\u3067\u3042\u308B\u3002\u5F93\u3063\u3066\u3001CYK\u6CD5\u306F\u4EFB\u610F\u306E\u6587\u8108\u81EA\u7531\u8A00\u8A9E\u3092\u8A8D\u8B58\u3067\u304D\u308B\u6700\u3082\u52B9\u7387\u7684\u306A\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u306E1\u3064\u3067\u3042\u308B\u3002\u305F\u3060\u3057\u3001\u6587\u8108\u81EA\u7531\u8A00\u8A9E\u306E\u7279\u5B9A\u306E\u30B5\u30D6\u30BB\u30C3\u30C8\u306B\u3064\u3044\u3066\u3001\u3088\u308A\u52B9\u7387\u306E\u826F\u3044\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u304C\u4ED6\u306B\u5B58\u5728\u3059\u308B\u3002"@ja . "Algoritmo CYK"@es . . "CYK-algoritme"@nl . . . "Algorytm CYK (Cocke\u2019a-Youngera-Kasamiego) \u2013 dynamiczny algorytm sprawdzaj\u0105cy, czy s\u0142owo nale\u017Cy do j\u0119zyka bezkontekstowego. J\u0119zyk bezkontekstowy musi by\u0107 przedstawiony w postaci normalnej Chomsky\u2019ego. Algorytm dzia\u0142a w czasie gdzie jest d\u0142ugo\u015Bci\u0105 s\u0142owa, a jest rozmiarem gramatyki."@pl . . . "CYK\u6CD5"@ja . "CYK\u7B97\u6CD5\uFF08\u82F1\u8A9E\uFF1ACocke\u2013Younger\u2013Kasami algorithm\uFF0C\u7E2E\u5BEB\u70BACYK algorithm\uFF09\u662F\u7531\u7D04\u7FF0\u00B7\u79D1\u514B\uFF0CYounger\u548C\u5171\u540C\u7814\u7A76\u51FA\u6765\u5927\u7EA6\u53D1\u8868\u4E8E1965\u5E74\u7684\u4E00\u4E2A\u7B97\u6CD5\uFF0C\u5B83\u662F\u4E00\u4E2A\u7528\u6765\u5224\u5B9A\u4EFB\u610F\u7ED9\u5B9A\u7684\u5B57\u7B26\u4E32 \u662F\u5426\u5C5E\u4E8E\u4E00\u4E2A\u4E0A\u4E0B\u6587\u65E0\u5173\u6587\u6CD5\u7684\u7B97\u6CD5\u3002\u666E\u901A\u7684\u56DE\u6EAF\u6CD5\uFF08backtracking\uFF09\u5728\u6700\u574F\u7684\u60C5\u51B5\u4E0B\u9700\u8981\u6307\u6570\u65F6\u95F4\u624D\u80FD\u89E3\u51B3\u8FD9\u6837\u7684\u95EE\u9898\uFF0C\u800CCYK\u7B97\u6CD5\u53EA\u9700\u8981\u591A\u9879\u5F0F\u65F6\u95F4\u5C31\u591F\u4E86\uFF08 \uFF0C n \u4E3A\u5B57\u7B26\u4E32 w \u7684\u957F\u5EA6\uFF09\u3002CYK\u7B97\u6CD5\u91C7\u7528\u4E86\u52A8\u6001\u89C4\u5212\u7684\u601D\u60F3\u3002 \u5BF9\u4E8E\u4E00\u4E2A\u4EFB\u610F\u7ED9\u5B9A\u7684\u4E0A\u4E0B\u6587\u65E0\u5173\u6587\u6CD5\uFF0C\u90FD\u53EF\u4EE5\u4F7F\u7528CYK\u7B97\u6CD5\u6765\u8BA1\u7B97\u4E0A\u8FF0\u95EE\u9898\uFF0C\u4F46\u9996\u5148\u8981\u5C06\u8BE5\u6587\u6CD5\u8F6C\u6362\u6210\u4E54\u59C6\u65AF\u57FA\u8303\u5F0F\u3002"@zh . . . "Algoritmus CYK (Cocke-Younger-Kasami) je algoritmus, kter\u00FD ur\u010Duje, zda slovo n\u00E1le\u017E\u00ED do bezkontextov\u00E9ho jazyka, a to v \u010Dasov\u00E9 slo\u017Eitosti vzhledem k d\u00E9lce slova. Bezkontextov\u00FD jazyk mus\u00ED b\u00FDt zaps\u00E1n gramatikou v Chomsk\u00E9ho norm\u00E1ln\u00ED form\u011B. Algoritmus vypad\u00E1 takto: Vytvo\u0159\u00EDme pole , pro , kde jsou postupn\u011B v\u0161echny netermin\u00E1ly (nebo alternativn\u011B jejich \u010D\u00EDsla), a hodnoty v\u0161ech jeho prvk\u016F nastav\u00EDme na 0Pro ka\u017Ed\u00FD znak na pozici , a pro ka\u017Ed\u00E9 takov\u00E9, \u017Ee v gramatice existuje pravidlo , nastav\u00EDme v poli Pro ka\u017Edou d\u00E9lku podslova od 2 do :Pro ka\u017Ed\u00FD za\u010D\u00E1tek podslova od 1 do :Pro ka\u017Edou d\u00E9lku prvn\u00ED poloviny podslova od 1 do :Jestli\u017Ee v poli maj\u00ED jedni\u010Dkovou hodnotu i , a v gramatice existuje pravidlo , nastav\u00EDme v poli Slovo n\u00E1le\u017E\u00ED do jazyka, jestli\u017Ee , kde je vstupn\u00ED netermin\u00E1l gramatiky. Jin\u00E9 algoritmy jsou Earlyho parser a ."@cs . . . . . . . . "Algorytm CYK"@pl . . . . . . . ", where:\n* is length of the string\n* is the size of the CNF grammar"@en . . "Algoritmus CYK (Cocke-Younger-Kasami) je algoritmus, kter\u00FD ur\u010Duje, zda slovo n\u00E1le\u017E\u00ED do bezkontextov\u00E9ho jazyka, a to v \u010Dasov\u00E9 slo\u017Eitosti vzhledem k d\u00E9lce slova. Bezkontextov\u00FD jazyk mus\u00ED b\u00FDt zaps\u00E1n gramatikou v Chomsk\u00E9ho norm\u00E1ln\u00ED form\u011B. Algoritmus vypad\u00E1 takto: Jin\u00E9 algoritmy jsou Earlyho parser a ."@cs . . "Algorytm CYK (Cocke\u2019a-Youngera-Kasamiego) \u2013 dynamiczny algorytm sprawdzaj\u0105cy, czy s\u0142owo nale\u017Cy do j\u0119zyka bezkontekstowego. J\u0119zyk bezkontekstowy musi by\u0107 przedstawiony w postaci normalnej Chomsky\u2019ego. Algorytm dzia\u0142a w czasie gdzie jest d\u0142ugo\u015Bci\u0105 s\u0142owa, a jest rozmiarem gramatyki."@pl . . "En informatique th\u00E9orique et en th\u00E9orie des langages, l'algorithme de Cocke-Younger-Kasami (CYK) est un algorithme d'analyse syntaxique pour les grammaires non contextuelles, publi\u00E9 par Itiroo Sakai en 1961. Il permet de d\u00E9terminer si un mot est engendr\u00E9 par une grammaire, et si oui, d'en donner un arbre syntaxique. L'algorithme est nomm\u00E9 d'apr\u00E8s les trois personnes qui l'ont red\u00E9couvert ind\u00E9pendamment, J. Cocke, dont l'article n'a jamais \u00E9t\u00E9 publi\u00E9, D. H. Younger et T. Kasami qui a publi\u00E9 un rapport interne aux US-AirForce. L'algorithme op\u00E8re par analyse ascendante et emploie la programmation dynamique. L'algorithme suppose que la grammaire est en forme normale de Chomsky. Cette restriction n'est pas g\u00EAnante dans la mesure o\u00F9 toute grammaire non contextuelle admet une grammaire en forme normale de Chomsky \u00E9quivalente. Le temps de calcul de cet algorithme est en , o\u00F9 est la longueur du mot \u00E0 analyser et est la taille de la grammaire."@fr . . "\u0410\u043B\u0433\u043E\u0440\u0438\u0442\u043C \u041A\u043E\u043A\u0430 \u2014 \u042F\u043D\u0433\u0435\u0440\u0430 \u2014 \u041A\u0430\u0441\u0430\u043C\u0438 (\u0430\u043D\u0433\u043B. Cocke \u2014 Younger \u2014 Kasami algorithm), \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C CYK \u043B\u0438\u0431\u043E CKY \u2014 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C, \u043F\u043E\u0437\u0432\u043E\u043B\u044F\u044E\u0449\u0438\u0439 \u0443\u0441\u0442\u0430\u043D\u043E\u0432\u0438\u0442\u044C, \u043C\u043E\u0436\u043D\u043E \u043B\u0438 \u0432 \u0437\u0430\u0434\u0430\u043D\u043D\u043E\u0439 \u043A\u043E\u043D\u0442\u0435\u043A\u0441\u0442\u043D\u043E-\u0441\u0432\u043E\u0431\u043E\u0434\u043D\u043E\u0439 \u0433\u0440\u0430\u043C\u043C\u0430\u0442\u0438\u043A\u0435 \u0432\u044B\u0432\u0435\u0441\u0442\u0438 \u0437\u0430\u0434\u0430\u043D\u043D\u0443\u044E \u0441\u0442\u0440\u043E\u043A\u0443, \u0438 \u0435\u0441\u043B\u0438 \u044D\u0442\u043E \u0442\u0430\u043A, \u0442\u043E \u043F\u0440\u0435\u0434\u043E\u0441\u0442\u0430\u0432\u0438\u0442\u044C \u0435\u0451 \u0432\u044B\u0432\u043E\u0434. \u0414\u0440\u0443\u0433\u0438\u043C\u0438 \u0441\u043B\u043E\u0432\u0430\u043C\u0438, \u044D\u0442\u043E \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C \u0441\u0438\u043D\u0442\u0430\u043A\u0441\u0438\u0447\u0435\u0441\u043A\u043E\u0433\u043E \u0430\u043D\u0430\u043B\u0438\u0437\u0430 \u0441\u0442\u0440\u043E\u043A\u0438. \u0410\u043B\u0433\u043E\u0440\u0438\u0442\u043C \u0440\u0435\u0430\u043B\u0438\u0437\u0443\u0435\u0442 \u0441\u0438\u043D\u0442\u0430\u043A\u0441\u0438\u0447\u0435\u0441\u043A\u0438\u0439 \u0430\u043D\u0430\u043B\u0438\u0437 \u0441\u043D\u0438\u0437\u0443-\u0432\u0432\u0435\u0440\u0445 \u0438 \u043E\u0441\u043D\u043E\u0432\u044B\u0432\u0430\u0435\u0442\u0441\u044F \u043D\u0430 \u043C\u0435\u0442\u043E\u0434\u0435 \u0434\u0438\u043D\u0430\u043C\u0438\u0447\u0435\u0441\u043A\u043E\u0433\u043E \u043F\u0440\u043E\u0433\u0440\u0430\u043C\u043C\u0438\u0440\u043E\u0432\u0430\u043D\u0438\u044F. \u0435\u0433\u043E \u043E\u0442\u043A\u0440\u044B\u0432\u0430\u0442\u0435\u043B\u0438: \u0414\u0436\u043E\u043D \u041A\u043E\u043A, \u0414\u044D\u043D\u0438\u0435\u043B \u042F\u043D\u0433\u0435\u0440, \u0422\u0430\u0434\u0430\u043E \u041A\u0430\u0441\u0430\u043C\u0438 \u0438 \u0414\u0436\u0435\u0439\u043A\u043E\u0431 \u0422. \u0428\u0432\u0430\u0440\u0446. \u041E\u043D\u0438 \u0438\u0441\u043F\u043E\u043B\u044C\u0437\u043E\u0432\u0430\u043B\u0438 \u0432\u043E\u0441\u0445\u043E\u0434\u044F\u0449\u0438\u0439 \u0430\u043D\u0430\u043B\u0438\u0437 \u0438 \u0434\u0438\u043D\u0430\u043C\u0438\u0447\u0435\u0441\u043A\u043E\u0435 \u043F\u0440\u043E\u0433\u0440\u0430\u043C\u043C\u0438\u0440\u043E\u0432\u0430\u043D\u0438\u0435."@ru . . . . . "Cocke\u2013Younger\u2013Kasami algorithm"@en . . . . "CYK\u6CD5\uFF08\u82F1: CYK algorithm\uFF09\u306F\u3001\u3042\u308B\u6587\u5B57\u5217\u304C\u4E0E\u3048\u3089\u308C\u305F\u6587\u8108\u81EA\u7531\u6587\u6CD5\u3067\u751F\u6210\u3067\u304D\u308B\u304B\u3092\u6C7A\u3081\u3001\u751F\u6210\u3067\u304D\u308B\u5834\u5408\u306E\u751F\u6210\u65B9\u6CD5\u3092\u6C42\u3081\u308B\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u3067\u3042\u308B\u3002CYK \u306F Cocke-Younger-Kasami \u306E\u7565\uFF08\u305D\u308C\u305E\u308C\u3001RISC\u306E\u5148\u99C6\u3068\u8A00\u308F\u308C\u308B801\u306A\u3069\u3067\u3082\u77E5\u3089\u308C\u308B\u30B8\u30E7\u30F3\u30FB\u30B3\u30C3\u30AF\u3001Daniel Younger\u3001\u5D69\u5FE0\u96C4\u3067\u3042\u308B\uFF09\u3002\u6587\u8108\u81EA\u7531\u6587\u6CD5\u306E\u69CB\u6587\u89E3\u6790\u624B\u6CD5\u3068\u6349\u3048\u308B\u3053\u3068\u3082\u3067\u304D\u308B\u3002\u3053\u306E\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u306F\u4E00\u7A2E\u306E\u52D5\u7684\u8A08\u753B\u6CD5\u3067\u3042\u308B\u3002 \u6A19\u6E96\u7684\u306ACYK\u6CD5\u306F\u3001\u30C1\u30E7\u30E0\u30B9\u30AD\u30FC\u6A19\u6E96\u5F62\u3067\u66F8\u304B\u308C\u305F\u6587\u8108\u81EA\u7531\u6587\u6CD5\u3067\u5B9A\u7FA9\u3055\u308C\u308B\u8A00\u8A9E\u3092\u8A8D\u8B58\u3059\u308B\u3002\u4EFB\u610F\u306E\u6587\u8108\u81EA\u7531\u6587\u6CD5\u3092\u30C1\u30E7\u30E0\u30B9\u30AD\u30FC\u6A19\u6E96\u5F62\u306B\u66F8\u304D\u63DB\u3048\u308B\u306E\u306F\u305D\u308C\u307B\u3069\u56F0\u96E3\u3067\u306F\u306A\u3044\u306E\u3067\u3001CYK\u6CD5\u306F\u4EFB\u610F\u306E\u6587\u8108\u81EA\u7531\u6587\u6CD5\u306E\u8A8D\u8B58\u306B\u4F7F\u3046\u3053\u3068\u304C\u3067\u304D\u308B\u3002CYK\u6CD5\u3092\u62E1\u5F35\u3057\u3066\u30C1\u30E7\u30E0\u30B9\u30AD\u30FC\u6A19\u6E96\u5F62\u3067\u66F8\u304B\u308C\u3066\u3044\u306A\u3044\u6587\u8108\u81EA\u7531\u6587\u6CD5\u3092\u6271\u3046\u3088\u3046\u306B\u3059\u308B\u3053\u3068\u3082\u53EF\u80FD\u3067\u3042\u308B\u3002\u3053\u308C\u306B\u3088\u308A\u6027\u80FD\u306F\u5411\u4E0A\u3059\u308B\u304C\u3001\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u3092\u7406\u89E3\u3059\u308B\u3053\u3068\u306F\u96E3\u3057\u304F\u306A\u308B\u3002 CYK\u6CD5\u306E\u6700\u60AA\u6642\u9593\u8A08\u7B97\u91CF\u306F \u0398(n3) \u3067\u3042\u308A\u3001n \u306F\u89E3\u6790\u5BFE\u8C61\u306E\u6587\u5B57\u5217\u306E\u9577\u3055\u3067\u3042\u308B\u3002\u5F93\u3063\u3066\u3001CYK\u6CD5\u306F\u4EFB\u610F\u306E\u6587\u8108\u81EA\u7531\u8A00\u8A9E\u3092\u8A8D\u8B58\u3067\u304D\u308B\u6700\u3082\u52B9\u7387\u7684\u306A\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u306E1\u3064\u3067\u3042\u308B\u3002\u305F\u3060\u3057\u3001\u6587\u8108\u81EA\u7531\u8A00\u8A9E\u306E\u7279\u5B9A\u306E\u30B5\u30D6\u30BB\u30C3\u30C8\u306B\u3064\u3044\u3066\u3001\u3088\u308A\u52B9\u7387\u306E\u826F\u3044\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u304C\u4ED6\u306B\u5B58\u5728\u3059\u308B\u3002"@ja . . . . "\u062E\u0648\u0627\u0631\u0632\u0645\u064A\u0629 CYK"@ar . . . . . . . . "Algorithme de Cocke-Younger-Kasami"@fr . "Het Cocke-Younger-Kasami (CYK)-algoritme (soms ook bekend als CKY) bepaalt of een string gegenereerd kan worden door een gegeven contextvrije grammatica en, als dit het geval is, levert het de manier waarop de string gegenereerd kan worden. Dit proces noemt men het parsen of ontleden van de string. Het algoritme is een voorbeeld van . De standaardversie van het CYK-algoritme herkent talen die gedefinieerd zijn door contextvrije grammatica's in Chomsky-normaalvorm. Aangezien elke contextvrije grammatica op eenvoudige wijze in deze normaalvorm om te zetten is, kan het CYK-algoritme gebruikt worden om alle contextvrije talen te herkennen. Het is eveneens mogelijk het CYK-algoritme uit te breiden zodat de gegeven contextvrije grammatica niet noodzakelijk in Chomsky-normaalvorm moet staan. Zo'n uitbreiding maakt het algoritme meer performant, maar ook moeilijker om de werking te begrijpen. In het slechtste geval is de asymptotische tijdscomplexiteit van het CYK-algoritme \u0398(n3), waar n de lengte van de geparseerde string is. Dit maakt het een van de meest effici\u00EBnte algoritmes voor het herkennen van contextvrije talen qua tijdscomplexiteit. Er zijn echter wel andere algoritmes die nog beter presteren om bepaalde deelgroepen van de contextvrije talen te herkennen. Het algoritme is vernoemd naar John Cocke, en ."@nl . "CYK \uC54C\uACE0\uB9AC\uC998"@ko . . . "En informatique th\u00E9orique et en th\u00E9orie des langages, l'algorithme de Cocke-Younger-Kasami (CYK) est un algorithme d'analyse syntaxique pour les grammaires non contextuelles, publi\u00E9 par Itiroo Sakai en 1961. Il permet de d\u00E9terminer si un mot est engendr\u00E9 par une grammaire, et si oui, d'en donner un arbre syntaxique. L'algorithme est nomm\u00E9 d'apr\u00E8s les trois personnes qui l'ont red\u00E9couvert ind\u00E9pendamment, J. Cocke, dont l'article n'a jamais \u00E9t\u00E9 publi\u00E9, D. H. Younger et T. Kasami qui a publi\u00E9 un rapport interne aux US-AirForce."@fr . . . . . "In computer science, the Cocke\u2013Younger\u2013Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for context-free grammars published by Itiroo Sakai in 1961. The algorithm is named after some of its rediscoverers: John Cocke, Daniel Younger, Tadao Kasami, and Jacob T. Schwartz. It employs bottom-up parsing and dynamic programming. The standard version of CYK operates only on context-free grammars given in Chomsky normal form (CNF). However any context-free grammar may be transformed (after convention) to a CNF grammar expressing the same language. The importance of the CYK algorithm stems from its high efficiency in certain situations. Using big O notation, the worst case running time of CYK is , where is the length of the parsed string and is the size of the CNF grammar . This makes it one of the most efficient parsing algorithms in terms of worst-case asymptotic complexity, although other algorithms exist with better average running time in many practical scenarios."@en . . . "CYK \uC54C\uACE0\uB9AC\uC998(Cocke-Younger-Kasami \uC54C\uACE0\uB9AC\uC998, CYK Algorithm) \uB610\uB294 CKY \uC54C\uACE0\uB9AC\uC998\uC740 \uD2B9\uC815\uD55C \uBB38\uC790\uC5F4\uC5D0 \uB300\uD574, \uADF8 \uBB38\uC790\uC5F4\uC774 \uD2B9\uC815\uD55C \uBB38\uB9E5 \uC790\uC720 \uBB38\uBC95\uC5D0 \uC18D\uD558\uB294\uC9C0\uB97C \uD310\uB2E8\uD558\uACE0, \uB610\uD55C \uC5B4\uB5A0\uD55C \uBC29\uC2DD\uC73C\uB85C \uC0DD\uC131\uB418\uB294\uC9C0\uB97C \uD310\uB2E8\uD558\uB294 \uD30C\uC2F1 \uC54C\uACE0\uB9AC\uC998\uC774\uB2E4. \uC774 \uC54C\uACE0\uB9AC\uC998\uC740 \uB3D9\uC801 \uACC4\uD68D\uBC95\uC744 \uC0AC\uC6A9\uD558\uBA70, \uAD6C\uC870\uB97C \uAC00\uC9C0\uACE0 \uC788\uB2E4. \uAE30\uBCF8\uC801\uC73C\uB85C CYK \uC54C\uACE0\uB9AC\uC998\uC5D0\uC11C\uB294 \uC73C\uB85C \uD45C\uD604\uB41C \uBB38\uB9E5 \uC790\uC720 \uBB38\uBC95\uC744 \uC0AC\uC6A9\uD558\uC9C0\uB9CC, \uBAA8\uB4E0 \uBB38\uB9E5 \uC790\uC720 \uBB38\uBC95\uC740 \uCD18\uC2A4\uD0A4 \uC815\uADDC \uD615\uC2DD\uC73C\uB85C \uBCC0\uD658\uC774 \uAC00\uB2A5\uD558\uAE30 \uB54C\uBB38\uC5D0 CYK \uC54C\uACE0\uB9AC\uC998\uC744 \uC0AC\uC6A9\uD560 \uC218 \uC788\uB2E4. \uBB38\uC790\uC5F4\uC758 \uAE38\uC774\uAC00 \uC77C \uB54C, CYK \uC54C\uACE0\uB9AC\uC998\uC740 \u0398(n3)\uC758 \uC2DC\uAC04 \uBCF5\uC7A1\uB3C4\uB97C \uAC00\uC9C4\uB2E4. \uC774\uAC83\uC740 \uD604\uC7AC \uBAA8\uB4E0 \uBB38\uB9E5 \uC790\uC720 \uBB38\uBC95\uC744 \uD30C\uC2F1\uD560 \uC218 \uC788\uB294 \uAC00\uC7A5 \uD6A8\uC728\uC801\uC778 \uC54C\uACE0\uB9AC\uC998\uC774\uB2E4. (CYK \uC54C\uACE0\uB9AC\uC998\uBCF4\uB2E4 \uD6A8\uC728\uC801\uC73C\uB85C \uB3D9\uC791\uD558\uB294 \uBA87\uBA87 \uC54C\uACE0\uB9AC\uC998\uC774 \uC788\uC9C0\uB9CC, \uADF8 \uC54C\uACE0\uB9AC\uC998\uC740 \uD2B9\uC815\uD55C \uBB38\uBC95\uC758 \uACBD\uC6B0\uC5D0\uB9CC \uC0AC\uC6A9\uC774 \uAC00\uB2A5\uD558\uB2E4.)"@ko . "\u062E\u0648\u0627\u0631\u0632\u0645\u064A\u0629 \u0643\u0648\u0643-\u064A\u0648\u0646\u063A\u064A\u0631-\u0643\u0627\u0633\u0627\u0645\u064A Cocke-Younger-Kasami (\u0648\u062A\u0633\u0645\u0649 \u0623\u064A\u0636\u0627\u064B CKY) \u0647\u064A \u062E\u0648\u0627\u0631\u0632\u0645\u064A\u0629 \u062A\u062D\u0644\u064A\u0644 \u0646\u062D\u0648\u064A \u062A\u0646\u062A\u0645\u064A \u0644\u0644\u0642\u0648\u0627\u0639\u062F \u0627\u0644\u0646\u062D\u0648\u064A\u0629 \u0627\u0644\u062E\u0627\u0644\u064A\u0629 \u0645\u0646 \u0627\u0644\u0633\u064A\u0627\u0642 \u0641\u064A \u0639\u0644\u0648\u0645 \u0627\u0644\u062D\u0627\u0633\u0648\u0628\u060C \u0648\u0642\u062F \u0633\u0645\u064A\u062A \u0628\u0627\u0633\u0645 \u0645\u062E\u062A\u0631\u0639\u064A\u0647\u0627\u060C \u062C\u0648\u0646 \u0643\u0648\u0643\u060C \u062F\u0627\u0646\u064A\u0627\u0644 \u064A\u0648\u0646\u063A\u064A\u0631 \u0648\u062A\u0627\u062F\u0627\u0648 \u0643\u0633\u0627\u0645\u064A. \u0648\u0647\u064A \u062A\u0633\u062A\u062E\u062F\u0645 \u0641\u064A \u0627\u0644\u062A\u062D\u0644\u064A\u0644 \u0645\u0646 \u0627\u0644\u0623\u0633\u0641\u0644 \u0625\u0644\u0649 \u0627\u0644\u0623\u0639\u0644\u0649 \u0648\u0627\u0644\u0628\u0631\u0645\u062C\u0629 \u0627\u0644\u062F\u064A\u0646\u0627\u0645\u064A\u0643\u064A\u0629. \u064A\u0639\u0645\u0644 \u0627\u0644\u0625\u0635\u062F\u0627\u0631 \u0627\u0644\u0642\u064A\u0627\u0633\u064A \u0645\u0646 \u0627\u0644\u062E\u0648\u0627\u0631\u0632\u0645\u064A\u0629 \u0641\u0642\u0637 \u0639\u0644\u0649 \u0627\u0644\u0642\u0648\u0627\u0639\u062F \u0627\u0644\u062E\u0627\u0644\u064A\u0629 \u0645\u0646 \u0627\u0644\u0633\u064A\u0627\u0642 \u0641\u064A \u0646\u0645\u0648\u0630\u062C \u062A\u0634\u0648\u0645\u0633\u0643\u064A \u0627\u0644\u0637\u0628\u064A\u0639\u064A (CNF). \u0648\u0645\u0639 \u0630\u0644\u0643\u060C \u064A\u0645\u0643\u0646 \u062A\u062D\u0648\u064A\u0644 \u0623\u064A \u0642\u0648\u0627\u0639\u062F \u0646\u062D\u0648\u064A\u0629 \u062E\u0627\u0644\u064A\u0629 \u0645\u0646 \u0627\u0644\u0633\u064A\u0627\u0642 \u0625\u0644\u0649 \u0642\u0648\u0627\u0639\u062F CNF \u0645\u0639\u0628\u0631\u0629 \u0639\u0646 \u0646\u0641\u0633 \u0627\u0644\u0644\u063A\u0629."@ar . . . . . . . "CYK\u7B97\u6CD5\uFF08\u82F1\u8A9E\uFF1ACocke\u2013Younger\u2013Kasami algorithm\uFF0C\u7E2E\u5BEB\u70BACYK algorithm\uFF09\u662F\u7531\u7D04\u7FF0\u00B7\u79D1\u514B\uFF0CYounger\u548C\u5171\u540C\u7814\u7A76\u51FA\u6765\u5927\u7EA6\u53D1\u8868\u4E8E1965\u5E74\u7684\u4E00\u4E2A\u7B97\u6CD5\uFF0C\u5B83\u662F\u4E00\u4E2A\u7528\u6765\u5224\u5B9A\u4EFB\u610F\u7ED9\u5B9A\u7684\u5B57\u7B26\u4E32 \u662F\u5426\u5C5E\u4E8E\u4E00\u4E2A\u4E0A\u4E0B\u6587\u65E0\u5173\u6587\u6CD5\u7684\u7B97\u6CD5\u3002\u666E\u901A\u7684\u56DE\u6EAF\u6CD5\uFF08backtracking\uFF09\u5728\u6700\u574F\u7684\u60C5\u51B5\u4E0B\u9700\u8981\u6307\u6570\u65F6\u95F4\u624D\u80FD\u89E3\u51B3\u8FD9\u6837\u7684\u95EE\u9898\uFF0C\u800CCYK\u7B97\u6CD5\u53EA\u9700\u8981\u591A\u9879\u5F0F\u65F6\u95F4\u5C31\u591F\u4E86\uFF08 \uFF0C n \u4E3A\u5B57\u7B26\u4E32 w \u7684\u957F\u5EA6\uFF09\u3002CYK\u7B97\u6CD5\u91C7\u7528\u4E86\u52A8\u6001\u89C4\u5212\u7684\u601D\u60F3\u3002 \u5BF9\u4E8E\u4E00\u4E2A\u4EFB\u610F\u7ED9\u5B9A\u7684\u4E0A\u4E0B\u6587\u65E0\u5173\u6587\u6CD5\uFF0C\u90FD\u53EF\u4EE5\u4F7F\u7528CYK\u7B97\u6CD5\u6765\u8BA1\u7B97\u4E0A\u8FF0\u95EE\u9898\uFF0C\u4F46\u9996\u5148\u8981\u5C06\u8BE5\u6587\u6CD5\u8F6C\u6362\u6210\u4E54\u59C6\u65AF\u57FA\u8303\u5F0F\u3002"@zh . . "El algoritmo de Cocke-Younger-Kasami (CYK) determina si una cadena puede ser generada por una gram\u00E1tica libre de contexto y, si es posible, c\u00F3mo puede ser generada. Este proceso es conocido como an\u00E1lisis sint\u00E1ctico de la cadena. El algoritmo es un ejemplo de programaci\u00F3n din\u00E1mica."@es . . . . "In computer science, the Cocke\u2013Younger\u2013Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for context-free grammars published by Itiroo Sakai in 1961. The algorithm is named after some of its rediscoverers: John Cocke, Daniel Younger, Tadao Kasami, and Jacob T. Schwartz. It employs bottom-up parsing and dynamic programming. The standard version of CYK operates only on context-free grammars given in Chomsky normal form (CNF). However any context-free grammar may be transformed (after convention) to a CNF grammar expressing the same language."@en . . "Algoritmus Cocke-Younger-Kasami"@cs . "\u0410\u043B\u0433\u043E\u0440\u0438\u0442\u043C \u041A\u043E\u043A\u0430 \u2014 \u042F\u043D\u0433\u0435\u0440\u0430 \u2014 \u041A\u0430\u0441\u0430\u043C\u0438"@ru . . . . . . . "Het Cocke-Younger-Kasami (CYK)-algoritme (soms ook bekend als CKY) bepaalt of een string gegenereerd kan worden door een gegeven contextvrije grammatica en, als dit het geval is, levert het de manier waarop de string gegenereerd kan worden. Dit proces noemt men het parsen of ontleden van de string. Het algoritme is een voorbeeld van . Het algoritme is vernoemd naar John Cocke, en ."@nl . . . "CYK \uC54C\uACE0\uB9AC\uC998(Cocke-Younger-Kasami \uC54C\uACE0\uB9AC\uC998, CYK Algorithm) \uB610\uB294 CKY \uC54C\uACE0\uB9AC\uC998\uC740 \uD2B9\uC815\uD55C \uBB38\uC790\uC5F4\uC5D0 \uB300\uD574, \uADF8 \uBB38\uC790\uC5F4\uC774 \uD2B9\uC815\uD55C \uBB38\uB9E5 \uC790\uC720 \uBB38\uBC95\uC5D0 \uC18D\uD558\uB294\uC9C0\uB97C \uD310\uB2E8\uD558\uACE0, \uB610\uD55C \uC5B4\uB5A0\uD55C \uBC29\uC2DD\uC73C\uB85C \uC0DD\uC131\uB418\uB294\uC9C0\uB97C \uD310\uB2E8\uD558\uB294 \uD30C\uC2F1 \uC54C\uACE0\uB9AC\uC998\uC774\uB2E4. \uC774 \uC54C\uACE0\uB9AC\uC998\uC740 \uB3D9\uC801 \uACC4\uD68D\uBC95\uC744 \uC0AC\uC6A9\uD558\uBA70, \uAD6C\uC870\uB97C \uAC00\uC9C0\uACE0 \uC788\uB2E4. \uAE30\uBCF8\uC801\uC73C\uB85C CYK \uC54C\uACE0\uB9AC\uC998\uC5D0\uC11C\uB294 \uC73C\uB85C \uD45C\uD604\uB41C \uBB38\uB9E5 \uC790\uC720 \uBB38\uBC95\uC744 \uC0AC\uC6A9\uD558\uC9C0\uB9CC, \uBAA8\uB4E0 \uBB38\uB9E5 \uC790\uC720 \uBB38\uBC95\uC740 \uCD18\uC2A4\uD0A4 \uC815\uADDC \uD615\uC2DD\uC73C\uB85C \uBCC0\uD658\uC774 \uAC00\uB2A5\uD558\uAE30 \uB54C\uBB38\uC5D0 CYK \uC54C\uACE0\uB9AC\uC998\uC744 \uC0AC\uC6A9\uD560 \uC218 \uC788\uB2E4. \uBB38\uC790\uC5F4\uC758 \uAE38\uC774\uAC00 \uC77C \uB54C, CYK \uC54C\uACE0\uB9AC\uC998\uC740 \u0398(n3)\uC758 \uC2DC\uAC04 \uBCF5\uC7A1\uB3C4\uB97C \uAC00\uC9C4\uB2E4. \uC774\uAC83\uC740 \uD604\uC7AC \uBAA8\uB4E0 \uBB38\uB9E5 \uC790\uC720 \uBB38\uBC95\uC744 \uD30C\uC2F1\uD560 \uC218 \uC788\uB294 \uAC00\uC7A5 \uD6A8\uC728\uC801\uC778 \uC54C\uACE0\uB9AC\uC998\uC774\uB2E4. (CYK \uC54C\uACE0\uB9AC\uC998\uBCF4\uB2E4 \uD6A8\uC728\uC801\uC73C\uB85C \uB3D9\uC791\uD558\uB294 \uBA87\uBA87 \uC54C\uACE0\uB9AC\uC998\uC774 \uC788\uC9C0\uB9CC, \uADF8 \uC54C\uACE0\uB9AC\uC998\uC740 \uD2B9\uC815\uD55C \uBB38\uBC95\uC758 \uACBD\uC6B0\uC5D0\uB9CC \uC0AC\uC6A9\uC774 \uAC00\uB2A5\uD558\uB2E4.)"@ko . . . . "O algoritmo Cocke-Younger-Kasami (CYK) determina se uma cadeia de caracteres pode ser gerada por uma determinada gram\u00E1tica livre de contexto e, se ela puder, como ela pode ser gerada. Esse processo \u00E9 conhecido como a an\u00E1lise sint\u00E1tica da cadeia, no caso, ascendente."@pt . . . "Der Cocke-Younger-Kasami-Algorithmus (CYK-Algorithmus) ist ein Algorithmus aus dem Gebiet der theoretischen Informatik. Mit ihm l\u00E4sst sich feststellen, ob ein Wort zu einer bestimmten kontextfreien Sprache geh\u00F6rt. In der Fachsprache bezeichnet man dies als L\u00F6sen des Wortproblems f\u00FCr kontextfreie Sprachen. Mit Hilfe von Backtracking kann der Parse-Tree bzw. die Parse-Trees eines gegebenen Wortes der Sprache konstruiert werden. Um den Algorithmus anzuwenden, muss zu der vorgegebenen Sprache eine Grammatik in Chomsky-Normalform vorliegen. Der in den 1960er Jahren von , John Cocke, Tadao Kasami, Jacob Schwartz und unabh\u00E4ngig voneinander entwickelte Algorithmus nutzt das Prinzip der dynamischen Programmierung."@de . "53929"^^ . "CYK algorithm"@en . . . . . . . "Parsing with context-free grammars"@en . . . . . . . . . "\u0410\u043B\u0433\u043E\u0440\u0438\u0442\u043C \u041A\u043E\u043A\u0430 \u2014 \u042F\u043D\u0433\u0435\u0440\u0430 \u2014 \u041A\u0430\u0441\u0430\u043C\u0438 (\u0430\u043D\u0433\u043B. Cocke \u2014 Younger \u2014 Kasami algorithm), \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C CYK \u043B\u0438\u0431\u043E CKY \u2014 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C, \u043F\u043E\u0437\u0432\u043E\u043B\u044F\u044E\u0449\u0438\u0439 \u0443\u0441\u0442\u0430\u043D\u043E\u0432\u0438\u0442\u044C, \u043C\u043E\u0436\u043D\u043E \u043B\u0438 \u0432 \u0437\u0430\u0434\u0430\u043D\u043D\u043E\u0439 \u043A\u043E\u043D\u0442\u0435\u043A\u0441\u0442\u043D\u043E-\u0441\u0432\u043E\u0431\u043E\u0434\u043D\u043E\u0439 \u0433\u0440\u0430\u043C\u043C\u0430\u0442\u0438\u043A\u0435 \u0432\u044B\u0432\u0435\u0441\u0442\u0438 \u0437\u0430\u0434\u0430\u043D\u043D\u0443\u044E \u0441\u0442\u0440\u043E\u043A\u0443, \u0438 \u0435\u0441\u043B\u0438 \u044D\u0442\u043E \u0442\u0430\u043A, \u0442\u043E \u043F\u0440\u0435\u0434\u043E\u0441\u0442\u0430\u0432\u0438\u0442\u044C \u0435\u0451 \u0432\u044B\u0432\u043E\u0434. \u0414\u0440\u0443\u0433\u0438\u043C\u0438 \u0441\u043B\u043E\u0432\u0430\u043C\u0438, \u044D\u0442\u043E \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C \u0441\u0438\u043D\u0442\u0430\u043A\u0441\u0438\u0447\u0435\u0441\u043A\u043E\u0433\u043E \u0430\u043D\u0430\u043B\u0438\u0437\u0430 \u0441\u0442\u0440\u043E\u043A\u0438. \u0410\u043B\u0433\u043E\u0440\u0438\u0442\u043C \u0440\u0435\u0430\u043B\u0438\u0437\u0443\u0435\u0442 \u0441\u0438\u043D\u0442\u0430\u043A\u0441\u0438\u0447\u0435\u0441\u043A\u0438\u0439 \u0430\u043D\u0430\u043B\u0438\u0437 \u0441\u043D\u0438\u0437\u0443-\u0432\u0432\u0435\u0440\u0445 \u0438 \u043E\u0441\u043D\u043E\u0432\u044B\u0432\u0430\u0435\u0442\u0441\u044F \u043D\u0430 \u043C\u0435\u0442\u043E\u0434\u0435 \u0434\u0438\u043D\u0430\u043C\u0438\u0447\u0435\u0441\u043A\u043E\u0433\u043E \u043F\u0440\u043E\u0433\u0440\u0430\u043C\u043C\u0438\u0440\u043E\u0432\u0430\u043D\u0438\u044F. \u0435\u0433\u043E \u043E\u0442\u043A\u0440\u044B\u0432\u0430\u0442\u0435\u043B\u0438: \u0414\u0436\u043E\u043D \u041A\u043E\u043A, \u0414\u044D\u043D\u0438\u0435\u043B \u042F\u043D\u0433\u0435\u0440, \u0422\u0430\u0434\u0430\u043E \u041A\u0430\u0441\u0430\u043C\u0438 \u0438 \u0414\u0436\u0435\u0439\u043A\u043E\u0431 \u0422. \u0428\u0432\u0430\u0440\u0446. \u041E\u043D\u0438 \u0438\u0441\u043F\u043E\u043B\u044C\u0437\u043E\u0432\u0430\u043B\u0438 \u0432\u043E\u0441\u0445\u043E\u0434\u044F\u0449\u0438\u0439 \u0430\u043D\u0430\u043B\u0438\u0437 \u0438 \u0434\u0438\u043D\u0430\u043C\u0438\u0447\u0435\u0441\u043A\u043E\u0435 \u043F\u0440\u043E\u0433\u0440\u0430\u043C\u043C\u0438\u0440\u043E\u0432\u0430\u043D\u0438\u0435. \u0421\u0442\u0430\u043D\u0434\u0430\u0440\u0442\u043D\u0430\u044F \u0432\u0435\u0440\u0441\u0438\u044F CYK \u0440\u0430\u0431\u043E\u0442\u0430\u0435\u0442 \u0442\u043E\u043B\u044C\u043A\u043E \u0441 \u043A\u043E\u043D\u0442\u0435\u043A\u0441\u0442\u043D\u043E-\u0441\u0432\u043E\u0431\u043E\u0434\u043D\u044B\u043C\u0438 \u0433\u0440\u0430\u043C\u043C\u0430\u0442\u0438\u043A\u0430\u043C\u0438, \u0437\u0430\u0434\u0430\u043D\u043D\u044B\u043C\u0438 \u0432 \u043D\u043E\u0440\u043C\u0430\u043B\u044C\u043D\u043E\u0439 \u0444\u043E\u0440\u043C\u0435 (CNF). \u041E\u0434\u043D\u0430\u043A\u043E \u043B\u044E\u0431\u0430\u044F \u043A\u043E\u043D\u0442\u0435\u043A\u0441\u0442\u043D\u043E-\u0441\u0432\u043E\u0431\u043E\u0434\u043D\u0430\u044F \u0433\u0440\u0430\u043C\u043C\u0430\u0442\u0438\u043A\u0430 \u043C\u043E\u0436\u0435\u0442 \u0431\u044B\u0442\u044C \u043F\u0440\u0435\u043E\u0431\u0440\u0430\u0437\u043E\u0432\u0430\u043D\u0430 (\u043F\u043E\u0441\u043B\u0435 \u043A\u043E\u043D\u0432\u0435\u0440\u0442\u0438\u0440\u043E\u0432\u0430\u043D\u0438\u044F) \u0432 \u0433\u0440\u0430\u043C\u043C\u0430\u0442\u0438\u043A\u0443 CNF, \u0432\u044B\u0440\u0430\u0436\u0430\u044E\u0449\u0443\u044E \u0442\u043E\u0442 \u0436\u0435 \u044F\u0437\u044B\u043A (Sipser 1997). \u042F\u0432\u043B\u044F\u0435\u0442\u0441\u044F \u043E\u0434\u043D\u0438\u043C \u0438\u0437 \u0441\u0430\u043C\u044B\u0445 \u044D\u0444\u0444\u0435\u043A\u0442\u0438\u0432\u043D\u044B\u0445 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u043E\u0432 \u0441\u0438\u043D\u0442\u0430\u043A\u0441\u0438\u0447\u0435\u0441\u043A\u043E\u0433\u043E \u0430\u043D\u0430\u043B\u0438\u0437\u0430 \u0441 \u0442\u043E\u0447\u043A\u0438 \u0437\u0440\u0435\u043D\u0438\u044F \u0430\u0441\u0438\u043C\u043F\u0442\u043E\u0442\u0438\u0447\u0435\u0441\u043A\u043E\u0439 \u0441\u043B\u043E\u0436\u043D\u043E\u0441\u0442\u0438 \u0432 \u043D\u0430\u0438\u0445\u0443\u0434\u0448\u0435\u043C \u0441\u043B\u0443\u0447\u0430\u0435, \u0445\u043E\u0442\u044F \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044E\u0442 \u0438 \u0434\u0440\u0443\u0433\u0438\u0435 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u044B \u0441 \u043B\u0443\u0447\u0448\u0438\u043C \u0441\u0440\u0435\u0434\u043D\u0438\u043C \u0432\u0440\u0435\u043C\u0435\u043D\u0435\u043C \u0432\u044B\u043F\u043E\u043B\u043D\u0435\u043D\u0438\u044F \u0432\u043E \u043C\u043D\u043E\u0433\u0438\u0445 \u043F\u0440\u0430\u043A\u0442\u0438\u0447\u0435\u0441\u043A\u0438\u0445 \u0441\u0446\u0435\u043D\u0430\u0440\u0438\u044F\u0445."@ru . . "17032"^^ . "\u062E\u0648\u0627\u0631\u0632\u0645\u064A\u0629 \u0643\u0648\u0643-\u064A\u0648\u0646\u063A\u064A\u0631-\u0643\u0627\u0633\u0627\u0645\u064A Cocke-Younger-Kasami (\u0648\u062A\u0633\u0645\u0649 \u0623\u064A\u0636\u0627\u064B CKY) \u0647\u064A \u062E\u0648\u0627\u0631\u0632\u0645\u064A\u0629 \u062A\u062D\u0644\u064A\u0644 \u0646\u062D\u0648\u064A \u062A\u0646\u062A\u0645\u064A \u0644\u0644\u0642\u0648\u0627\u0639\u062F \u0627\u0644\u0646\u062D\u0648\u064A\u0629 \u0627\u0644\u062E\u0627\u0644\u064A\u0629 \u0645\u0646 \u0627\u0644\u0633\u064A\u0627\u0642 \u0641\u064A \u0639\u0644\u0648\u0645 \u0627\u0644\u062D\u0627\u0633\u0648\u0628\u060C \u0648\u0642\u062F \u0633\u0645\u064A\u062A \u0628\u0627\u0633\u0645 \u0645\u062E\u062A\u0631\u0639\u064A\u0647\u0627\u060C \u062C\u0648\u0646 \u0643\u0648\u0643\u060C \u062F\u0627\u0646\u064A\u0627\u0644 \u064A\u0648\u0646\u063A\u064A\u0631 \u0648\u062A\u0627\u062F\u0627\u0648 \u0643\u0633\u0627\u0645\u064A. \u0648\u0647\u064A \u062A\u0633\u062A\u062E\u062F\u0645 \u0641\u064A \u0627\u0644\u062A\u062D\u0644\u064A\u0644 \u0645\u0646 \u0627\u0644\u0623\u0633\u0641\u0644 \u0625\u0644\u0649 \u0627\u0644\u0623\u0639\u0644\u0649 \u0648\u0627\u0644\u0628\u0631\u0645\u062C\u0629 \u0627\u0644\u062F\u064A\u0646\u0627\u0645\u064A\u0643\u064A\u0629. \u064A\u0639\u0645\u0644 \u0627\u0644\u0625\u0635\u062F\u0627\u0631 \u0627\u0644\u0642\u064A\u0627\u0633\u064A \u0645\u0646 \u0627\u0644\u062E\u0648\u0627\u0631\u0632\u0645\u064A\u0629 \u0641\u0642\u0637 \u0639\u0644\u0649 \u0627\u0644\u0642\u0648\u0627\u0639\u062F \u0627\u0644\u062E\u0627\u0644\u064A\u0629 \u0645\u0646 \u0627\u0644\u0633\u064A\u0627\u0642 \u0641\u064A \u0646\u0645\u0648\u0630\u062C \u062A\u0634\u0648\u0645\u0633\u0643\u064A \u0627\u0644\u0637\u0628\u064A\u0639\u064A (CNF). \u0648\u0645\u0639 \u0630\u0644\u0643\u060C \u064A\u0645\u0643\u0646 \u062A\u062D\u0648\u064A\u0644 \u0623\u064A \u0642\u0648\u0627\u0639\u062F \u0646\u062D\u0648\u064A\u0629 \u062E\u0627\u0644\u064A\u0629 \u0645\u0646 \u0627\u0644\u0633\u064A\u0627\u0642 \u0625\u0644\u0649 \u0642\u0648\u0627\u0639\u062F CNF \u0645\u0639\u0628\u0631\u0629 \u0639\u0646 \u0646\u0641\u0633 \u0627\u0644\u0644\u063A\u0629. \u062A\u0646\u0628\u0639 \u0623\u0647\u0645\u064A\u0629 \u062E\u0648\u0627\u0631\u0632\u0645\u064A\u0629 (CYK) \u0645\u0646 \u0643\u0641\u0627\u0621\u062A\u0647\u0627 \u0627\u0644\u0639\u0627\u0644\u064A\u0629 \u0641\u064A \u0645\u0648\u0627\u0642\u0641 \u0645\u0639\u064A\u0646\u0629. \u0625\u0630\u0627 \u0645\u0627 \u0642\u064A\u0645\u0646\u0627 \u0643\u0641\u0627\u0621\u0629 \u0639\u0645\u0644\u0647\u0627 \u0628\u0648\u0627\u0633\u0637\u0629 \u0645\u0642\u064A\u0627\u0633 \u0627\u0644\u062A\u0639\u0642\u064A\u062F \u0627\u0644\u062D\u0633\u0627\u0628\u064A Big O\u060C \u0641\u0625\u0646 \u0627\u0633\u0648\u0621 \u062D\u0627\u0644\u0629 \u062A\u0634\u063A\u064A\u0644 \u064A\u0645\u0643\u0646 \u0627\u0644\u062D\u0635\u0648\u0644 \u0639\u0644\u064A\u0647\u0627 \u0641\u064A \u062E\u0648\u0627\u0631\u0632\u0645\u064A\u0629 CYK \u0647\u064A \u060C \u062D\u064A\u062B \u062A\u0645\u062B\u0644 n \u0637\u0648\u0644 \u0627\u0644\u062C\u0645\u0644\u0629 \u0627\u0644\u0645\u0631\u0627\u062F \u062A\u062D\u0644\u064A\u0644\u0647\u0627 \u0641\u064A\u0645\u0627 \u062A\u0645\u062B\u0644 G \u062D\u062C\u0645 \u0627\u0644\u0642\u0648\u0627\u0639\u062F \u0636\u0645\u0646 \u0646\u0645\u0648\u0630\u062C \u062A\u0634\u0648\u0645\u0633\u0643\u064A \u0627\u0644\u0637\u0628\u064A\u0639\u064A \u0627\u0644\u0630\u064A \u064A\u062A\u0645 \u0627\u0644\u0639\u0645\u0644 \u0639\u0644\u064A\u0647. \u0648\u064A\u062C\u0639\u0644\u0647\u0627 \u0647\u0630\u0627 \u0625\u062D\u062F\u0649 \u0623\u0643\u062B\u0631 \u062E\u0648\u0627\u0631\u0632\u0645\u064A\u0627\u062A \u0627\u0644\u062A\u062D\u0644\u064A\u0644 \u0627\u0644\u0646\u062D\u0648\u064A \u0641\u0627\u0639\u0644\u064A\u0629\u060C \u0645\u0646 \u0646\u0627\u062D\u064A\u0629 \u0627\u0644\u062A\u0639\u0642\u064A\u062F \u0627\u0644\u062D\u0633\u0627\u0628\u064A."@ar . .