{"id":324472,"date":"2021-06-07T09:00:37","date_gmt":"2021-06-07T09:00:37","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=324472"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=324472","title":{"rendered":"\u0413\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0440\u0430\u0437\u0431\u043e\u0440 \u0434\u043b\u044f \u0435\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0445 \u044f\u0437\u044b\u043a\u043e\u0432. \u0427.2: \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 (CYK)"},"content":{"rendered":"\n<div class=\"post__text post__text_v2\" id=\"post-content-body\">\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/317\/017\/09a\/31701709a7694f6416487c19b10731d4.png\" width=\"510\" height=\"340\"><figcaption><\/figcaption><\/figure>\n<p><a href=\"https:\/\/habr.com\/ru\/company\/macloud\/blog\/558760\/\">\u0427\u0430\u0441\u0442\u044c .1: \u042f\u0437\u044b\u043a\u0438 \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u044f \u044f\u0437\u044b\u043a\u043e\u0432<\/a><\/p>\n<p>\u0412 \u0438\u0434\u0435\u0430\u043b\u0435 \u043d\u0430\u043c \u0445\u043e\u0442\u0435\u043b\u043e\u0441\u044c \u0431\u044b \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0442\u044c \u0442\u0435\u043a\u0441\u0442 \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0438 \u0437\u0430 \u043e\u0434\u0438\u043d \u043f\u0440\u043e\u0445\u043e\u0434. \u0420\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u044b\u0435 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u044f \u044d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0442, \u043d\u043e \u0443\u0436\u0435 \u0441 CFG \u044d\u0442\u043e \u043d\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f: \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440,&nbsp;<code>S \u2192 A | B; A \u2192 a | x A; B \u2192 b | x B<\/code>&nbsp;\u043f\u0440\u0435\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0441\u0442\u0440\u043e\u043a\u0443&nbsp;<code>x\u2026xa<\/code>&nbsp;\u0432 \u0434\u0435\u0440\u0435\u0432\u043e \u0438\u0437 \u0443\u0437\u043b\u043e\u0432&nbsp;<code>A<\/code>, \u0430 \u0441\u0442\u0440\u043e\u043a\u0443&nbsp;<code>x\u2026xb<\/code>&nbsp;\u0432 \u0434\u0435\u0440\u0435\u0432\u043e \u0438\u0437 \u0443\u0437\u043b\u043e\u0432&nbsp;<code>B<\/code>&nbsp;\u2014 \u0438 \u043f\u043e\u043a\u0430 \u0440\u0430\u0437\u0431\u043e\u0440\u0449\u0438\u043a \u043d\u0435 \u0443\u0432\u0438\u0434\u0438\u0442 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u0441\u0442\u0440\u043e\u043a\u0438, \u043e\u043d \u043d\u0435 \u0437\u043d\u0430\u0435\u0442, \u0447\u0442\u043e \u0434\u0435\u043b\u0430\u0442\u044c \u0441\u043e \u0432\u0441\u0435\u043c\u0438 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u043c\u0438 \u0441\u0438\u043c\u0432\u043e\u043b\u0430\u043c\u0438. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u043d\u0430 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 \u0434\u043b\u044f \u044f\u0437\u044b\u043a\u043e\u0432 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043d\u0430\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u044e\u0442 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u2014 \u043f\u043e \u0441\u0443\u0442\u0438, \u0447\u0442\u043e\u0431\u044b \u0434\u043b\u044f \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u043d\u0435 \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u043b\u043e\u0441\u044c &#171;\u0437\u0430\u0433\u043b\u044f\u0434\u044b\u0432\u0430\u0442\u044c \u0432\u043f\u0435\u0440\u0451\u0434&#187; \u2014 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0449\u0438\u0435 \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0442\u044c \u0442\u0435\u043a\u0441\u0442 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b \u0437\u0430 \u043e\u0434\u0438\u043d \u043f\u0440\u043e\u0445\u043e\u0434. \u041a\u0442\u043e \u043a\u043e\u0432\u044b\u0440\u044f\u043b\u0441\u044f \u0432 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440\u0430\u0445, \u0442\u043e\u0442 \u043d\u0430\u0432\u0435\u0440\u043d\u044f\u043a\u0430 \u0437\u043d\u0430\u043a\u043e\u043c \u0441 LL- \u0438 LR-\u0440\u0430\u0437\u0431\u043e\u0440\u043e\u043c, \u0438 \u0438\u043c\u0435\u0435\u0442 \u043e\u043f\u044b\u0442 &#171;\u043f\u043e\u0434\u0433\u043e\u043d\u043a\u0438&#187; \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 \u044f\u0437\u044b\u043a\u0430 \u043f\u043e\u0434 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u044f \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0440\u0430\u0437\u0431\u043e\u0440\u0430. \u041d\u043e \u043f\u0440\u0438 \u0440\u0430\u0431\u043e\u0442\u0435 \u0441 \u0435\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u043c\u0438 \u044f\u0437\u044b\u043a\u0430\u043c\u0438 \u043d\u0435\u0442 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u0438 &#171;\u043f\u043e\u0434\u043f\u0440\u0430\u0432\u0438\u0442\u044c&#187; \u044f\u0437\u044b\u043a \u0434\u043b\u044f \u0443\u0434\u043e\u0431\u0441\u0442\u0432\u0430 \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u2014 \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0441 \u0442\u0435\u043c \u044f\u0437\u044b\u043a\u043e\u043c, \u043a\u0430\u043a\u043e\u0439 \u0435\u0441\u0442\u044c.<\/p>\n<p>\u0412 1960-\u0445 \u0431\u044b\u043b \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043d \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c CYK \u0434\u043b\u044f \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0433\u043e CFG. \u0421\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u0432\u043f\u0435\u0440\u0432\u044b\u0435 \u0435\u0433\u043e \u043e\u043f\u0443\u0431\u043b\u0438\u043a\u043e\u0432\u0430\u043b\u0438 \u2014 \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e \u0434\u0440\u0443\u0433 \u043e\u0442 \u0434\u0440\u0443\u0433\u0430 \u2014 \u0418. \u0421\u0430\u043a\u0430\u0438 \u0438\u0437 \u044f\u043f\u043e\u043d\u0441\u043a\u043e\u0433\u043e \u041d\u0418\u0418 \u041c\u0438\u043d\u043e\u0431\u043e\u0440\u043e\u043d\u044b \u0432 1961 \u0438 \u0414\u0436. \u041a\u043e\u043a \u0438\u0437 \u041d\u044c\u044e-\u0419\u043e\u0440\u043a\u0441\u043a\u043e\u0433\u043e \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442\u0430 \u0432 1962. \u0412 1966 \u0442\u043e\u0442 \u0436\u0435 \u0441\u0430\u043c\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u0443\u0431\u043b\u0438\u043a\u043e\u0432\u0430\u043b\u0438 \u2014 \u043e\u043f\u044f\u0442\u044c \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e \u2014 \u0414. \u042f\u043d\u0433\u0435\u0440 \u0438\u0437 General Electric \u0438 \u0422. \u041a\u0430\u0441\u0430\u043c\u0438 \u0438\u0437 \u0423\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442\u0430 \u0418\u043b\u043b\u0438\u043d\u043e\u0439\u0441\u0430. \u042f\u043d\u0433\u0435\u0440 \u0432 \u0441\u0432\u043e\u0435\u0439 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0438 \u0443\u043f\u043e\u043c\u0438\u043d\u0430\u0435\u0442 \u0438\u043c\u0435\u043d\u0430 \u041a\u043e\u043a\u0430 \u0438 \u0421\u0430\u043a\u0430\u0438, \u043d\u043e \u043d\u0435 \u0441\u0441\u044b\u043b\u0430\u0435\u0442\u0441\u044f \u043d\u0438 \u043d\u0430 \u043a\u0430\u043a\u0438\u0435 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u044b\u0435 \u0438\u0445 \u0440\u0430\u0431\u043e\u0442\u044b: \u043f\u043e \u0432\u0441\u0435\u0439 \u0432\u0438\u0434\u0438\u043c\u043e\u0441\u0442\u0438, \u0440\u0430\u0431\u043e\u0442\u044b \u041a\u043e\u043a\u0430 \u0438 \u0421\u0430\u043a\u0430\u0438 \u042f\u043d\u0433\u0435\u0440\u0443 \u2014 \u043a\u0430\u043a \u0438 \u043c\u043d\u0435 \u0441\u0435\u0439\u0447\u0430\u0441 \u2014 \u043d\u0435 \u0431\u044b\u043b\u0438 \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u044b. \u0427\u0442\u043e\u0431\u044b \u043d\u0438\u043a\u043e\u043c\u0443 \u0438\u0437 \u0438\u0437\u043e\u0431\u0440\u0435\u0442\u0430\u0442\u0435\u043b\u0435\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043d\u0435 \u0431\u044b\u043b\u043e \u043e\u0431\u0438\u0434\u043d\u043e, \u0435\u0433\u043e \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442 \u0432 \u0447\u0435\u0441\u0442\u044c \u0441\u0440\u0430\u0437\u0443 \u0442\u0440\u043e\u0438\u0445, \u0445\u043e\u0442\u044f \u043e\u043d\u0438, \u0441\u043a\u043e\u0440\u0435\u0435 \u0432\u0441\u0435\u0433\u043e, \u0434\u0430\u0436\u0435 \u043d\u0435 \u0431\u044b\u043b\u0438 \u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0431\u043e\u0439 \u0437\u043d\u0430\u043a\u043e\u043c\u044b.<\/p>\n<p>\u0418\u0434\u0435\u044f CYK \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0440\u0430\u0437\u0431\u043e\u0440\u0435 &#171;\u0441\u043d\u0438\u0437\u0443 \u0432\u0432\u0435\u0440\u0445&#187; \u2014 \u043e\u0442 \u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u043e\u0432 \u043a S \u2014 \u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0438 \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 \u0434\u043b\u044f \u0438\u0437\u0431\u0435\u0436\u0430\u043d\u0438\u044f \u043f\u043e\u0432\u0442\u043e\u0440\u043d\u044b\u0445 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439: \u0432\u043d\u0430\u0447\u0430\u043b\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u043c \u0432\u0441\u0435 \u0443\u0437\u043b\u044b, \u0432\u044b\u0432\u043e\u0434\u0438\u043c\u044b\u0435 \u043d\u0435\u043f\u043e\u0441\u0440\u0435\u0434\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0438\u0437 \u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u043e\u0432, \u0438 \u043f\u043e\u043c\u0435\u0441\u0442\u0438\u043c \u0438\u0445 \u043d\u0430 &#171;\u0434\u043e\u0441\u043a\u0443&#187;. \u041d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0432\u043e\u0437\u044c\u043c\u0451\u043c \u0441 \u0434\u043e\u0441\u043a\u0438 \u043e\u0434\u0438\u043d \u0443\u0437\u0435\u043b, \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u043c \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u0443\u0437\u043b\u044b \u0441 \u0435\u0433\u043e \u0443\u0447\u0430\u0441\u0442\u0438\u0435\u043c, \u0438 \u0434\u043e\u0431\u0430\u0432\u0438\u043c \u043d\u0430 \u0434\u043e\u0441\u043a\u0443 \u0435\u0449\u0451 \u0438 \u0438\u0445. \u0415\u0441\u043b\u0438 \u043d\u0430 \u0434\u043e\u0441\u043a\u0435 \u043f\u043e\u044f\u0432\u0438\u043b\u0441\u044f S \u0434\u043b\u044f \u0432\u0441\u0435\u0433\u043e \u0442\u0435\u043a\u0441\u0442\u0430 \u0446\u0435\u043b\u0438\u043a\u043e\u043c, \u0437\u043d\u0430\u0447\u0438\u0442 \u0440\u0430\u0437\u0431\u043e\u0440 \u0443\u0434\u0430\u043b\u0441\u044f; \u0435\u0441\u043b\u0438 \u0432\u0441\u0435 \u0443\u0437\u043b\u044b \u0441 \u0434\u043e\u0441\u043a\u0438 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u044b, \u043d\u043e S \u0442\u0430\u043c \u0442\u0430\u043a \u0438 \u043d\u0435 \u043f\u043e\u044f\u0432\u0438\u043b\u0441\u044f \u2014 \u0437\u043d\u0430\u0447\u0438\u0442, \u0440\u0430\u0437\u0431\u043e\u0440 \u043d\u0435 \u0443\u0434\u0430\u043b\u0441\u044f. \u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u044f \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043f\u0440\u0438\u043c\u0435\u0440\u0430 \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0435\u0442 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0435 &#171;<em>She eats the fish with a fork.<\/em>&#187; \u043f\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0435:<\/p>\n<pre><code class=\"vala\">S \u2192 NP VP VP \u2192 VP PP | V NP | V PP \u2192 P NP NP \u2192 Det N | she V \u2192 eats P \u2192 with N \u2192 fish | fork Det \u2192 a | the<\/code><\/pre>\n<div>\n<div class=\"table\">\n<table>\n<tbody>\n<tr>\n<td>\n<p>\u0428\u0430\u0433<\/p>\n<\/td>\n<td>\n<p>\u041d\u0435\u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0435 \u0443\u0437\u043b\u044b \u043d\u0430 \u0434\u043e\u0441\u043a\u0435<\/p>\n<\/td>\n<td>\n<p>\u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0435 \u0443\u0437\u043b\u044b \u043d\u0430 \u0434\u043e\u0441\u043a\u0435<\/p>\n<\/td>\n<td>\n<p>\u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c\u044b\u0435 \u043d\u0430 \u0434\u043e\u0441\u043a\u0443 \u0443\u0437\u043b\u044b<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>1<\/p>\n<\/td>\n<td>\n<\/td>\n<td>\n<\/td>\n<td>\n<p><em>She<\/em><sub>NP<\/sub><em>, eats<\/em><sub>V<\/sub><em>, the<\/em><sub>Det<\/sub><em>, fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>2<\/p>\n<\/td>\n<td>\n<p><strong><em>She<\/em><sub>NP<\/sub><\/strong><em>, eats<\/em><sub>V<\/sub><em>, the<\/em><sub>Det<\/sub><em>, fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub><\/p>\n<\/td>\n<td>\n<\/td>\n<td>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>3<\/p>\n<\/td>\n<td>\n<p><strong><em>eats<\/em><sub>V<\/sub><\/strong><em>, the<\/em><sub>Det<\/sub><em>, fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub><\/p>\n<\/td>\n<td>\n<p><em>She<\/em><sub>NP<\/sub><\/p>\n<\/td>\n<td>\n<p><em>eats<\/em><sub>VP<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>4<\/p>\n<\/td>\n<td>\n<p><strong><em>the<\/em><sub>Det<\/sub><\/strong><em>, fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub>,&nbsp;<em>eats<\/em><sub>VP<\/sub><\/p>\n<\/td>\n<td>\n<p><em>She<\/em><sub>NP<\/sub><em>, eats<\/em><sub>V<\/sub><\/p>\n<\/td>\n<td>\n<p>[<em>the fish<\/em>]<sub>NP<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>5, 6<\/p>\n<\/td>\n<td>\n<p><strong><em>fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><\/strong><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub>,&nbsp;<em>eats<\/em><sub>VP<\/sub>, [<em>the fish<\/em>]<sub>NP<\/sub><\/p>\n<\/td>\n<td>\n<p><em>She<\/em><sub>NP<\/sub><em>, eats<\/em><sub>V<\/sub><em>, the<\/em><sub>Det<\/sub><\/p>\n<\/td>\n<td>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>7<\/p>\n<\/td>\n<td>\n<p><strong><em>a<\/em><sub>Det<\/sub><\/strong><em>, fork<\/em><sub>N<\/sub>,&nbsp;<em>eats<\/em><sub>VP<\/sub>, [<em>the fish<\/em>]<sub>NP<\/sub><\/p>\n<\/td>\n<td>\n<p><em>She<\/em><sub>NP<\/sub><em>, eats<\/em><sub>V<\/sub><em>, the<\/em><sub>Det<\/sub><em>, fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><\/p>\n<\/td>\n<td>\n<p>[<em>a fork<\/em>]<sub>NP<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>8<\/p>\n<\/td>\n<td>\n<p><strong><em>fork<\/em><sub>N<\/sub><\/strong>,&nbsp;<em>eats<\/em><sub>VP<\/sub>, [<em>the fish<\/em>]<sub>NP<\/sub>, [<em>a fork<\/em>]<sub>NP<\/sub><\/p>\n<\/td>\n<td>\n<p><em>She<\/em><sub>NP<\/sub><em>, eats<\/em><sub>V<\/sub><em>, the<\/em><sub>Det<\/sub><em>, fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><em>, a<\/em><sub>Det<\/sub><\/p>\n<\/td>\n<td>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>9<\/p>\n<\/td>\n<td>\n<p><strong><em>eats<\/em><sub>VP<\/sub><\/strong>, [<em>the fish<\/em>]<sub>NP<\/sub>, [<em>a fork<\/em>]<sub>NP<\/sub><\/p>\n<\/td>\n<td>\n<p><strong><em>She<\/em><sub>NP<\/sub><\/strong><em>, eats<\/em><sub>V<\/sub><em>, the<\/em><sub>Det<\/sub><em>, fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub><\/p>\n<\/td>\n<td>\n<p>[<em>She eats<\/em>]<sub>S<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>10<\/p>\n<\/td>\n<td>\n<p><strong>[<em>the fish<\/em>]<sub>NP<\/sub><\/strong>, [<em>a fork<\/em>]<sub>NP<\/sub>, [<em>She eats<\/em>]<sub>S<\/sub><\/p>\n<\/td>\n<td>\n<p><em>She<\/em><sub>NP<\/sub><em>,&nbsp;<\/em><strong><em>eats<\/em><sub>V<\/sub><\/strong><em>, the<\/em><sub>Det<\/sub><em>, fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub><em>, eats<\/em><sub>VP<\/sub><\/p>\n<\/td>\n<td>\n<p>[<em>eats the fish<\/em>]<sub>VP<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>11<\/p>\n<\/td>\n<td>\n<p><strong>[<em>a fork<\/em>]<sub>NP<\/sub><\/strong>, [<em>She eats<\/em>]<sub>S<\/sub>, [<em>eats the fish<\/em>]<sub>VP<\/sub><\/p>\n<\/td>\n<td>\n<p><em>She<\/em><sub>NP<\/sub>,<em>&nbsp;eats<\/em><sub>V<\/sub>,<em>&nbsp;the<\/em><sub>Det<\/sub>,<em>&nbsp;fish<\/em><sub>N<\/sub><em>,&nbsp;<\/em><strong><em>with<\/em><sub>P<\/sub><\/strong><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub><em>, eats<\/em><sub>VP<\/sub>,<em>&nbsp;<\/em>[<em>the fish<\/em>]<sub>NP<\/sub><\/p>\n<\/td>\n<td>\n<p>[<em>with a fork<\/em>]<sub>PP<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>12<\/p>\n<\/td>\n<td>\n<p><strong>[<em>She eats<\/em>]<sub>S<\/sub><\/strong>, [<em>eats the fish<\/em>]<sub>VP<\/sub>, [<em>with a fork<\/em>]<sub>PP<\/sub><\/p>\n<\/td>\n<td>\n<p><em>She<\/em><sub>NP<\/sub>,<em>&nbsp;eats<\/em><sub>V<\/sub>,<em>&nbsp;the<\/em><sub>Det<\/sub>,<em>&nbsp;fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub><em>, eats<\/em><sub>VP<\/sub>,<em>&nbsp;<\/em><strong>[<em>the fish<\/em>]<sub>NP<\/sub><\/strong>, [<em>a fork<\/em>]<sub>NP<\/sub><\/p>\n<\/td>\n<td>\n<p>[<em>She eats the fish<\/em>]<sub>S<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>13<\/p>\n<\/td>\n<td>\n<p><strong>[<em>eats the fish<\/em>]<sub>VP<\/sub><\/strong>, [<em>with a fork<\/em>]<sub>PP<\/sub>, [<em>She eats the fish<\/em>]<sub>S<\/sub><\/p>\n<\/td>\n<td>\n<p><em>She<\/em><sub>NP<\/sub>,<em>&nbsp;eats<\/em><sub>V<\/sub>,<em>&nbsp;the<\/em><sub>Det<\/sub>,<em>&nbsp;fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub><em>, eats<\/em><sub>VP<\/sub>,<em>&nbsp;<\/em>[<em>the fish<\/em>]<sub>NP<\/sub>, [<em>a fork<\/em>]<sub>NP,&nbsp;<\/sub>[<em>She eats<\/em>]<sub>S<\/sub><\/p>\n<\/td>\n<td>\n<p>[<em>eats the fish with a fork<\/em>]<sub>VP<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>14, 15<\/p>\n<\/td>\n<td>\n<p><strong>[<em>with a fork<\/em>]<sub>PP<\/sub>, [<em>She eats the fish<\/em>]<sub>S<\/sub><\/strong>, [<em>eats the fish with a fork<\/em>]<sub>VP<\/sub><\/p>\n<\/td>\n<td>\n<p><em>She<\/em><sub>NP<\/sub>,<em>&nbsp;eats<\/em><sub>V<\/sub>,<em>&nbsp;the<\/em><sub>Det<\/sub>,<em>&nbsp;fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub><em>, eats<\/em><sub>VP<\/sub>,<em>&nbsp;<\/em>[<em>the fish<\/em>]<sub>NP<\/sub>, [<em>a fork<\/em>]<sub>NP,&nbsp;<\/sub>[<em>She eats<\/em>]<sub>S<\/sub>, [<em>eats the fish with a fork<\/em>]<sub>VP<\/sub><\/p>\n<\/td>\n<td>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>16<\/p>\n<\/td>\n<td>\n<p><strong>[<em>eats the fish with a fork<\/em>]<sub>VP<\/sub><\/strong><\/p>\n<\/td>\n<td>\n<p><strong><em>She<\/em><sub>NP<\/sub><\/strong>,<em>&nbsp;eats<\/em><sub>V<\/sub>,<em>&nbsp;the<\/em><sub>Det<\/sub>,<em>&nbsp;fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub><em>, eats<\/em><sub>VP<\/sub>,<em>&nbsp;<\/em>[<em>the fish<\/em>]<sub>NP<\/sub>, [<em>a fork<\/em>]<sub>NP,&nbsp;<\/sub>[<em>She eats<\/em>]<sub>S<\/sub>, [<em>eats the fish with a fork<\/em>]<sub>VP<\/sub>, [<em>with a fork<\/em>]<sub>PP<\/sub>, [<em>She eats the fish<\/em>]<sub>S<\/sub><\/p>\n<\/td>\n<td>\n<p><strong>[<em>She eats the fish with a fork<\/em>]<sub>S<\/sub><\/strong><\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<p>\u041a\u0430\u043a\u043e\u0432\u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c CYK \u0434\u043b\u044f CFG? \u041d\u0430 \u0434\u043e\u0441\u043a\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043a\u0430\u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c&nbsp;<img decoding=\"async\" class=\"formula inline\" source=\"|N|\\cdot\\frac{n\\cdot(n+1)}2\" alt=\"|N|\\cdot\\frac{n\\cdot(n+1)}2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bae\/8ae\/cf7\/bae8aecf77aab799d13ca61b4bdd8ade.svg\">&nbsp;\u0443\u0437\u043b\u043e\u0432 \u2014 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0438 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 \u0432\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0442\u0435\u043a\u0441\u0442\u0430; \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0434\u043e\u0441\u043a\u0443 \u0443\u0434\u043e\u0431\u043d\u043e \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432 \u0432\u0438\u0434\u0435 \u0442\u0440\u0451\u0445\u043c\u0435\u0440\u043d\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430, \u0438\u043d\u0434\u0435\u043a\u0441\u044b \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u2014 \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b, \u043d\u0430\u0447\u0430\u043b\u043e \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 \u0438 \u043a\u043e\u043d\u0435\u0446 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438. \u041d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0435 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043e\u0434\u0438\u043d \u0443\u0437\u0435\u043b \u0441 \u0434\u043e\u0441\u043a\u0438 \u2014 \u0437\u043d\u0430\u0447\u0438\u0442, \u0434\u043b\u044f \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u044e\u0442\u0441\u044f&nbsp;<img decoding=\"async\" class=\"formula inline\" source=\"O(n^2)\" alt=\"O(n^2)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/091\/7c6\/1d4\/0917c61d458268ad5a1f3ef6bf36950f.svg\">&nbsp;\u0448\u0430\u0433\u043e\u0432. \u041d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u044e\u0442\u0441\u044f \u0432\u0441\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438, \u0438 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043f\u0440\u0430\u0432\u0438\u043b\u0430, \u0433\u0434\u0435 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u043c\u044b\u0439 \u0443\u0437\u0435\u043b \u043f\u043e\u0434\u0445\u043e\u0434\u0438\u0442 \u043f\u043e\u0434 \u043f\u0440\u0430\u0432\u0443\u044e \u0447\u0430\u0441\u0442\u044c, \u0431\u0443\u0434\u0443\u0442 \u043f\u0440\u043e\u0432\u0435\u0440\u0435\u043d\u044b \u0432\u0441\u0435 \u0443\u0437\u043b\u044b \u0441 \u0434\u043e\u0441\u043a\u0438, \u043c\u043e\u0433\u0443\u0449\u0438\u0435 \u0443\u0447\u0430\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u0432 \u043f\u0440\u0430\u0432\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u0432\u043c\u0435\u0441\u0442\u0435 \u0441 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u043c\u044b\u043c \u0443\u0437\u043b\u043e\u043c. \u041e\u0441\u0442\u0430\u043b\u043e\u0441\u044c \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0442\u0430\u043a\u043e\u0433\u043e \u0448\u0430\u0433\u0430.<\/p>\n<p>\u0418\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c CYK \u0440\u0430\u0431\u043e\u0442\u0430\u043b \u0441 CFG \u0432&nbsp;<a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9D%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D0%B0_%D0%A5%D0%BE%D0%BC%D1%81%D0%BA%D0%BE%D0%B3%D0%BE\"><em>\u043d\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0444\u043e\u0440\u043c\u0435&nbsp;\u0425\u043e\u043c\u0441\u043a\u043e\u0433\u043e<\/em><\/a>&nbsp;(CNF) \u2014 \u0432 \u043f\u0440\u0430\u0432\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u0432\u044b\u0432\u043e\u0434\u0430 \u0434\u043e\u043f\u0443\u0441\u043a\u0430\u043b\u0438\u0441\u044c \u043b\u0438\u0431\u043e \u043e\u0434\u0438\u043d \u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b, \u043b\u0438\u0431\u043e \u0434\u0432\u0430 \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u0430. \u0414\u043b\u044f \u043f\u0440\u0430\u0432\u0438\u043b\u0430&nbsp;<code>A \u2192 BC<\/code>&nbsp;&#171;\u0432\u0441\u0435 \u0443\u0437\u043b\u044b \u0441 \u0434\u043e\u0441\u043a\u0438, \u043c\u043e\u0433\u0443\u0449\u0438\u0435 \u0443\u0447\u0430\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u0432 \u043f\u0440\u0430\u0432\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u0432\u043c\u0435\u0441\u0442\u0435 \u0441 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u043c\u044b\u043c \u0443\u0437\u043b\u043e\u043c&#187; \u2014 \u044d\u0442\u043e \u043a\u0430\u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c&nbsp;<img decoding=\"async\" class=\"formula inline\" source=\"n\" alt=\"n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/62e\/f8b\/4e3\/62ef8b4e3f5596b813c29649b69367a3.svg\">&nbsp;\u0443\u0437\u043b\u043e\u0432 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c\u0438 (C, end<sub>B<\/sub>, ?) \u0438\/\u0438\u043b\u0438 \u043a\u0430\u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c&nbsp;<img decoding=\"async\" class=\"formula inline\" source=\"n\" alt=\"n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/62e\/f8b\/4e3\/62ef8b4e3f5596b813c29649b69367a3.svg\">&nbsp;\u0443\u0437\u043b\u043e\u0432 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c\u0438 (B, ?, start<sub>C<\/sub>). (\u0415\u0441\u043b\u0438 B=C, \u0442\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0442 \u043e\u0431\u0430 \u043d\u0430\u0431\u043e\u0440\u0430 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432.) \u041f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043e\u0434\u043d\u043e\u0433\u043e \u0448\u0430\u0433\u0430 CYK \u0434\u043b\u044f CNF \u2014 \u044d\u0442\u043e&nbsp;<img decoding=\"async\" class=\"formula inline\" source=\"O(n)\" alt=\"O(n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bb8\/6f5\/e76\/bb86f5e7601ffb3f61f58e11252e4fd1.svg\">, \u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0432\u0441\u0435\u0433\u043e \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u2014 \u044d\u0442\u043e&nbsp;<img decoding=\"async\" class=\"formula inline\" source=\"O(n^3)\" alt=\"O(n^3)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/fe9\/29b\/20e\/fe929b20e4e88e2bc630a39517198864.svg\">.<\/p>\n<p>\u0410 \u0435\u0441\u043b\u0438 CFG \u043d\u0435 \u0432 CNF? \u0414\u043b\u044f \u043f\u0440\u0430\u0432\u0438\u043b\u0430&nbsp;<code>A \u2192 BCD<\/code>&nbsp;\u043f\u0440\u0438\u0434\u0451\u0442\u0441\u044f \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c:<\/p>\n<ul>\n<li>\n<p>\u043a\u0430\u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c&nbsp;<img decoding=\"async\" class=\"formula inline\" source=\"n\" alt=\"n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/62e\/f8b\/4e3\/62ef8b4e3f5596b813c29649b69367a3.svg\">&nbsp;\u0443\u0437\u043b\u043e\u0432 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c\u0438 (C, end<sub>B<\/sub>, ?), \u0438 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0438\u0437 \u043d\u0438\u0445 \u2014 \u043a\u0430\u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c&nbsp;<img decoding=\"async\" class=\"formula inline\" source=\"n\" alt=\"n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/62e\/f8b\/4e3\/62ef8b4e3f5596b813c29649b69367a3.svg\">&nbsp;\u0443\u0437\u043b\u043e\u0432 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c\u0438 (D, end<sub>C<\/sub>, ?);<\/p>\n<\/li>\n<li>\n<p>\u043a\u0430\u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c&nbsp;<img decoding=\"async\" class=\"formula inline\" source=\"n^2\" alt=\"n^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0aa\/fd1\/fd0\/0aafd1fd0f3d0a4095d6c1849810462e.svg\">&nbsp;\u043f\u0430\u0440 \u0443\u0437\u043b\u043e\u0432 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c\u0438 (B, ?, start<sub>C<\/sub>), \u0438 (D, end<sub>C<\/sub>, ?);<\/p>\n<\/li>\n<li>\n<p>\u043a\u0430\u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c&nbsp;<img decoding=\"async\" class=\"formula inline\" source=\"n\" alt=\"n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/62e\/f8b\/4e3\/62ef8b4e3f5596b813c29649b69367a3.svg\">&nbsp;\u0443\u0437\u043b\u043e\u0432 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c\u0438 (C, ?, start<sub>D<\/sub>), \u0438 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0438\u0437 \u043d\u0438\u0445 \u2014 \u043a\u0430\u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c&nbsp;<img decoding=\"async\" class=\"formula inline\" source=\"n\" alt=\"n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/62e\/f8b\/4e3\/62ef8b4e3f5596b813c29649b69367a3.svg\">&nbsp;\u0443\u0437\u043b\u043e\u0432 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c\u0438 (B, ?, start<sub>C<\/sub>).<\/p>\n<\/li>\n<\/ul>\n<p>\u0417\u043d\u0430\u0447\u0438\u0442, \u0435\u0441\u043b\u0438 \u0432 \u043f\u0440\u0430\u0432\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u0432\u044b\u0432\u043e\u0434\u0430 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u0442\u044c \u0434\u043e \u0442\u0440\u0451\u0445 \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u043e\u0432, \u0442\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043e\u0434\u043d\u043e\u0433\u043e \u0448\u0430\u0433\u0430 CYK \u0431\u0443\u0434\u0435\u0442&nbsp;<img decoding=\"async\" class=\"formula inline\" source=\"O(n^2)\" alt=\"O(n^2)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e27\/557\/23c\/e2755723cb187ceca022d580508f7c0c.svg\">, \u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0432\u0441\u0435\u0433\u043e \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u0431\u0443\u0434\u0435\u0442&nbsp;<img decoding=\"async\" class=\"formula inline\" source=\"O(n^4)\" alt=\"O(n^4)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/67a\/735\/4bc\/67a7354bca0e656c0eaed7cea3a27ecb.svg\">. \u041e\u0431\u043e\u0431\u0449\u0430\u044f \u043d\u0430 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u0443\u044e CFG \u2014 \u0432\u0438\u0434\u0438\u043c, \u0447\u0442\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 CYK \u0431\u0443\u0434\u0435\u0442&nbsp;<img decoding=\"async\" class=\"formula inline\" source=\"O(n^{r+1})\" alt=\"O(n^{r+1})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/23c\/09e\/3ec\/23c09e3ecb3baf90583f9fbd5199d0ea.svg\">, \u0433\u0434\u0435&nbsp;<img decoding=\"async\" class=\"formula inline\" source=\"r\" alt=\"r\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/027\/21d\/cef\/02721dcef5bc180303b42a1701b2a870.svg\">&nbsp;\u2014 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u0434\u043b\u0438\u043d\u0430 \u043f\u0440\u0430\u0432\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u043f\u0440\u0430\u0432\u0438\u043b \u0432\u044b\u0432\u043e\u0434\u0430 (&#171;\u0440\u0430\u043d\u0433 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438&#187;).<\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u043e\u0431\u043e\u0431\u0449\u0438\u043c CYK \u0434\u043b\u044f MCFG, \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u044f \u0435\u0433\u043e \u0446\u0435\u043d\u0442\u0440\u0430\u043b\u044c\u043d\u0443\u044e \u0438\u0434\u0435\u044e: \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0431\u0435\u0440\u0451\u043c \u0441 \u0434\u043e\u0441\u043a\u0438 \u043e\u0434\u0438\u043d \u0443\u0437\u0435\u043b, \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u0443\u0437\u043b\u044b \u0441 \u0435\u0433\u043e \u0443\u0447\u0430\u0441\u0442\u0438\u0435\u043c, \u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0438\u0445 \u043d\u0430 \u0434\u043e\u0441\u043a\u0443. \u0420\u0430\u0437\u0431\u043e\u0440 &#171;<em>\u042f \u0442\u0435\u0431\u044f \u0434\u0435\u0442\u044f\u043c \u043f\u0440\u043e\u0441\u0438\u043b \u043f\u043e\u043c\u043e\u0447\u044c!<\/em>&#187; \u043f\u043e \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0435, \u043f\u0440\u0438\u0432\u0435\u0434\u0451\u043d\u043d\u043e\u0439 \u0432 \u0447.1 \u0438 \u0434\u043b\u044f \u0443\u0434\u043e\u0431\u0441\u0442\u0432\u0430 \u043f\u043e\u0432\u0442\u043e\u0440\u0451\u043d\u043d\u043e\u0439 \u0437\u0434\u0435\u0441\u044c, \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f \u0442\u0430\u043a\u0438\u043c:<\/p>\n<pre><code class=\"vala\">VP(X,Y) \u2190 NP(X),V(Y) CP(X,Y) \u2190 VP(X,Y) VP(X,YZW) \u2190 NP(X),V(Z),CP(Y,W) S(XYZ) \u2190 NP(X),VP(Y,Z) NP(\u044f) \u2190 \u03b5 NP(\u0442\u0435\u0431\u044f) \u2190 \u03b5 NP(\u0434\u0435\u0442\u044f\u043c) \u2190 \u03b5 V(\u043f\u0440\u043e\u0441\u0438\u043b) \u2190 \u03b5 V(\u043f\u043e\u043c\u043e\u0447\u044c) \u2190 \u03b5<\/code><\/pre>\n<div>\n<div class=\"table\">\n<table>\n<tbody>\n<tr>\n<td>\n<p>\u0428\u0430\u0433<\/p>\n<\/td>\n<td>\n<p>\u041d\u0435\u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0435 \u0443\u0437\u043b\u044b<\/p>\n<\/td>\n<td data-colwidth=\"195\" width=\"195\">\n<p>\u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0435 \u0443\u0437\u043b\u044b<\/p>\n<\/td>\n<td>\n<p>\u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c\u044b\u0435 \u0443\u0437\u043b\u044b<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>1<\/p>\n<\/td>\n<td>\n<\/td>\n<td data-colwidth=\"195\" width=\"195\">\n<\/td>\n<td>\n<p><em>\u042f<\/em><sub>NP<\/sub>, <em>\u0442\u0435\u0431\u044f<\/em><sub>NP<\/sub>, <em>\u0434\u0435\u0442\u044f\u043c<\/em><sub>NP<\/sub>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em><sub>V<\/sub>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em><sub>V<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>2\u20144<\/p>\n<\/td>\n<td>\n<p><strong><em>\u042f<\/em><sub>NP<\/sub>, <em>\u0442\u0435\u0431\u044f<\/em><sub>NP<\/sub>, <em>\u0434\u0435\u0442\u044f\u043c<\/em><sub>NP<\/sub><\/strong>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em><sub>V<\/sub>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em><sub>V<\/sub><\/p>\n<\/td>\n<td data-colwidth=\"195\" width=\"195\">\n<\/td>\n<td>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>5<\/p>\n<\/td>\n<td>\n<p><strong><em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em><sub>V<\/sub><\/strong>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em><sub>V<\/sub><\/p>\n<\/td>\n<td data-colwidth=\"195\" width=\"195\">\n<p><strong><em>\u042f<\/em><sub>NP<\/sub>, <em>\u0442\u0435\u0431\u044f<\/em><sub>NP<\/sub>,<\/strong> <strong><em>\u0434\u0435\u0442\u044f\u043c<\/em><sub>NP<\/sub><\/strong><\/p>\n<\/td>\n<td>\n<p>(<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>6<\/p>\n<\/td>\n<td>\n<p><strong><em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em><sub>V<\/sub><\/strong>, (<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub><\/p>\n<\/td>\n<td data-colwidth=\"195\" width=\"195\">\n<p><strong><em>\u042f<\/em><sub>NP<\/sub>, <em>\u0442\u0435\u0431\u044f<\/em><sub>NP<\/sub>,<\/strong> <strong><em>\u0434\u0435\u0442\u044f\u043c<\/em><sub>NP<\/sub><\/strong>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em><sub>V<\/sub><\/p>\n<\/td>\n<td>\n<p>(<em>\u042f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>7, 8<\/p>\n<\/td>\n<td>\n<p><strong>(<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub><\/strong>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, (<em>\u042f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub><\/p>\n<\/td>\n<td data-colwidth=\"195\" width=\"195\">\n<p><em>\u042f<\/em><sub>NP<\/sub>, <em>\u0442\u0435\u0431\u044f<\/em><sub>NP<\/sub>, <em>\u0434\u0435\u0442\u044f\u043c<\/em><sub>NP<\/sub>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em><sub>V<\/sub>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em><sub>V<\/sub><\/p>\n<\/td>\n<td>\n<p>(<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>\u0421P<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>\u0421P<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>9<\/p>\n<\/td>\n<td>\n<p><strong>(<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub><\/strong>, (<em>\u042f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub>, (<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>\u0421P<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>\u0421P<\/sub><\/p>\n<\/td>\n<td data-colwidth=\"195\" width=\"195\">\n<p><em>\u042f<\/em><sub>NP<\/sub>, <strong><em>\u0442\u0435\u0431\u044f<\/em><sub>NP<\/sub><\/strong>, <em>\u0434\u0435\u0442\u044f\u043c<\/em><sub>NP<\/sub>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em><sub>V<\/sub>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em><sub>V<\/sub>, (<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub><\/p>\n<\/td>\n<td>\n<p>[<em>\u0442\u0435\u0431\u044f \u0434\u0435\u0442\u044f\u043c \u043f\u0440\u043e\u0441\u0438\u043b<\/em>]<sub>S<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>\u0421P<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>10\u201412<\/p>\n<\/td>\n<td>\n<p><strong>(<em>\u042f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub><\/strong>, (<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>\u0421P<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>\u0421P<\/sub>, [<em>\u0442\u0435\u0431\u044f \u0434\u0435\u0442\u044f\u043c \u043f\u0440\u043e\u0441\u0438\u043b<\/em>]<sub>S<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>\u0421P<\/sub><\/p>\n<\/td>\n<td data-colwidth=\"195\" width=\"195\">\n<p><em>\u042f<\/em><sub>NP<\/sub>, <em>\u0442\u0435\u0431\u044f<\/em><sub>NP<\/sub>, <em>\u0434\u0435\u0442\u044f\u043c<\/em><sub>NP<\/sub>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em><sub>V<\/sub>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em><sub>V<\/sub>, (<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub><\/p>\n<\/td>\n<td>\n<p>(<em>\u042f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>\u0421P<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>\u0421P<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>CP<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>13\u201418<\/p>\n<\/td>\n<td>\n<p><strong>(<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>\u0421P<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>\u0421P<\/sub>, [<em>\u0442\u0435\u0431\u044f \u0434\u0435\u0442\u044f\u043c \u043f\u0440\u043e\u0441\u0438\u043b<\/em>]<sub>S<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>\u0421P<\/sub>, (<em>\u042f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>\u0421P<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>\u0421P<\/sub><\/strong>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>CP<\/sub><\/p>\n<\/td>\n<td data-colwidth=\"195\" width=\"195\">\n<p><em>\u042f<\/em><sub>NP<\/sub>, <em>\u0442\u0435\u0431\u044f<\/em><sub>NP<\/sub>, <em>\u0434\u0435\u0442\u044f\u043c<\/em><sub>NP<\/sub>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em><sub>V<\/sub>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em><sub>V<\/sub>, (<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, &#8230;<\/p>\n<\/td>\n<td>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>19<\/p>\n<\/td>\n<td>\n<p><strong>(<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>CP<\/sub><\/strong><\/p>\n<\/td>\n<td data-colwidth=\"195\" width=\"195\">\n<p><em>\u042f<\/em><sub>NP<\/sub>, <strong><em>\u0442\u0435\u0431\u044f<\/em><sub>NP<\/sub><\/strong>, <em>\u0434\u0435\u0442\u044f\u043c<\/em><sub>NP<\/sub>, <strong><em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em><sub>V<\/sub><\/strong>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em><sub>V<\/sub>, (<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, &#8230;<\/p>\n<\/td>\n<td>\n<p>(<em>\u0442\u0435\u0431\u044f<\/em>, [<em>\u0434\u0435\u0442\u044f\u043c \u043f\u0440\u043e\u0441\u0438\u043b \u043f\u043e\u043c\u043e\u0447\u044c<\/em>])<sub>VP<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>20<\/p>\n<\/td>\n<td>\n<p><strong>(<em>\u0442\u0435\u0431\u044f<\/em>, [<em>\u0434\u0435\u0442\u044f\u043c \u043f\u0440\u043e\u0441\u0438\u043b \u043f\u043e\u043c\u043e\u0447\u044c<\/em>])<sub>VP<\/sub><\/strong><\/p>\n<\/td>\n<td data-colwidth=\"195\" width=\"195\">\n<p><strong><em>\u042f<\/em><sub>NP<\/sub><\/strong>, <em>\u0442\u0435\u0431\u044f<\/em><sub>NP<\/sub>, <em>\u0434\u0435\u0442\u044f\u043c<\/em><sub>NP<\/sub>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em><sub>V<\/sub>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em><sub>V<\/sub>, (<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, &#8230;<\/p>\n<\/td>\n<td>\n<p><strong>[<em>\u042f \u0442\u0435\u0431\u044f \u0434\u0435\u0442\u044f\u043c \u043f\u0440\u043e\u0441\u0438\u043b \u043f\u043e\u043c\u043e\u0447\u044c<\/em>]<sub>S<\/sub><\/strong><\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<p>\u041a\u0430\u043a \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0442\u0430\u043a\u043e\u0439 \u0440\u0430\u0437\u0431\u043e\u0440, \u0438 \u043a\u0430\u043a\u043e\u0439 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f \u0435\u0433\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c? \u0422\u0440\u0451\u0445\u043c\u0435\u0440\u043d\u043e\u0439 \u0434\u043e\u0441\u043a\u043e\u0439 \u0443\u0436\u0435 \u043d\u0435 \u043e\u0431\u043e\u0439\u0442\u0438\u0441\u044c: \u0443\u0437\u043b\u044b \u0434\u0432\u0443\u0445\u043c\u0435\u0441\u0442\u043d\u044b\u0445 \u043f\u0440\u0435\u0434\u0438\u043a\u0430\u0442\u043e\u0432, \u0442\u0430\u043a\u0438\u0445 \u043a\u0430\u043a VP \u0438 CP, \u043c\u043e\u0433\u0443\u0442 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u0434\u043b\u044f \u043b\u044e\u0431\u043e\u0439 \u043f\u0430\u0440\u044b \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a \u0432\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0442\u0435\u043a\u0441\u0442\u0430, \u0442\u0430\u043a \u0447\u0442\u043e \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u0446\u0438\u044f \u043f\u044f\u0442\u0451\u0440\u043a\u0430\u043c\u0438 (\u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b, \u043d\u0430\u0447\u0430\u043b\u043e<sub>1<\/sub>, \u043a\u043e\u043d\u0435\u0446<sub>1<\/sub>, \u043d\u0430\u0447\u0430\u043b\u043e<sub>2<\/sub>, \u043a\u043e\u043d\u0435\u0446<sub>2<\/sub>). \u041e\u0434\u043d\u043e \u0443\u0436\u0435 \u044d\u0442\u043e \u043f\u043e\u0432\u044b\u0448\u0430\u0435\u0442 \u0447\u0438\u0441\u043b\u043e \u0448\u0430\u0433\u043e\u0432 \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u0434\u043e <img decoding=\"async\" class=\"formula inline\" source=\"O(n^4)\" alt=\"O(n^4)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/10c\/494\/d92\/10c494d928f1a778b2f449281ccb87ce.svg\">. \u0422\u0435\u043f\u0435\u0440\u044c \u043d\u0430\u0434\u043e \u043f\u043e\u043d\u044f\u0442\u044c, \u043a\u0430\u043a\u0438\u0435 \u0443\u0437\u043b\u044b \u0442\u0430\u043a\u043e\u0439 \u043f\u044f\u0442\u0438\u043c\u0435\u0440\u043d\u043e\u0439 \u0434\u043e\u0441\u043a\u0438 \u043c\u043e\u0433\u0443\u0442 \u0443\u0447\u0430\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u0432\u043c\u0435\u0441\u0442\u0435 \u0441 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u043c\u044b\u043c \u0443\u0437\u043b\u043e\u043c \u0432 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u0432\u044b\u0432\u043e\u0434\u0430 \u2014 \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043f\u0440\u0430\u0432\u0438\u043b\u0430 <code>P(XY,ZW) \u2190 P(X,Z),P(Y,W)<\/code> \u0438\u0437 \u043f\u0440\u0438\u0432\u0435\u0434\u0451\u043d\u043d\u043e\u0439 \u0432 \u0447.1 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 \u044f\u0437\u044b\u043a\u0430 \u0434\u0432\u0430\u0436\u0434\u044b \u043f\u043e\u0432\u0442\u043e\u0440\u0451\u043d\u043d\u044b\u0445 \u0441\u0442\u0440\u043e\u043a. \u041f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0438\u0435 \u0443\u0437\u043b\u044b \u0431\u0443\u0434\u0443\u0442 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c\u0441\u044f \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c (P, end<sub>X<\/sub>, ?, end<sub>Z<\/sub>, ?) \u0438 (P, ?, start<sub>Y<\/sub>, ?, start<sub>W<\/sub>), \u0442\u0430\u043a \u0447\u0442\u043e \u0438\u0445 \u0431\u0443\u0434\u0435\u0442 <img decoding=\"async\" class=\"formula inline\" source=\"O(n^2)\" alt=\"O(n^2)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7fb\/1dc\/11e\/7fb1dc11e02acb70004a96d895e6cfe9.svg\"> \u0448\u0442\u0443\u043a. \u0412 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u0438, \u0447\u0442\u043e &#171;\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438&#187; \u0440\u0430\u0432\u043d\u0430 2 (\u0442.\u0435. \u043f\u0440\u0435\u0434\u0438\u043a\u0430\u0442\u044b \u043a\u0430\u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c \u0434\u0432\u0443\u0445\u043c\u0435\u0441\u0442\u043d\u044b\u0435) \u0438 \u0435\u0451 \u0440\u0430\u043d\u0433 \u0442\u043e\u0436\u0435 \u0440\u0430\u0432\u0435\u043d 2 (\u0442.\u0435. \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u0432\u044b\u0432\u043e\u0434\u0430 \u0434\u043e\u043f\u0443\u0441\u043a\u0430\u044e\u0442 \u043a\u043e\u043d\u043a\u0430\u0442\u0435\u043d\u0430\u0446\u0438\u044e \u043a\u0430\u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c \u0434\u0432\u0443\u0445 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445) \u2014 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c, \u0447\u0442\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c CYK-\u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u0431\u0443\u0434\u0435\u0442 <img decoding=\"async\" class=\"formula inline\" source=\"O(n^6)\" alt=\"O(n^6)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/31a\/c2a\/0d9\/31ac2a0d9bc179e5ce7872a585bcaff5.svg\">.<\/p>\n<p>\u0410 \u0435\u0441\u043b\u0438 \u0440\u0430\u043d\u0433 \u0432\u044b\u0448\u0435, \u043a\u0430\u043a \u0432 \u0432\u044b\u0448\u0435\u043f\u0440\u0438\u0432\u0435\u0434\u0451\u043d\u043d\u043e\u0439 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0435, \u0433\u0434\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u043e <code>VP(X,YZW) \u2190 NP(X),V(Z),CP(Y,W)<\/code> \u0432\u043a\u043b\u044e\u0447\u0430\u0435\u0442 \u043a\u043e\u043d\u043a\u0430\u0442\u0435\u043d\u0430\u0446\u0438\u044e \u0442\u0440\u0451\u0445 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445? \u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0438\u0435 \u0434\u043b\u044f V \u0443\u0437\u043b\u044b \u0431\u0443\u0434\u0443\u0442 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c\u0441\u044f \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c (CP, ?, start<sub>Z<\/sub>, end<sub>Z<\/sub>, ?) \u0438 (NP, ?, ?, \u2205, \u2205), \u0442\u0430\u043a \u0447\u0442\u043e \u0438\u0445 \u0431\u0443\u0434\u0435\u0442 \u0443\u0436\u0435 <img decoding=\"async\" class=\"formula inline\" source=\"O(n^4)\" alt=\"O(n^4)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/813\/fe0\/c94\/813fe0c94f0c496a0cb92f12126af68b.svg\"> \u0448\u0442\u0443\u043a. \u0410\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e, \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0438\u0435 \u0434\u043b\u044f NP \u0443\u0437\u043b\u044b \u0431\u0443\u0434\u0443\u0442 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c\u0441\u044f \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c (CP, ?, ?, ?, ?) \u0438 (V, end<sub>Y<\/sub>, start<sub>W<\/sub>, \u2205, \u2205), \u0438 \u0438\u0445 \u0442\u043e\u0436\u0435 \u0431\u0443\u0434\u0435\u0442<img decoding=\"async\" class=\"formula inline\" source=\"O(n^4)\" alt=\"O(n^4)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/813\/fe0\/c94\/813fe0c94f0c496a0cb92f12126af68b.svg\"> \u0448\u0442\u0443\u043a. \u041f\u043e\u043b\u0443\u0447\u0430\u044e\u0442\u0441\u044f <img decoding=\"async\" class=\"formula inline\" source=\"O(n^4)\" alt=\"O(n^4)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/10c\/494\/d92\/10c494d928f1a778b2f449281ccb87ce.svg\"> \u0448\u0430\u0433\u043e\u0432 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c\u044e <img decoding=\"async\" class=\"formula inline\" source=\"O(n^4)\" alt=\"O(n^4)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/10c\/494\/d92\/10c494d928f1a778b2f449281ccb87ce.svg\"> \u043a\u0430\u0436\u0434\u044b\u0439. \u041e\u0433\u0440\u043e\u043c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0431\u0435\u0441\u043f\u043e\u043b\u0435\u0437\u043d\u044b\u0445 \u0448\u0430\u0433\u043e\u0432 \u0437\u0430\u043c\u0435\u0442\u043d\u043e \u0438 \u0432 \u043f\u0440\u0438\u0432\u0435\u0434\u0451\u043d\u043d\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u0440\u0430\u0437\u0431\u043e\u0440\u0430: \u0432 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0438, \u0433\u0434\u0435 \u0442\u0440\u0438 NP \u0438 \u0434\u0432\u0430 V, \u0438\u0437 \u043a\u0430\u0436\u0434\u043e\u0439 \u0438\u0445 \u043f\u043e\u043f\u0430\u0440\u043d\u043e\u0439 \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0446\u0438\u0438 \u0432\u044b\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u043f\u043e \u0443\u0437\u043b\u0443 VP \u0438 CP.<\/p>\n<p>\u0412 \u0446\u0435\u043b\u043e\u043c \u043c\u043e\u0436\u043d\u043e \u0432\u0438\u0434\u0435\u0442\u044c, \u0447\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u043e\u0441\u0442\u0430\u0451\u0442\u0441\u044f \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u043c, \u043d\u043e \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0431\u044b\u0441\u0442\u0440\u043e \u0440\u0430\u0441\u0442\u0451\u0442 \u043f\u043e \u043c\u0435\u0440\u0435 \u0443\u0441\u043b\u043e\u0436\u043d\u0435\u043d\u0438\u044f \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438: \u043e\u0431\u043e\u0431\u0449\u0430\u044f \u043f\u0440\u0438\u0432\u0435\u0434\u0451\u043d\u043d\u044b\u0435 \u0440\u0430\u0441\u0441\u0443\u0436\u0434\u0435\u043d\u0438\u044f, \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c <img decoding=\"async\" class=\"formula inline\" source=\"O(n^{d\\cdot(r+1)})\" alt=\"O(n^{d\\cdot(r+1)})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cbf\/c5f\/3a0\/cbfc5f3a0fb80b6f280afd824d520dce.svg\">, \u0433\u0434\u0435&nbsp;<img decoding=\"async\" class=\"formula inline\" source=\"d\" alt=\"d\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/122\/451\/988\/122451988aec6755d79ac114b6839cec.svg\">&nbsp;\u2014 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438. \u042d\u0442\u043e \u0437\u043d\u0430\u0447\u0438\u0442, \u0447\u0442\u043e \u0440\u0430\u0437\u0431\u043e\u0440 \u043c\u043e\u0436\u043d\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0443\u043f\u0440\u043e\u0441\u0442\u0438\u0442\u044c, \u0437\u0430\u043c\u0435\u043d\u044f\u044f \u043a\u043e\u043d\u043a\u0430\u0442\u0435\u043d\u0430\u0446\u0438\u044e \u0431\u043e\u043b\u0435\u0435 \u0447\u0435\u043c \u0434\u0432\u0443\u0445 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u043d\u0430 \u043d\u043e\u0432\u044b\u0439 \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u043f\u0440\u0430\u0432\u0438\u043b\u043e  <code>VP(X,YZW) \u2190 NP(X),V(Z),CP(Y,W)<\/code> \u043d\u0430 \u043f\u0430\u0440\u0443 \u043f\u0440\u0430\u0432\u0438\u043b <code>CP'(Y,ZW) \u2190 V(Z),CP(Y,W); VP(X,YZ) \u2190 NP(X),CP'(Y,Z)<\/code>. \u041f\u043e\u043b\u0443\u0447\u0435\u043d\u043d\u043e\u0435 \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0434\u0435\u0440\u0435\u0432\u043e \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u0434\u0430\u043b\u044c\u0448\u0435 \u043e\u0442 \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u044f, \u043d\u043e \u0442\u0435\u043c \u043d\u0435 \u043c\u0435\u043d\u0435\u0435, \u0442\u0430\u043a\u0430\u044f &#171;\u043d\u043e\u0440\u043c\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f&#187; \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a \u0448\u0438\u0440\u043e\u043a\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f.<\/p>\n<p>\u041a\u0430\u043a \u043e\u0442\u043c\u0435\u0447\u0430\u043b\u043e\u0441\u044c \u0432 \u0447.1, \u0442\u0435\u043a\u0441\u0442\u044b \u043d\u0430 \u0435\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0445 \u044f\u0437\u044b\u043a\u0430\u0445 \u0447\u0430\u0441\u0442\u043e \u0434\u043e\u043f\u0443\u0441\u043a\u0430\u044e\u0442 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0440\u0430\u0437\u0431\u043e\u0440\u043e\u0432, \u0438 \u0441\u0440\u0435\u0434\u0438 \u044d\u0442\u0438\u0445 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0440\u0430\u0437\u0431\u043e\u0440\u043e\u0432 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0432\u044b\u0431\u0440\u0430\u0442\u044c \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u044b\u0439. \u0421\u0430\u043c\u043e\u0435 \u043b\u043e\u0431\u043e\u0432\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u2014 \u044d\u0442\u043e \u043f\u0440\u0438\u0441\u0432\u043e\u0438\u0442\u044c \u043a\u0430\u0436\u0434\u043e\u043c\u0443 \u043f\u0440\u0430\u0432\u0438\u043b\u0443 \u0432\u044b\u0432\u043e\u0434\u0430 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, <code>VP(X,Y) \u2190 75% NP(X),V(Y); VP(X,YZW) \u2190 25% NP(X),V(Z),CP(Y,W)<\/code> \u2014 \u0442\u0430\u043a\u0443\u044e \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u043d\u0443\u044e \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0443 \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442 PMCFG), \u0438 \u0442\u043e\u0433\u0434\u0430 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u2014 \u044d\u0442\u043e \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u0435\u0439 \u0432\u0441\u0435\u0445 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0432 \u043d\u0451\u043c \u043f\u0440\u0430\u0432\u0438\u043b \u0432\u044b\u0432\u043e\u0434\u0430. \u041d\u0430\u043c\u043d\u043e\u0433\u043e \u0443\u0434\u043e\u0431\u043d\u0435\u0435, \u0447\u0435\u043c \u0441 \u043c\u0438\u043a\u0440\u043e\u0441\u043a\u043e\u043f\u0438\u0447\u0435\u0441\u043a\u0438\u043c\u0438 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044f\u043c\u0438, \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0441 \u0438\u0445 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u0430\u043c\u0438: \u0442\u043e\u0433\u0434\u0430 \u043f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u0435\u0439 \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0441\u043b\u043e\u0436\u0435\u043d\u0438\u0435\u043c \u0438\u0445 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u043e\u0432.<\/p>\n<p>\u0412 \u0437\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435 \u043f\u043e\u0434\u0435\u043b\u044e\u0441\u044c \u043c\u043e\u0435\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0435\u0439 CYK \u0434\u043b\u044f PMCFG \u043d\u0430 Python, \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c\u043e\u0439 (\u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043b\u043e\u0441\u044c \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0442\u044c \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0434\u043e 10 \u0441\u043b\u043e\u0432 \u0432 \u043f\u0440\u0435\u0434\u0435\u043b\u0430\u0445 5 \u0441\u0435\u043a\u0443\u043d\u0434) \u0434\u043b\u044f <img decoding=\"async\" class=\"formula inline\" source=\"d\\le2,\\ r\\le4\" alt=\"d\\le2,\\ r\\le4\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/20a\/36a\/ecb\/20a36aecb3bb0cb639fc6ddf9e98bdbd.svg\">, \u043d\u043e \u0441\u043f\u043e\u0441\u043e\u0431\u043d\u043e\u0439 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0438 \u0432\u043d\u0435 \u044d\u0442\u0438\u0445 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439. \u0412\u043c\u0435\u0441\u0442\u043e <img decoding=\"async\" class=\"formula inline\" source=\"2d+1\" alt=\"2d+1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/875\/023\/91e\/87502391e27c277c45ddbba67d866bc1.svg\">-\u043c\u0435\u0440\u043d\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0434\u043b\u044f \u0434\u043e\u0441\u043a\u0438 \u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e \u0434\u0432\u0443\u0445\u0443\u0440\u043e\u0432\u043d\u0435\u0432\u044b\u0439 <code>dict<\/code>, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043a\u043b\u044e\u0447\u0438 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0443\u0440\u043e\u0432\u043d\u044f \u2014 \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u044b, \u0432\u0442\u043e\u0440\u043e\u0433\u043e \u2014 \u043e\u0431\u044a\u0435\u043a\u0442\u044b <code>Chunk<\/code>, \u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u2014 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u044b \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u0435\u0439. \u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0446\u0438\u0438 \u0438\u0437 \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u0430 \u0438 \u043d\u0430\u0431\u043e\u0440\u0430 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a \u043c\u043e\u0436\u0435\u0442 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0434\u0438\u043d \u044d\u043a\u0437\u0435\u043c\u043f\u043b\u044f\u0440 <code>Chunk<\/code>, \u0442\u0430\u043a \u0447\u0442\u043e \u0434\u043b\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0441\u0440\u0430\u0432\u043d\u0438\u0442\u044c \u0438\u0445 <code>id<\/code> \u2014 \u044d\u0442\u043e \u043c\u043d\u043e\u0433\u043e\u043a\u0440\u0430\u0442\u043d\u043e \u0443\u0441\u043a\u043e\u0440\u044f\u0435\u0442 \u043f\u043e\u0438\u0441\u043a \u0432 <code>dict<\/code> \u043f\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044e \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043a\u043b\u044e\u0447\u0430 \u043e\u0431\u044b\u0447\u043d\u043e\u0439 \u0437\u0430\u043f\u0438\u0441\u0438 (data class).<\/p>\n<pre><code class=\"python\">class Chunk:     instances = {}     def __new__(cls, symbol, inputs):         key = symbol, tuple(inputs)         i = cls.instances.get(key)         if i:            return i         i = super(Chunk, cls).__new__(cls)         i.symbol = symbol         i.inputs = inputs         cls.instances[key] = i         return i   def parse(grammar, string):     chart = {n: {} for n in grammar.non_terminals}     agenda = {Chunk(rule.left.symbol, [(i, i + 1)]): rule.prob               for i in range(len(string)) for rule in grammar.rules               if rule.terminating and rule.left.inputs[0] == string[i]}     goal = Chunk(grammar.start, [(0, len(string))])     while agenda and goal not in chart[grammar.start]:         (best, prob) = max(agenda.items(), key=lambda x: x[1])         chart[best.symbol][best] = prob         del agenda[best]         for rule in grammar.rules:             if not rule.terminating and any(best.symbol == prod.symbol for prod in rule.right):                 right = list(rule.right)                 for perm in itertools.product(*(chart[prod.symbol].keys() for prod in right)):                     if best in perm:                         sat = satisfies(perm, rule.left, right, chart)                         if sat is not None:                             chunk = sat[0]                             new_prob = sat[1] + rule.prob                             if (chunk not in chart[chunk.symbol]) and \\                                ((chunk not in agenda) or (agenda[chunk] != new_prob)):                                 agenda[chunk] = new_prob     return chart[grammar.start].get(goal)   def satisfies(perm, left, right, chart):     mapping = {}     prob = 0     for chunk, pred in zip(perm, right):         for c_i, p_i in zip(chunk.inputs, pred.inputs):             mapping[p_i] = c_i         prob += chart[chunk.symbol][chunk]     inputs = []     for r in left.inputs:         if len(r) == 1:             inputs.append(mapping[r])         else:             mapped = [mapping[c] for c in r]             for k in range(len(mapped) - 1):                 if mapped[k][1] != mapped[k + 1][0]:                     return None             inputs.append((mapped[0][0], mapped[-1][1]))     if len(inputs) &gt; 1:         for i in range(len(inputs) - 1):             if inputs[i][1] &gt; inputs[i + 1][0]:                 return None     return Chunk(left.symbol, inputs), prob <\/code><\/pre>\n<p>\u0421\u0430\u043c\u044b\u0435 \u0432\u043d\u0438\u043c\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0437\u0430\u043c\u0435\u0442\u044f\u0442, \u0447\u0442\u043e \u044d\u0442\u0430 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0434\u043e\u043f\u0443\u0441\u043a\u0430\u0435\u0442 \u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u044b \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u043f\u0440\u0430\u0432\u0438\u043b\u0430\u0445 \u0432\u0438\u0434\u0430 <code>N(t) \u2190 \u03b5<\/code>, \u043f\u043e \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0438 \u0441 CNF. \u042d\u0442\u043e \u043e\u0442\u0447\u0430\u0441\u0442\u0438 \u0434\u0430\u043d\u044c \u0442\u0440\u0430\u0434\u0438\u0446\u0438\u0438, \u043f\u0440\u0435\u0434\u043f\u0438\u0441\u044b\u0432\u0430\u044e\u0449\u0435\u0439 \u043a\u0430\u0442\u0435\u0433\u043e\u0440\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043a\u0430\u0436\u0434\u043e\u0435 \u0441\u043b\u043e\u0432\u043e \u043f\u0435\u0440\u0435\u0434 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435\u043c \u0441\u0438\u043d\u0442\u0430\u043a\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u0439 \u0441 \u0435\u0433\u043e \u0443\u0447\u0430\u0441\u0442\u0438\u0435\u043c.<\/p>\n<hr>\n<p>\u041e\u0431\u043b\u0430\u0447\u043d\u044b\u0435 \u0441\u0435\u0440\u0432\u0435\u0440\u044b \u043e\u0442 <a href=\"https:\/\/macloud.ru\/?partner=4189mjxpzx\">\u041c\u0430\u043a\u043b\u0430\u0443\u0434<\/a> \u0431\u044b\u0441\u0442\u0440\u044b\u0435 \u0438 \u0431\u0435\u0437\u043e\u043f\u0430\u0441\u043d\u044b\u0435.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/63d\/f6f\/640\/63df6f640f456a44dcb9f0618d9e3365.png\" width=\"1320\" height=\"300\"><figcaption><\/figcaption><\/figure>\n<p>\u0417\u0430\u0440\u0435\u0433\u0438\u0441\u0442\u0440\u0438\u0440\u0443\u0439\u0442\u0435\u0441\u044c \u043f\u043e \u0441\u0441\u044b\u043b\u043a\u0435 \u0432\u044b\u0448\u0435 \u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0435 10% \u0441\u043a\u0438\u0434\u043a\u0443 \u043d\u0430 \u043f\u0435\u0440\u0432\u044b\u0439 \u043c\u0435\u0441\u044f\u0446 \u0430\u0440\u0435\u043d\u0434\u044b \u0441\u0435\u0440\u0432\u0435\u0440\u0430 \u043b\u044e\u0431\u043e\u0439 \u043a\u043e\u043d\u0444\u0438\u0433\u0443\u0440\u0430\u0446\u0438\u0438!<\/p>\n<\/div>\n<p> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/company\/macloud\/blog\/560062\/\"> https:\/\/habr.com\/ru\/company\/macloud\/blog\/560062\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n<div class=\"post__text post__text_v2\" id=\"post-content-body\">\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p><a href=\"https:\/\/habr.com\/ru\/company\/macloud\/blog\/558760\/\">\u0427\u0430\u0441\u0442\u044c .1: \u042f\u0437\u044b\u043a\u0438 \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u044f \u044f\u0437\u044b\u043a\u043e\u0432<\/a><\/p>\n<p>\u0412 \u0438\u0434\u0435\u0430\u043b\u0435 \u043d\u0430\u043c \u0445\u043e\u0442\u0435\u043b\u043e\u0441\u044c \u0431\u044b \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0442\u044c \u0442\u0435\u043a\u0441\u0442 \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0438 \u0437\u0430 \u043e\u0434\u0438\u043d \u043f\u0440\u043e\u0445\u043e\u0434. \u0420\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u044b\u0435 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u044f \u044d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0442, \u043d\u043e \u0443\u0436\u0435 \u0441 CFG \u044d\u0442\u043e \u043d\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f: \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440,&nbsp;<code>S \u2192 A | B; A \u2192 a | x A; B \u2192 b | x B<\/code>&nbsp;\u043f\u0440\u0435\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0441\u0442\u0440\u043e\u043a\u0443&nbsp;<code>x\u2026xa<\/code>&nbsp;\u0432 \u0434\u0435\u0440\u0435\u0432\u043e \u0438\u0437 \u0443\u0437\u043b\u043e\u0432&nbsp;<code>A<\/code>, \u0430 \u0441\u0442\u0440\u043e\u043a\u0443&nbsp;<code>x\u2026xb<\/code>&nbsp;\u0432 \u0434\u0435\u0440\u0435\u0432\u043e \u0438\u0437 \u0443\u0437\u043b\u043e\u0432&nbsp;<code>B<\/code>&nbsp;\u2014 \u0438 \u043f\u043e\u043a\u0430 \u0440\u0430\u0437\u0431\u043e\u0440\u0449\u0438\u043a \u043d\u0435 \u0443\u0432\u0438\u0434\u0438\u0442 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u0441\u0442\u0440\u043e\u043a\u0438, \u043e\u043d \u043d\u0435 \u0437\u043d\u0430\u0435\u0442, \u0447\u0442\u043e \u0434\u0435\u043b\u0430\u0442\u044c \u0441\u043e \u0432\u0441\u0435\u043c\u0438 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u043c\u0438 \u0441\u0438\u043c\u0432\u043e\u043b\u0430\u043c\u0438. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u043d\u0430 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 \u0434\u043b\u044f \u044f\u0437\u044b\u043a\u043e\u0432 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043d\u0430\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u044e\u0442 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u2014 \u043f\u043e \u0441\u0443\u0442\u0438, \u0447\u0442\u043e\u0431\u044b \u0434\u043b\u044f \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u043d\u0435 \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u043b\u043e\u0441\u044c &#171;\u0437\u0430\u0433\u043b\u044f\u0434\u044b\u0432\u0430\u0442\u044c \u0432\u043f\u0435\u0440\u0451\u0434&#187; \u2014 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0449\u0438\u0435 \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0442\u044c \u0442\u0435\u043a\u0441\u0442 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b \u0437\u0430 \u043e\u0434\u0438\u043d \u043f\u0440\u043e\u0445\u043e\u0434. \u041a\u0442\u043e \u043a\u043e\u0432\u044b\u0440\u044f\u043b\u0441\u044f \u0432 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440\u0430\u0445, \u0442\u043e\u0442 \u043d\u0430\u0432\u0435\u0440\u043d\u044f\u043a\u0430 \u0437\u043d\u0430\u043a\u043e\u043c \u0441 LL- \u0438 LR-\u0440\u0430\u0437\u0431\u043e\u0440\u043e\u043c, \u0438 \u0438\u043c\u0435\u0435\u0442 \u043e\u043f\u044b\u0442 &#171;\u043f\u043e\u0434\u0433\u043e\u043d\u043a\u0438&#187; \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 \u044f\u0437\u044b\u043a\u0430 \u043f\u043e\u0434 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u044f \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0440\u0430\u0437\u0431\u043e\u0440\u0430. \u041d\u043e \u043f\u0440\u0438 \u0440\u0430\u0431\u043e\u0442\u0435 \u0441 \u0435\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u043c\u0438 \u044f\u0437\u044b\u043a\u0430\u043c\u0438 \u043d\u0435\u0442 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u0438 &#171;\u043f\u043e\u0434\u043f\u0440\u0430\u0432\u0438\u0442\u044c&#187; \u044f\u0437\u044b\u043a \u0434\u043b\u044f \u0443\u0434\u043e\u0431\u0441\u0442\u0432\u0430 \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u2014 \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0441 \u0442\u0435\u043c \u044f\u0437\u044b\u043a\u043e\u043c, \u043a\u0430\u043a\u043e\u0439 \u0435\u0441\u0442\u044c.<\/p>\n<p>\u0412 1960-\u0445 \u0431\u044b\u043b \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043d \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c CYK \u0434\u043b\u044f \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0433\u043e CFG. \u0421\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u0432\u043f\u0435\u0440\u0432\u044b\u0435 \u0435\u0433\u043e \u043e\u043f\u0443\u0431\u043b\u0438\u043a\u043e\u0432\u0430\u043b\u0438 \u2014 \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e \u0434\u0440\u0443\u0433 \u043e\u0442 \u0434\u0440\u0443\u0433\u0430 \u2014 \u0418. \u0421\u0430\u043a\u0430\u0438 \u0438\u0437 \u044f\u043f\u043e\u043d\u0441\u043a\u043e\u0433\u043e \u041d\u0418\u0418 \u041c\u0438\u043d\u043e\u0431\u043e\u0440\u043e\u043d\u044b \u0432 1961 \u0438 \u0414\u0436. \u041a\u043e\u043a \u0438\u0437 \u041d\u044c\u044e-\u0419\u043e\u0440\u043a\u0441\u043a\u043e\u0433\u043e \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442\u0430 \u0432 1962. \u0412 1966 \u0442\u043e\u0442 \u0436\u0435 \u0441\u0430\u043c\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u0443\u0431\u043b\u0438\u043a\u043e\u0432\u0430\u043b\u0438 \u2014 \u043e\u043f\u044f\u0442\u044c \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e \u2014 \u0414. \u042f\u043d\u0433\u0435\u0440 \u0438\u0437 General Electric \u0438 \u0422. \u041a\u0430\u0441\u0430\u043c\u0438 \u0438\u0437 \u0423\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442\u0430 \u0418\u043b\u043b\u0438\u043d\u043e\u0439\u0441\u0430. \u042f\u043d\u0433\u0435\u0440 \u0432 \u0441\u0432\u043e\u0435\u0439 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0438 \u0443\u043f\u043e\u043c\u0438\u043d\u0430\u0435\u0442 \u0438\u043c\u0435\u043d\u0430 \u041a\u043e\u043a\u0430 \u0438 \u0421\u0430\u043a\u0430\u0438, \u043d\u043e \u043d\u0435 \u0441\u0441\u044b\u043b\u0430\u0435\u0442\u0441\u044f \u043d\u0438 \u043d\u0430 \u043a\u0430\u043a\u0438\u0435 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u044b\u0435 \u0438\u0445 \u0440\u0430\u0431\u043e\u0442\u044b: \u043f\u043e \u0432\u0441\u0435\u0439 \u0432\u0438\u0434\u0438\u043c\u043e\u0441\u0442\u0438, \u0440\u0430\u0431\u043e\u0442\u044b \u041a\u043e\u043a\u0430 \u0438 \u0421\u0430\u043a\u0430\u0438 \u042f\u043d\u0433\u0435\u0440\u0443 \u2014 \u043a\u0430\u043a \u0438 \u043c\u043d\u0435 \u0441\u0435\u0439\u0447\u0430\u0441 \u2014 \u043d\u0435 \u0431\u044b\u043b\u0438 \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u044b. \u0427\u0442\u043e\u0431\u044b \u043d\u0438\u043a\u043e\u043c\u0443 \u0438\u0437 \u0438\u0437\u043e\u0431\u0440\u0435\u0442\u0430\u0442\u0435\u043b\u0435\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043d\u0435 \u0431\u044b\u043b\u043e \u043e\u0431\u0438\u0434\u043d\u043e, \u0435\u0433\u043e \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442 \u0432 \u0447\u0435\u0441\u0442\u044c \u0441\u0440\u0430\u0437\u0443 \u0442\u0440\u043e\u0438\u0445, \u0445\u043e\u0442\u044f \u043e\u043d\u0438, \u0441\u043a\u043e\u0440\u0435\u0435 \u0432\u0441\u0435\u0433\u043e, \u0434\u0430\u0436\u0435 \u043d\u0435 \u0431\u044b\u043b\u0438 \u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0431\u043e\u0439 \u0437\u043d\u0430\u043a\u043e\u043c\u044b.<\/p>\n<p>\u0418\u0434\u0435\u044f CYK \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0440\u0430\u0437\u0431\u043e\u0440\u0435 &#171;\u0441\u043d\u0438\u0437\u0443 \u0432\u0432\u0435\u0440\u0445&#187; \u2014 \u043e\u0442 \u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u043e\u0432 \u043a S \u2014 \u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0438 \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 \u0434\u043b\u044f \u0438\u0437\u0431\u0435\u0436\u0430\u043d\u0438\u044f \u043f\u043e\u0432\u0442\u043e\u0440\u043d\u044b\u0445 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439: \u0432\u043d\u0430\u0447\u0430\u043b\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u043c \u0432\u0441\u0435 \u0443\u0437\u043b\u044b, \u0432\u044b\u0432\u043e\u0434\u0438\u043c\u044b\u0435 \u043d\u0435\u043f\u043e\u0441\u0440\u0435\u0434\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0438\u0437 \u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u043e\u0432, \u0438 \u043f\u043e\u043c\u0435\u0441\u0442\u0438\u043c \u0438\u0445 \u043d\u0430 &#171;\u0434\u043e\u0441\u043a\u0443&#187;. \u041d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0432\u043e\u0437\u044c\u043c\u0451\u043c \u0441 \u0434\u043e\u0441\u043a\u0438 \u043e\u0434\u0438\u043d \u0443\u0437\u0435\u043b, \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u043c \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u0443\u0437\u043b\u044b \u0441 \u0435\u0433\u043e \u0443\u0447\u0430\u0441\u0442\u0438\u0435\u043c, \u0438 \u0434\u043e\u0431\u0430\u0432\u0438\u043c \u043d\u0430 \u0434\u043e\u0441\u043a\u0443 \u0435\u0449\u0451 \u0438 \u0438\u0445. \u0415\u0441\u043b\u0438 \u043d\u0430 \u0434\u043e\u0441\u043a\u0435 \u043f\u043e\u044f\u0432\u0438\u043b\u0441\u044f S \u0434\u043b\u044f \u0432\u0441\u0435\u0433\u043e \u0442\u0435\u043a\u0441\u0442\u0430 \u0446\u0435\u043b\u0438\u043a\u043e\u043c, \u0437\u043d\u0430\u0447\u0438\u0442 \u0440\u0430\u0437\u0431\u043e\u0440 \u0443\u0434\u0430\u043b\u0441\u044f; \u0435\u0441\u043b\u0438 \u0432\u0441\u0435 \u0443\u0437\u043b\u044b \u0441 \u0434\u043e\u0441\u043a\u0438 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u044b, \u043d\u043e S \u0442\u0430\u043c \u0442\u0430\u043a \u0438 \u043d\u0435 \u043f\u043e\u044f\u0432\u0438\u043b\u0441\u044f \u2014 \u0437\u043d\u0430\u0447\u0438\u0442, \u0440\u0430\u0437\u0431\u043e\u0440 \u043d\u0435 \u0443\u0434\u0430\u043b\u0441\u044f. \u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u044f \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043f\u0440\u0438\u043c\u0435\u0440\u0430 \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0435\u0442 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0435 &#171;<em>She eats the fish with a fork.<\/em>&#187; \u043f\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0435:<\/p>\n<pre><code class=\"vala\">S \u2192 NP VP VP \u2192 VP PP | V NP | V PP \u2192 P NP NP \u2192 Det N | she V \u2192 eats P \u2192 with N \u2192 fish | fork Det \u2192 a | the<\/code><\/pre>\n<div>\n<div class=\"table\">\n<table>\n<tbody>\n<tr>\n<td>\n<p>\u0428\u0430\u0433<\/p>\n<\/td>\n<td>\n<p>\u041d\u0435\u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0435 \u0443\u0437\u043b\u044b \u043d\u0430 \u0434\u043e\u0441\u043a\u0435<\/p>\n<\/td>\n<td>\n<p>\u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0435 \u0443\u0437\u043b\u044b \u043d\u0430 \u0434\u043e\u0441\u043a\u0435<\/p>\n<\/td>\n<td>\n<p>\u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c\u044b\u0435 \u043d\u0430 \u0434\u043e\u0441\u043a\u0443 \u0443\u0437\u043b\u044b<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>1<\/p>\n<\/td>\n<td>\n<\/td>\n<td>\n<\/td>\n<td>\n<p><em>She<\/em><sub>NP<\/sub><em>, eats<\/em><sub>V<\/sub><em>, the<\/em><sub>Det<\/sub><em>, fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>2<\/p>\n<\/td>\n<td>\n<p><strong><em>She<\/em><sub>NP<\/sub><\/strong><em>, eats<\/em><sub>V<\/sub><em>, the<\/em><sub>Det<\/sub><em>, fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub><\/p>\n<\/td>\n<td>\n<\/td>\n<td>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>3<\/p>\n<\/td>\n<td>\n<p><strong><em>eats<\/em><sub>V<\/sub><\/strong><em>, the<\/em><sub>Det<\/sub><em>, fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub><\/p>\n<\/td>\n<td>\n<p><em>She<\/em><sub>NP<\/sub><\/p>\n<\/td>\n<td>\n<p><em>eats<\/em><sub>VP<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>4<\/p>\n<\/td>\n<td>\n<p><strong><em>the<\/em><sub>Det<\/sub><\/strong><em>, fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub>,&nbsp;<em>eats<\/em><sub>VP<\/sub><\/p>\n<\/td>\n<td>\n<p><em>She<\/em><sub>NP<\/sub><em>, eats<\/em><sub>V<\/sub><\/p>\n<\/td>\n<td>\n<p>[<em>the fish<\/em>]<sub>NP<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>5, 6<\/p>\n<\/td>\n<td>\n<p><strong><em>fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><\/strong><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub>,&nbsp;<em>eats<\/em><sub>VP<\/sub>, [<em>the fish<\/em>]<sub>NP<\/sub><\/p>\n<\/td>\n<td>\n<p><em>She<\/em><sub>NP<\/sub><em>, eats<\/em><sub>V<\/sub><em>, the<\/em><sub>Det<\/sub><\/p>\n<\/td>\n<td>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>7<\/p>\n<\/td>\n<td>\n<p><strong><em>a<\/em><sub>Det<\/sub><\/strong><em>, fork<\/em><sub>N<\/sub>,&nbsp;<em>eats<\/em><sub>VP<\/sub>, [<em>the fish<\/em>]<sub>NP<\/sub><\/p>\n<\/td>\n<td>\n<p><em>She<\/em><sub>NP<\/sub><em>, eats<\/em><sub>V<\/sub><em>, the<\/em><sub>Det<\/sub><em>, fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><\/p>\n<\/td>\n<td>\n<p>[<em>a fork<\/em>]<sub>NP<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>8<\/p>\n<\/td>\n<td>\n<p><strong><em>fork<\/em><sub>N<\/sub><\/strong>,&nbsp;<em>eats<\/em><sub>VP<\/sub>, [<em>the fish<\/em>]<sub>NP<\/sub>, [<em>a fork<\/em>]<sub>NP<\/sub><\/p>\n<\/td>\n<td>\n<p><em>She<\/em><sub>NP<\/sub><em>, eats<\/em><sub>V<\/sub><em>, the<\/em><sub>Det<\/sub><em>, fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><em>, a<\/em><sub>Det<\/sub><\/p>\n<\/td>\n<td>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>9<\/p>\n<\/td>\n<td>\n<p><strong><em>eats<\/em><sub>VP<\/sub><\/strong>, [<em>the fish<\/em>]<sub>NP<\/sub>, [<em>a fork<\/em>]<sub>NP<\/sub><\/p>\n<\/td>\n<td>\n<p><strong><em>She<\/em><sub>NP<\/sub><\/strong><em>, eats<\/em><sub>V<\/sub><em>, the<\/em><sub>Det<\/sub><em>, fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub><\/p>\n<\/td>\n<td>\n<p>[<em>She eats<\/em>]<sub>S<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>10<\/p>\n<\/td>\n<td>\n<p><strong>[<em>the fish<\/em>]<sub>NP<\/sub><\/strong>, [<em>a fork<\/em>]<sub>NP<\/sub>, [<em>She eats<\/em>]<sub>S<\/sub><\/p>\n<\/td>\n<td>\n<p><em>She<\/em><sub>NP<\/sub><em>,&nbsp;<\/em><strong><em>eats<\/em><sub>V<\/sub><\/strong><em>, the<\/em><sub>Det<\/sub><em>, fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub><em>, eats<\/em><sub>VP<\/sub><\/p>\n<\/td>\n<td>\n<p>[<em>eats the fish<\/em>]<sub>VP<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>11<\/p>\n<\/td>\n<td>\n<p><strong>[<em>a fork<\/em>]<sub>NP<\/sub><\/strong>, [<em>She eats<\/em>]<sub>S<\/sub>, [<em>eats the fish<\/em>]<sub>VP<\/sub><\/p>\n<\/td>\n<td>\n<p><em>She<\/em><sub>NP<\/sub>,<em>&nbsp;eats<\/em><sub>V<\/sub>,<em>&nbsp;the<\/em><sub>Det<\/sub>,<em>&nbsp;fish<\/em><sub>N<\/sub><em>,&nbsp;<\/em><strong><em>with<\/em><sub>P<\/sub><\/strong><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub><em>, eats<\/em><sub>VP<\/sub>,<em>&nbsp;<\/em>[<em>the fish<\/em>]<sub>NP<\/sub><\/p>\n<\/td>\n<td>\n<p>[<em>with a fork<\/em>]<sub>PP<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>12<\/p>\n<\/td>\n<td>\n<p><strong>[<em>She eats<\/em>]<sub>S<\/sub><\/strong>, [<em>eats the fish<\/em>]<sub>VP<\/sub>, [<em>with a fork<\/em>]<sub>PP<\/sub><\/p>\n<\/td>\n<td>\n<p><em>She<\/em><sub>NP<\/sub>,<em>&nbsp;eats<\/em><sub>V<\/sub>,<em>&nbsp;the<\/em><sub>Det<\/sub>,<em>&nbsp;fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub><em>, eats<\/em><sub>VP<\/sub>,<em>&nbsp;<\/em><strong>[<em>the fish<\/em>]<sub>NP<\/sub><\/strong>, [<em>a fork<\/em>]<sub>NP<\/sub><\/p>\n<\/td>\n<td>\n<p>[<em>She eats the fish<\/em>]<sub>S<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>13<\/p>\n<\/td>\n<td>\n<p><strong>[<em>eats the fish<\/em>]<sub>VP<\/sub><\/strong>, [<em>with a fork<\/em>]<sub>PP<\/sub>, [<em>She eats the fish<\/em>]<sub>S<\/sub><\/p>\n<\/td>\n<td>\n<p><em>She<\/em><sub>NP<\/sub>,<em>&nbsp;eats<\/em><sub>V<\/sub>,<em>&nbsp;the<\/em><sub>Det<\/sub>,<em>&nbsp;fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub><em>, eats<\/em><sub>VP<\/sub>,<em>&nbsp;<\/em>[<em>the fish<\/em>]<sub>NP<\/sub>, [<em>a fork<\/em>]<sub>NP,&nbsp;<\/sub>[<em>She eats<\/em>]<sub>S<\/sub><\/p>\n<\/td>\n<td>\n<p>[<em>eats the fish with a fork<\/em>]<sub>VP<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>14, 15<\/p>\n<\/td>\n<td>\n<p><strong>[<em>with a fork<\/em>]<sub>PP<\/sub>, [<em>She eats the fish<\/em>]<sub>S<\/sub><\/strong>, [<em>eats the fish with a fork<\/em>]<sub>VP<\/sub><\/p>\n<\/td>\n<td>\n<p><em>She<\/em><sub>NP<\/sub>,<em>&nbsp;eats<\/em><sub>V<\/sub>,<em>&nbsp;the<\/em><sub>Det<\/sub>,<em>&nbsp;fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub><em>, eats<\/em><sub>VP<\/sub>,<em>&nbsp;<\/em>[<em>the fish<\/em>]<sub>NP<\/sub>, [<em>a fork<\/em>]<sub>NP,&nbsp;<\/sub>[<em>She eats<\/em>]<sub>S<\/sub>, [<em>eats the fish with a fork<\/em>]<sub>VP<\/sub><\/p>\n<\/td>\n<td>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>16<\/p>\n<\/td>\n<td>\n<p><strong>[<em>eats the fish with a fork<\/em>]<sub>VP<\/sub><\/strong><\/p>\n<\/td>\n<td>\n<p><strong><em>She<\/em><sub>NP<\/sub><\/strong>,<em>&nbsp;eats<\/em><sub>V<\/sub>,<em>&nbsp;the<\/em><sub>Det<\/sub>,<em>&nbsp;fish<\/em><sub>N<\/sub><em>, with<\/em><sub>P<\/sub><em>, a<\/em><sub>Det<\/sub><em>, fork<\/em><sub>N<\/sub><em>, eats<\/em><sub>VP<\/sub>,<em>&nbsp;<\/em>[<em>the fish<\/em>]<sub>NP<\/sub>, [<em>a fork<\/em>]<sub>NP,&nbsp;<\/sub>[<em>She eats<\/em>]<sub>S<\/sub>, [<em>eats the fish with a fork<\/em>]<sub>VP<\/sub>, [<em>with a fork<\/em>]<sub>PP<\/sub>, [<em>She eats the fish<\/em>]<sub>S<\/sub><\/p>\n<\/td>\n<td>\n<p><strong>[<em>She eats the fish with a fork<\/em>]<sub>S<\/sub><\/strong><\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<p>\u041a\u0430\u043a\u043e\u0432\u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c CYK \u0434\u043b\u044f CFG? \u041d\u0430 \u0434\u043e\u0441\u043a\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043a\u0430\u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c&nbsp;&nbsp;\u0443\u0437\u043b\u043e\u0432 \u2014 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0438 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 \u0432\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0442\u0435\u043a\u0441\u0442\u0430; \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0434\u043e\u0441\u043a\u0443 \u0443\u0434\u043e\u0431\u043d\u043e \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432 \u0432\u0438\u0434\u0435 \u0442\u0440\u0451\u0445\u043c\u0435\u0440\u043d\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430, \u0438\u043d\u0434\u0435\u043a\u0441\u044b \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u2014 \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b, \u043d\u0430\u0447\u0430\u043b\u043e \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 \u0438 \u043a\u043e\u043d\u0435\u0446 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438. \u041d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0435 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043e\u0434\u0438\u043d \u0443\u0437\u0435\u043b \u0441 \u0434\u043e\u0441\u043a\u0438 \u2014 \u0437\u043d\u0430\u0447\u0438\u0442, \u0434\u043b\u044f \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u044e\u0442\u0441\u044f&nbsp;&nbsp;\u0448\u0430\u0433\u043e\u0432. \u041d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u044e\u0442\u0441\u044f \u0432\u0441\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438, \u0438 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043f\u0440\u0430\u0432\u0438\u043b\u0430, \u0433\u0434\u0435 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u043c\u044b\u0439 \u0443\u0437\u0435\u043b \u043f\u043e\u0434\u0445\u043e\u0434\u0438\u0442 \u043f\u043e\u0434 \u043f\u0440\u0430\u0432\u0443\u044e \u0447\u0430\u0441\u0442\u044c, \u0431\u0443\u0434\u0443\u0442 \u043f\u0440\u043e\u0432\u0435\u0440\u0435\u043d\u044b \u0432\u0441\u0435 \u0443\u0437\u043b\u044b \u0441 \u0434\u043e\u0441\u043a\u0438, \u043c\u043e\u0433\u0443\u0449\u0438\u0435 \u0443\u0447\u0430\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u0432 \u043f\u0440\u0430\u0432\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u0432\u043c\u0435\u0441\u0442\u0435 \u0441 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u043c\u044b\u043c \u0443\u0437\u043b\u043e\u043c. \u041e\u0441\u0442\u0430\u043b\u043e\u0441\u044c \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0442\u0430\u043a\u043e\u0433\u043e \u0448\u0430\u0433\u0430.<\/p>\n<p>\u0418\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c CYK \u0440\u0430\u0431\u043e\u0442\u0430\u043b \u0441 CFG \u0432&nbsp;<a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9D%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D0%B0_%D0%A5%D0%BE%D0%BC%D1%81%D0%BA%D0%BE%D0%B3%D0%BE\"><em>\u043d\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0444\u043e\u0440\u043c\u0435&nbsp;\u0425\u043e\u043c\u0441\u043a\u043e\u0433\u043e<\/em><\/a>&nbsp;(CNF) \u2014 \u0432 \u043f\u0440\u0430\u0432\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u0432\u044b\u0432\u043e\u0434\u0430 \u0434\u043e\u043f\u0443\u0441\u043a\u0430\u043b\u0438\u0441\u044c \u043b\u0438\u0431\u043e \u043e\u0434\u0438\u043d \u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b, \u043b\u0438\u0431\u043e \u0434\u0432\u0430 \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u0430. \u0414\u043b\u044f \u043f\u0440\u0430\u0432\u0438\u043b\u0430&nbsp;<code>A \u2192 BC<\/code>&nbsp;&#171;\u0432\u0441\u0435 \u0443\u0437\u043b\u044b \u0441 \u0434\u043e\u0441\u043a\u0438, \u043c\u043e\u0433\u0443\u0449\u0438\u0435 \u0443\u0447\u0430\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u0432 \u043f\u0440\u0430\u0432\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u0432\u043c\u0435\u0441\u0442\u0435 \u0441 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u043c\u044b\u043c \u0443\u0437\u043b\u043e\u043c&#187; \u2014 \u044d\u0442\u043e \u043a\u0430\u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c&nbsp;&nbsp;\u0443\u0437\u043b\u043e\u0432 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c\u0438 (C, end<sub>B<\/sub>, ?) \u0438\/\u0438\u043b\u0438 \u043a\u0430\u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c&nbsp;&nbsp;\u0443\u0437\u043b\u043e\u0432 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c\u0438 (B, ?, start<sub>C<\/sub>). (\u0415\u0441\u043b\u0438 B=C, \u0442\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0442 \u043e\u0431\u0430 \u043d\u0430\u0431\u043e\u0440\u0430 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432.) \u041f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043e\u0434\u043d\u043e\u0433\u043e \u0448\u0430\u0433\u0430 CYK \u0434\u043b\u044f CNF \u2014 \u044d\u0442\u043e&nbsp;, \u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0432\u0441\u0435\u0433\u043e \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u2014 \u044d\u0442\u043e&nbsp;.<\/p>\n<p>\u0410 \u0435\u0441\u043b\u0438 CFG \u043d\u0435 \u0432 CNF? \u0414\u043b\u044f \u043f\u0440\u0430\u0432\u0438\u043b\u0430&nbsp;<code>A \u2192 BCD<\/code>&nbsp;\u043f\u0440\u0438\u0434\u0451\u0442\u0441\u044f \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c:<\/p>\n<ul>\n<li>\n<p>\u043a\u0430\u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c&nbsp;&nbsp;\u0443\u0437\u043b\u043e\u0432 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c\u0438 (C, end<sub>B<\/sub>, ?), \u0438 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0438\u0437 \u043d\u0438\u0445 \u2014 \u043a\u0430\u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c&nbsp;&nbsp;\u0443\u0437\u043b\u043e\u0432 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c\u0438 (D, end<sub>C<\/sub>, ?);<\/p>\n<\/li>\n<li>\n<p>\u043a\u0430\u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c&nbsp;&nbsp;\u043f\u0430\u0440 \u0443\u0437\u043b\u043e\u0432 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c\u0438 (B, ?, start<sub>C<\/sub>), \u0438 (D, end<sub>C<\/sub>, ?);<\/p>\n<\/li>\n<li>\n<p>\u043a\u0430\u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c&nbsp;&nbsp;\u0443\u0437\u043b\u043e\u0432 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c\u0438 (C, ?, start<sub>D<\/sub>), \u0438 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0438\u0437 \u043d\u0438\u0445 \u2014 \u043a\u0430\u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c&nbsp;&nbsp;\u0443\u0437\u043b\u043e\u0432 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c\u0438 (B, ?, start<sub>C<\/sub>).<\/p>\n<\/li>\n<\/ul>\n<p>\u0417\u043d\u0430\u0447\u0438\u0442, \u0435\u0441\u043b\u0438 \u0432 \u043f\u0440\u0430\u0432\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u0432\u044b\u0432\u043e\u0434\u0430 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u0442\u044c \u0434\u043e \u0442\u0440\u0451\u0445 \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b\u043e\u0432, \u0442\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043e\u0434\u043d\u043e\u0433\u043e \u0448\u0430\u0433\u0430 CYK \u0431\u0443\u0434\u0435\u0442&nbsp;, \u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0432\u0441\u0435\u0433\u043e \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u0431\u0443\u0434\u0435\u0442&nbsp;. \u041e\u0431\u043e\u0431\u0449\u0430\u044f \u043d\u0430 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u0443\u044e CFG \u2014 \u0432\u0438\u0434\u0438\u043c, \u0447\u0442\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 CYK \u0431\u0443\u0434\u0435\u0442&nbsp;, \u0433\u0434\u0435&nbsp;&nbsp;\u2014 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u0434\u043b\u0438\u043d\u0430 \u043f\u0440\u0430\u0432\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u043f\u0440\u0430\u0432\u0438\u043b \u0432\u044b\u0432\u043e\u0434\u0430 (&#171;\u0440\u0430\u043d\u0433 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438&#187;).<\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u043e\u0431\u043e\u0431\u0449\u0438\u043c CYK \u0434\u043b\u044f MCFG, \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u044f \u0435\u0433\u043e \u0446\u0435\u043d\u0442\u0440\u0430\u043b\u044c\u043d\u0443\u044e \u0438\u0434\u0435\u044e: \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0431\u0435\u0440\u0451\u043c \u0441 \u0434\u043e\u0441\u043a\u0438 \u043e\u0434\u0438\u043d \u0443\u0437\u0435\u043b, \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u0443\u0437\u043b\u044b \u0441 \u0435\u0433\u043e \u0443\u0447\u0430\u0441\u0442\u0438\u0435\u043c, \u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0438\u0445 \u043d\u0430 \u0434\u043e\u0441\u043a\u0443. \u0420\u0430\u0437\u0431\u043e\u0440 &#171;<em>\u042f \u0442\u0435\u0431\u044f \u0434\u0435\u0442\u044f\u043c \u043f\u0440\u043e\u0441\u0438\u043b \u043f\u043e\u043c\u043e\u0447\u044c!<\/em>&#187; \u043f\u043e \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0435, \u043f\u0440\u0438\u0432\u0435\u0434\u0451\u043d\u043d\u043e\u0439 \u0432 \u0447.1 \u0438 \u0434\u043b\u044f \u0443\u0434\u043e\u0431\u0441\u0442\u0432\u0430 \u043f\u043e\u0432\u0442\u043e\u0440\u0451\u043d\u043d\u043e\u0439 \u0437\u0434\u0435\u0441\u044c, \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f \u0442\u0430\u043a\u0438\u043c:<\/p>\n<pre><code class=\"vala\">VP(X,Y) \u2190 NP(X),V(Y) CP(X,Y) \u2190 VP(X,Y) VP(X,YZW) \u2190 NP(X),V(Z),CP(Y,W) S(XYZ) \u2190 NP(X),VP(Y,Z) NP(\u044f) \u2190 \u03b5 NP(\u0442\u0435\u0431\u044f) \u2190 \u03b5 NP(\u0434\u0435\u0442\u044f\u043c) \u2190 \u03b5 V(\u043f\u0440\u043e\u0441\u0438\u043b) \u2190 \u03b5 V(\u043f\u043e\u043c\u043e\u0447\u044c) \u2190 \u03b5<\/code><\/pre>\n<div>\n<div class=\"table\">\n<table>\n<tbody>\n<tr>\n<td>\n<p>\u0428\u0430\u0433<\/p>\n<\/td>\n<td>\n<p>\u041d\u0435\u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0435 \u0443\u0437\u043b\u044b<\/p>\n<\/td>\n<td data-colwidth=\"195\" width=\"195\">\n<p>\u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0435 \u0443\u0437\u043b\u044b<\/p>\n<\/td>\n<td>\n<p>\u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c\u044b\u0435 \u0443\u0437\u043b\u044b<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>1<\/p>\n<\/td>\n<td>\n<\/td>\n<td data-colwidth=\"195\" width=\"195\">\n<\/td>\n<td>\n<p><em>\u042f<\/em><sub>NP<\/sub>, <em>\u0442\u0435\u0431\u044f<\/em><sub>NP<\/sub>, <em>\u0434\u0435\u0442\u044f\u043c<\/em><sub>NP<\/sub>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em><sub>V<\/sub>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em><sub>V<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>2\u20144<\/p>\n<\/td>\n<td>\n<p><strong><em>\u042f<\/em><sub>NP<\/sub>, <em>\u0442\u0435\u0431\u044f<\/em><sub>NP<\/sub>, <em>\u0434\u0435\u0442\u044f\u043c<\/em><sub>NP<\/sub><\/strong>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em><sub>V<\/sub>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em><sub>V<\/sub><\/p>\n<\/td>\n<td data-colwidth=\"195\" width=\"195\">\n<\/td>\n<td>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>5<\/p>\n<\/td>\n<td>\n<p><strong><em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em><sub>V<\/sub><\/strong>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em><sub>V<\/sub><\/p>\n<\/td>\n<td data-colwidth=\"195\" width=\"195\">\n<p><strong><em>\u042f<\/em><sub>NP<\/sub>, <em>\u0442\u0435\u0431\u044f<\/em><sub>NP<\/sub>,<\/strong> <strong><em>\u0434\u0435\u0442\u044f\u043c<\/em><sub>NP<\/sub><\/strong><\/p>\n<\/td>\n<td>\n<p>(<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>6<\/p>\n<\/td>\n<td>\n<p><strong><em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em><sub>V<\/sub><\/strong>, (<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub><\/p>\n<\/td>\n<td data-colwidth=\"195\" width=\"195\">\n<p><strong><em>\u042f<\/em><sub>NP<\/sub>, <em>\u0442\u0435\u0431\u044f<\/em><sub>NP<\/sub>,<\/strong> <strong><em>\u0434\u0435\u0442\u044f\u043c<\/em><sub>NP<\/sub><\/strong>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em><sub>V<\/sub><\/p>\n<\/td>\n<td>\n<p>(<em>\u042f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>7, 8<\/p>\n<\/td>\n<td>\n<p><strong>(<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub><\/strong>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, (<em>\u042f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub><\/p>\n<\/td>\n<td data-colwidth=\"195\" width=\"195\">\n<p><em>\u042f<\/em><sub>NP<\/sub>, <em>\u0442\u0435\u0431\u044f<\/em><sub>NP<\/sub>, <em>\u0434\u0435\u0442\u044f\u043c<\/em><sub>NP<\/sub>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em><sub>V<\/sub>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em><sub>V<\/sub><\/p>\n<\/td>\n<td>\n<p>(<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>\u0421P<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>\u0421P<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>9<\/p>\n<\/td>\n<td>\n<p><strong>(<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub><\/strong>, (<em>\u042f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub>, (<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>\u0421P<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>\u0421P<\/sub><\/p>\n<\/td>\n<td data-colwidth=\"195\" width=\"195\">\n<p><em>\u042f<\/em><sub>NP<\/sub>, <strong><em>\u0442\u0435\u0431\u044f<\/em><sub>NP<\/sub><\/strong>, <em>\u0434\u0435\u0442\u044f\u043c<\/em><sub>NP<\/sub>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em><sub>V<\/sub>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em><sub>V<\/sub>, (<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub><\/p>\n<\/td>\n<td>\n<p>[<em>\u0442\u0435\u0431\u044f \u0434\u0435\u0442\u044f\u043c \u043f\u0440\u043e\u0441\u0438\u043b<\/em>]<sub>S<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>\u0421P<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>10\u201412<\/p>\n<\/td>\n<td>\n<p><strong>(<em>\u042f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>VP<\/sub><\/strong>, (<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>\u0421P<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>\u0421P<\/sub>, [<em>\u0442\u0435\u0431\u044f \u0434\u0435\u0442\u044f\u043c \u043f\u0440\u043e\u0441\u0438\u043b<\/em>]<sub>S<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>\u0421P<\/sub><\/p>\n<\/td>\n<td data-colwidth=\"195\" width=\"195\">\n<p><em>\u042f<\/em><sub>NP<\/sub>, <em>\u0442\u0435\u0431\u044f<\/em><sub>NP<\/sub>, <em>\u0434\u0435\u0442\u044f\u043c<\/em><sub>NP<\/sub>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em><sub>V<\/sub>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em><sub>V<\/sub>, (<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub><\/p>\n<\/td>\n<td>\n<p>(<em>\u042f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>\u0421P<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>\u0421P<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>CP<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>13\u201418<\/p>\n<\/td>\n<td>\n<p><strong>(<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>\u0421P<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>\u0421P<\/sub>, [<em>\u0442\u0435\u0431\u044f \u0434\u0435\u0442\u044f\u043c \u043f\u0440\u043e\u0441\u0438\u043b<\/em>]<sub>S<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>\u0421P<\/sub>, (<em>\u042f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>\u0421P<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>\u0421P<\/sub><\/strong>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>CP<\/sub><\/p>\n<\/td>\n<td data-colwidth=\"195\" width=\"195\">\n<p><em>\u042f<\/em><sub>NP<\/sub>, <em>\u0442\u0435\u0431\u044f<\/em><sub>NP<\/sub>, <em>\u0434\u0435\u0442\u044f\u043c<\/em><sub>NP<\/sub>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em><sub>V<\/sub>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em><sub>V<\/sub>, (<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, (<em>\u0442\u0435\u0431\u044f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, (<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, &#8230;<\/p>\n<\/td>\n<td>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>19<\/p>\n<\/td>\n<td>\n<p><strong>(<em>\u0434\u0435\u0442\u044f\u043c<\/em>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em>)<sub>CP<\/sub><\/strong><\/p>\n<\/td>\n<td data-colwidth=\"195\" width=\"195\">\n<p><em>\u042f<\/em><sub>NP<\/sub>, <strong><em>\u0442\u0435\u0431\u044f<\/em><sub>NP<\/sub><\/strong>, <em>\u0434\u0435\u0442\u044f\u043c<\/em><sub>NP<\/sub>, <strong><em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em><sub>V<\/sub><\/strong>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em><sub>V<\/sub>, (<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, &#8230;<\/p>\n<\/td>\n<td>\n<p>(<em>\u0442\u0435\u0431\u044f<\/em>, [<em>\u0434\u0435\u0442\u044f\u043c \u043f\u0440\u043e\u0441\u0438\u043b \u043f\u043e\u043c\u043e\u0447\u044c<\/em>])<sub>VP<\/sub><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p>20<\/p>\n<\/td>\n<td>\n<p><strong>(<em>\u0442\u0435\u0431\u044f<\/em>, [<em>\u0434\u0435\u0442\u044f\u043c \u043f\u0440\u043e\u0441\u0438\u043b \u043f\u043e\u043c\u043e\u0447\u044c<\/em>])<sub>VP<\/sub><\/strong><\/p>\n<\/td>\n<td data-colwidth=\"195\" width=\"195\">\n<p><strong><em>\u042f<\/em><sub>NP<\/sub><\/strong>, <em>\u0442\u0435\u0431\u044f<\/em><sub>NP<\/sub>, <em>\u0434\u0435\u0442\u044f\u043c<\/em><sub>NP<\/sub>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em><sub>V<\/sub>, <em>\u043f\u043e\u043c\u043e\u0447\u044c<\/em><sub>V<\/sub>, (<em>\u042f<\/em>, <em>\u043f\u0440\u043e\u0441\u0438\u043b<\/em>)<sub>VP<\/sub>, &#8230;<\/p>\n<\/td>\n<td>\n<p><strong>[<em>\u042f \u0442\u0435\u0431\u044f \u0434\u0435\u0442\u044f\u043c \u043f\u0440\u043e\u0441\u0438\u043b \u043f\u043e\u043c\u043e\u0447\u044c<\/em>]<sub>S<\/sub><\/strong><\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<p>\u041a\u0430\u043a \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0442\u0430\u043a\u043e\u0439 \u0440\u0430\u0437\u0431\u043e\u0440, \u0438 \u043a\u0430\u043a\u043e\u0439 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f \u0435\u0433\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c? \u0422\u0440\u0451\u0445\u043c\u0435\u0440\u043d\u043e\u0439 \u0434\u043e\u0441\u043a\u043e\u0439 \u0443\u0436\u0435 \u043d\u0435 \u043e\u0431\u043e\u0439\u0442\u0438\u0441\u044c: \u0443\u0437\u043b\u044b \u0434\u0432\u0443\u0445\u043c\u0435\u0441\u0442\u043d\u044b\u0445 \u043f\u0440\u0435\u0434\u0438\u043a\u0430\u0442\u043e\u0432, \u0442\u0430\u043a\u0438\u0445 \u043a\u0430\u043a VP \u0438 CP, \u043c\u043e\u0433\u0443\u0442 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u0434\u043b\u044f \u043b\u044e\u0431\u043e\u0439 \u043f\u0430\u0440\u044b \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a \u0432\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0442\u0435\u043a\u0441\u0442\u0430, \u0442\u0430\u043a \u0447\u0442\u043e \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u0446\u0438\u044f \u043f\u044f\u0442\u0451\u0440\u043a\u0430\u043c\u0438 (\u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b, \u043d\u0430\u0447\u0430\u043b\u043e<sub>1<\/sub>, \u043a\u043e\u043d\u0435\u0446<sub>1<\/sub>, \u043d\u0430\u0447\u0430\u043b\u043e<sub>2<\/sub>, \u043a\u043e\u043d\u0435\u0446<sub>2<\/sub>). \u041e\u0434\u043d\u043e \u0443\u0436\u0435 \u044d\u0442\u043e \u043f\u043e\u0432\u044b\u0448\u0430\u0435\u0442 \u0447\u0438\u0441\u043b\u043e \u0448\u0430\u0433\u043e\u0432 \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u0434\u043e . \u0422\u0435\u043f\u0435\u0440\u044c \u043d\u0430\u0434\u043e \u043f\u043e\u043d\u044f\u0442\u044c, \u043a\u0430\u043a\u0438\u0435 \u0443\u0437\u043b\u044b \u0442\u0430\u043a\u043e\u0439 \u043f\u044f\u0442\u0438\u043c\u0435\u0440\u043d\u043e\u0439 \u0434\u043e\u0441\u043a\u0438 \u043c\u043e\u0433\u0443\u0442 \u0443\u0447\u0430\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u0432\u043c\u0435\u0441\u0442\u0435 \u0441 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u043c\u044b\u043c \u0443\u0437\u043b\u043e\u043c \u0432 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u0432\u044b\u0432\u043e\u0434\u0430 \u2014 \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043f\u0440\u0430\u0432\u0438\u043b\u0430 <code>P(XY,ZW) \u2190 P(X,Z),P(Y,W)<\/code> \u0438\u0437 \u043f\u0440\u0438\u0432\u0435\u0434\u0451\u043d\u043d\u043e\u0439 \u0432 \u0447.1 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438 \u044f\u0437\u044b\u043a\u0430 \u0434\u0432\u0430\u0436\u0434\u044b \u043f\u043e\u0432\u0442\u043e\u0440\u0451\u043d\u043d\u044b\u0445 \u0441\u0442\u0440\u043e\u043a. \u041f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0438\u0435 \u0443\u0437\u043b\u044b \u0431\u0443\u0434\u0443\u0442 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c\u0441\u044f \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c (P, end<sub>X<\/sub>, ?, end<sub>Z<\/sub>, ?) \u0438 (P, ?, start<sub>Y<\/sub>, ?, start<sub>W<\/sub>), \u0442\u0430\u043a \u0447\u0442\u043e \u0438\u0445 \u0431\u0443\u0434\u0435\u0442  \u0448\u0442\u0443\u043a. \u0412 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u0438, \u0447\u0442\u043e &#171;\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438&#187; \u0440\u0430\u0432\u043d\u0430 2 (\u0442.\u0435. \u043f\u0440\u0435\u0434\u0438\u043a\u0430\u0442\u044b \u043a\u0430\u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c \u0434\u0432\u0443\u0445\u043c\u0435\u0441\u0442\u043d\u044b\u0435) \u0438 \u0435\u0451 \u0440\u0430\u043d\u0433 \u0442\u043e\u0436\u0435 \u0440\u0430\u0432\u0435\u043d 2 (\u0442.\u0435. \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u0432\u044b\u0432\u043e\u0434\u0430 \u0434\u043e\u043f\u0443\u0441\u043a\u0430\u044e\u0442 \u043a\u043e\u043d\u043a\u0430\u0442\u0435\u043d\u0430\u0446\u0438\u044e \u043a\u0430\u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c \u0434\u0432\u0443\u0445 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445) \u2014 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c, \u0447\u0442\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c CYK-\u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u0431\u0443\u0434\u0435\u0442 .<\/p>\n<p>\u0410 \u0435\u0441\u043b\u0438 \u0440\u0430\u043d\u0433 \u0432\u044b\u0448\u0435, \u043a\u0430\u043a \u0432 \u0432\u044b\u0448\u0435\u043f\u0440\u0438\u0432\u0435\u0434\u0451\u043d\u043d\u043e\u0439 \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0435, \u0433\u0434\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u043e <code>VP(X,YZW) \u2190 NP(X),V(Z),CP(Y,W)<\/code> \u0432\u043a\u043b\u044e\u0447\u0430\u0435\u0442 \u043a\u043e\u043d\u043a\u0430\u0442\u0435\u043d\u0430\u0446\u0438\u044e \u0442\u0440\u0451\u0445 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445? \u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0438\u0435 \u0434\u043b\u044f V \u0443\u0437\u043b\u044b \u0431\u0443\u0434\u0443\u0442 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c\u0441\u044f \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c (CP, ?, start<sub>Z<\/sub>, end<sub>Z<\/sub>, ?) \u0438 (NP, ?, ?, \u2205, \u2205), \u0442\u0430\u043a \u0447\u0442\u043e \u0438\u0445 \u0431\u0443\u0434\u0435\u0442 \u0443\u0436\u0435  \u0448\u0442\u0443\u043a. \u0410\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e, \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0438\u0435 \u0434\u043b\u044f NP \u0443\u0437\u043b\u044b \u0431\u0443\u0434\u0443\u0442 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c\u0441\u044f \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c (CP, ?, ?, ?, ?) \u0438 (V, end<sub>Y<\/sub>, start<sub>W<\/sub>, \u2205, \u2205), \u0438 \u0438\u0445 \u0442\u043e\u0436\u0435 \u0431\u0443\u0434\u0435\u0442 \u0448\u0442\u0443\u043a. \u041f\u043e\u043b\u0443\u0447\u0430\u044e\u0442\u0441\u044f  \u0448\u0430\u0433\u043e\u0432 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c\u044e  \u043a\u0430\u0436\u0434\u044b\u0439. \u041e\u0433\u0440\u043e\u043c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0431\u0435\u0441\u043f\u043e\u043b\u0435\u0437\u043d\u044b\u0445 \u0448\u0430\u0433\u043e\u0432 \u0437\u0430\u043c\u0435\u0442\u043d\u043e \u0438 \u0432 \u043f\u0440\u0438\u0432\u0435\u0434\u0451\u043d\u043d\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u0440\u0430\u0437\u0431\u043e\u0440\u0430: \u0432 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0438, \u0433\u0434\u0435 \u0442\u0440\u0438 NP \u0438 \u0434\u0432\u0430 V, \u0438\u0437 \u043a\u0430\u0436\u0434\u043e\u0439 \u0438\u0445 \u043f\u043e\u043f\u0430\u0440\u043d\u043e\u0439 \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0446\u0438\u0438 \u0432\u044b\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u043f\u043e \u0443\u0437\u043b\u0443 VP \u0438 CP.<\/p>\n<p>\u0412 \u0446\u0435\u043b\u043e\u043c \u043c\u043e\u0436\u043d\u043e \u0432\u0438\u0434\u0435\u0442\u044c, \u0447\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u043e\u0441\u0442\u0430\u0451\u0442\u0441\u044f \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u043c, \u043d\u043e \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0431\u044b\u0441\u0442\u0440\u043e \u0440\u0430\u0441\u0442\u0451\u0442 \u043f\u043e \u043c\u0435\u0440\u0435 \u0443\u0441\u043b\u043e\u0436\u043d\u0435\u043d\u0438\u044f \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438: \u043e\u0431\u043e\u0431\u0449\u0430\u044f \u043f\u0440\u0438\u0432\u0435\u0434\u0451\u043d\u043d\u044b\u0435 \u0440\u0430\u0441\u0441\u0443\u0436\u0434\u0435\u043d\u0438\u044f, \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c , \u0433\u0434\u0435&nbsp;&nbsp;\u2014 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a\u0438. \u042d\u0442\u043e \u0437\u043d\u0430\u0447\u0438\u0442, \u0447\u0442\u043e \u0440\u0430\u0437\u0431\u043e\u0440 \u043c\u043e\u0436\u043d\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0443\u043f\u0440\u043e\u0441\u0442\u0438\u0442\u044c, \u0437\u0430\u043c\u0435\u043d\u044f\u044f \u043a\u043e\u043d\u043a\u0430\u0442\u0435\u043d\u0430\u0446\u0438\u044e \u0431\u043e\u043b\u0435\u0435 \u0447\u0435\u043c \u0434\u0432\u0443\u0445 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u043d\u0430 \u043d\u043e\u0432\u044b\u0439 \u043d\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0430\u043b, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u043f\u0440\u0430\u0432\u0438\u043b\u043e  <code>VP(X,YZW) \u2190 NP(X),V(Z),CP(Y,W)<\/code> \u043d\u0430 \u043f\u0430\u0440\u0443 \u043f\u0440\u0430\u0432\u0438\u043b <code>CP'(Y,ZW) \u2190 V(Z),CP(Y,W); VP(X,YZ) \u2190 NP(X),CP'(Y,Z)<\/code>. \u041f\u043e\u043b\u0443\u0447\u0435\u043d\u043d\u043e\u0435 \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0434\u0435\u0440\u0435\u0432\u043e \u0440\u0430\u0437\u0431\u043e\u0440\u0430 \u0434\u0430\u043b\u044c\u0448\u0435 \u043e\u0442 \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u044f, \u043d\u043e \u0442\u0435\u043c \u043d\u0435 \u043c\u0435\u043d\u0435\u0435, \u0442\u0430\u043a\u0430\u044f &#171;\u043d\u043e\u0440\u043c\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f&#187; \u0433\u0440\u0430\u043c\u043c\u0430\u0442\u0438\u043a \u0448\u0438\u0440\u043e\u043a\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f.<\/p>\n<p>\u041a\u0430\u043a \u043e\u0442\u043c\u0435\u0447\u0430\u043b\u043e\u0441\u044c \u0432 \u0447.1, \u0442\u0435\u043a\u0441\u0442\u044b \u043d\u0430 \u0435\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0445 \u044f\u0437\u044b\u043a\u0430\u0445 \u0447\u0430\u0441\u0442\u043e \u0434\u043e\u043f\u0443\u0441\u043a\u0430\u044e\u0442<\/p>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-324472","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/324472","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=324472"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/324472\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=324472"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=324472"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=324472"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}