Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ — различия между версиями
Kabanov (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показано 13 промежуточных версий 4 участников) | |||
Строка 12: | Строка 12: | ||
* <tex>N</tex> {{---}} множество, элементы которого называют '''нетерминалами''' (англ. ''nonterminals'') | * <tex>N</tex> {{---}} множество, элементы которого называют '''нетерминалами''' (англ. ''nonterminals'') | ||
* <tex>S</tex> {{---}} начальный символ грамматики (англ. ''start symbol'') | * <tex>S</tex> {{---}} начальный символ грамматики (англ. ''start symbol'') | ||
− | * <tex>P</tex> {{---}} набор правил вывода (англ. ''production rules'' или ''productions'') вида <tex>A \rightarrow B_1 B_2 | + | * <tex>P</tex> {{---}} набор правил вывода (англ. ''production rules'' или ''productions'') вида <tex>A \rightarrow B_1 B_2 \ldots B_n</tex>, где <tex>A \in N</tex>, <tex>B_i \in \Sigma \cup N</tex>, то есть у которых левые части {{---}} одиночные нетерминалы, а правые {{---}} последовательности терминалов и нетерминалов. |
}} | }} | ||
− | |||
=== Пример === | === Пример === | ||
Строка 35: | Строка 34: | ||
== Нормальная форма Хомского == | == Нормальная форма Хомского == | ||
− | '''[[Нормальная форма Хомского]]''' - нормальная форма КС-грамматик, в которой все продукции имеют вид: | + | '''[[Нормальная форма Хомского]]''' {{---}} нормальная форма КС-грамматик, в которой все продукции имеют вид: |
− | * A | + | * <tex>A \rightarrow a</tex>, где <tex>A</tex> {{---}} нетерминал, а <tex>a</tex> {{---}} терминал |
− | * A | + | * <tex>A \rightarrow BC</tex>, где <tex>A</tex>, <tex>B</tex>, <tex>C</tex> {{---}} нетерминалы, причем <tex>B</tex> и <tex>C</tex> не являются начальными нетерминалами |
− | * S | + | * <tex>S \rightarrow \varepsilon</tex>, где <tex>S</tex> {{---}} начальный нетерминал и <tex>\varepsilon</tex> {{---}} пустая строка (данная продукция необходима, если в языке присуствует пустая строка) |
− | [[Нормальная форма Хомского|Можно показать]], что любую КС-грамматику можно привести к нормальной форме Хомского | + | [[Нормальная форма Хомского|Можно показать]], что любую КС-грамматику можно привести к нормальной форме Хомского. |
== Алгоритм == | == Алгоритм == | ||
− | '''Алгоритм Кока-Янгера-Касами''' (англ. ''Cocke-Younger-Kasami algorithm'', англ. ''CYK-алгоритм'') {{---}} | + | '''Алгоритм Кока-Янгера-Касами''' (англ. ''Cocke-Younger-Kasami algorithm'', англ. ''CYK-алгоритм'') {{---}} алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского. Любую КС-грамматику можно привести к НФХ, поэтому алгоритм является универсальным для любой КС-грамматики. |
− | Будем решать задачу [[Динамическое_программирование|динамическим программированием]]. Дана строка <tex>w</tex> размером <tex>n</tex>. Заведем для неё трехмерный массив <tex>d</tex> размером <tex>|N| \times n \times n</tex>, состоящий из логических значений, и <tex>d[A][i][j] = true</tex> тогда и только тогда, когда из нетерминала <tex>A</tex> правилами грамматики можно вывести подстроку <tex>w[i \ | + | |
+ | Будем решать задачу [[Динамическое_программирование|динамическим программированием]]. Дана строка <tex>w</tex> размером <tex>n</tex>. Заведем для неё трехмерный массив <tex>d</tex> размером <tex>|N| \times n \times n</tex>, состоящий из логических значений, и <tex>d[A][i][j] = true \ </tex> тогда и только тогда, когда из нетерминала <tex>A</tex> правилами грамматики можно вывести подстроку <tex>w[i \ldots j]</tex>. | ||
Рассмотрим все пары <tex>\lbrace \langle j, i \rangle | j-i=m \rbrace</tex>, где <tex>m</tex> {{---}} константа и <tex>m < n</tex>. | Рассмотрим все пары <tex>\lbrace \langle j, i \rangle | j-i=m \rbrace</tex>, где <tex>m</tex> {{---}} константа и <tex>m < n</tex>. | ||
− | * <tex>i = j</tex>. Инициализируем массив для всех нетерминалов, из которых выводится какой-либо символ строки <tex>w</tex>. В таком случае <tex>d[A][i][i] = true</tex>, если в грамматике <tex>\Gamma</tex> присутствует правило <tex>A \rightarrow w[i]</tex>. Иначе <tex>d[A][i][i] = false</tex>. | + | * <tex>i = j</tex>. Инициализируем массив для всех нетерминалов, из которых выводится какой-либо символ строки <tex>w</tex>. В таком случае <tex>d[A][i][i] = true \ </tex>, если в грамматике <tex>\Gamma</tex> присутствует правило <tex>A \rightarrow w[i]</tex>. Иначе <tex>d[A][i][i] = false</tex>. |
− | * <tex>i \ne j</tex>. Значения для всех нетерминалов и пар <tex>\lbrace \langle j', i' \rangle | j' - i' < m \rbrace</tex> уже вычислены, поэтому <tex>d[A][i][j] = \bigvee\limits_{A \rightarrow BC}\bigvee\limits_{k = i}^{j-1} d[B][i][k] \wedge d[C][k+1][j]</tex>. То есть, подстроку <tex>w[i \ | + | * <tex>i \ne j</tex>. Значения для всех нетерминалов и пар <tex>\lbrace \langle j', i' \rangle | j' - i' < m \rbrace</tex> уже вычислены, поэтому <tex>d[A][i][j] = \bigvee\limits_{A \rightarrow BC}\bigvee\limits_{k = i}^{j-1} d[B][i][k] \wedge d[C][k+1][j] \ \ </tex>. То есть, подстроку <tex>w[i \ldots j]</tex> можно вывести из нетерминала <tex>A</tex>, если существует продукция вида <tex>A \rightarrow BC</tex> и такое <tex>k</tex>, что подстрока <tex>w[i \ldots k]</tex> выводима из <tex>B</tex>, а подстрока <tex>w[k + 1 \ldots j]</tex> выводится из <tex>C</tex>. |
[[Файл:CYK_rule_2.jpg|400px]] | [[Файл:CYK_rule_2.jpg|400px]] | ||
Строка 58: | Строка 58: | ||
=== Количество способов вывести слово === | === Количество способов вывести слово === | ||
− | Если массив будет хранить целые числа, а формулу заменить на <tex>d[A][i][j] = \sum\limits_{A \rightarrow BC}\sum\limits_{k = i}^{j-1} d[B][i][k] \cdot d[C][k + 1][j]</tex>, то <tex>d[A][i][j]</tex> {{---}} количество способов получить подстроку <tex>w[i \ | + | Если массив будет хранить целые числа, а формулу заменить на <tex>d[A][i][j] = \sum\limits_{A \rightarrow BC}\sum\limits_{k = i}^{j-1} d[B][i][k] \cdot d[C][k + 1][j] \ \ </tex>, то <tex>d[A][i][j]</tex> {{---}} количество способов получить подстроку <tex>w[i \ldots j]</tex> из нетерминала <tex>A</tex>. |
=== Минимальная стоимость вывода слова === | === Минимальная стоимость вывода слова === | ||
− | Пусть <tex>H(A \rightarrow BC)</tex> {{---}} стоимость вывода по правилу <tex>A \rightarrow BC</tex>. Тогда, если использовать формулу <tex>d[A][i][j] = \min\limits_{A \rightarrow BC} \min\limits_{k = i}^{j-1} ( d[B][i][k] + d[C][k + 1][j] + H(A \rightarrow BC) )</tex>, то <tex>d[A][i][j]</tex> {{---}} минимальная стоимость вывода подстроки <tex>w[i \ | + | Пусть <tex>H(A \rightarrow BC)</tex> {{---}} стоимость вывода по правилу <tex>A \rightarrow BC</tex>. Тогда, если использовать формулу <tex>d[A][i][j] = \min\limits_{A \rightarrow BC} \min\limits_{k = i}^{j-1} ( d[B][i][k] + d[C][k + 1][j] + H(A \rightarrow BC) ) \ \ </tex>, то <tex>d[A][i][j]</tex> {{---}} минимальная стоимость вывода подстроки <tex>w[i \ldots j]</tex> из нетерминала <tex>A</tex>. |
Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является частным случаем задачи динамического программирования на подотрезке. | Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является частным случаем задачи динамического программирования на подотрезке. | ||
Строка 76: | Строка 76: | ||
<tex>\begin{array}{l l} | <tex>\begin{array}{l l} | ||
− | A \rightarrow \varepsilon|BB|CD\\ | + | A \rightarrow \varepsilon\ |\ BB\ |\ CD\\ |
− | B \rightarrow BB|CD\\ | + | B \rightarrow BB\ |\ CD\\ |
C \rightarrow (\\ | C \rightarrow (\\ | ||
− | D \rightarrow BE|)\\ | + | D \rightarrow BE\ |\ )\\ |
E \rightarrow )\\ | E \rightarrow )\\ | ||
\end{array}</tex> | \end{array}</tex> | ||
− | Дано слово <tex>w = | + | Дано слово <tex>w = ()(())</tex>. |
− | |||
Инициализация массива <tex>d</tex>. | Инициализация массива <tex>d</tex>. | ||
− | |||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|A | + | ! colspan="7" style="background:#ffdead;"|A |
|- | |- | ||
! | ! | ||
Строка 108: | Строка 106: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 117: | Строка 114: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 126: | Строка 122: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 135: | Строка 130: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 144: | Строка 138: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 153: | Строка 146: | ||
| | | | ||
| | | | ||
− | |||
|} | |} | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|B | + | ! colspan="7" style="background:#ffdead;"|B |
|- | |- | ||
! | ! | ||
Строка 173: | Строка 165: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 182: | Строка 173: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 191: | Строка 181: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 200: | Строка 189: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 209: | Строка 197: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 218: | Строка 205: | ||
| | | | ||
| | | | ||
− | |||
|} | |} | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|C | + | ! colspan="7" style="background:#ffdead;"|C |
|- | |- | ||
! | ! | ||
Строка 238: | Строка 224: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 247: | Строка 232: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 256: | Строка 240: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 265: | Строка 248: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 274: | Строка 256: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 283: | Строка 264: | ||
| | | | ||
| | | | ||
− | |||
|} | |} | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|D | + | ! colspan="7" style="background:#ffdead;"|D |
|- | |- | ||
! | ! | ||
Строка 303: | Строка 283: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 312: | Строка 291: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 321: | Строка 299: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 330: | Строка 307: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 339: | Строка 315: | ||
| align="center"| ● | | align="center"| ● | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 348: | Строка 323: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|} | |} | ||
− | {| border="1" class="wikitable" style="width: 150px; height: 150px; " | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|E | + | ! colspan="7" style="background:#ffdead;"|E |
|- | |- | ||
! | ! | ||
Строка 368: | Строка 342: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 377: | Строка 350: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 386: | Строка 358: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 395: | Строка 366: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 404: | Строка 374: | ||
| align="center"| ● | | align="center"| ● | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 413: | Строка 382: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|} | |} | ||
− | + | <div style="clear:both;"></div> | |
Заполнение массива <tex>d</tex>. | Заполнение массива <tex>d</tex>. | ||
− | |||
− | |||
− | |||
+ | Итерация <tex>m = 1</tex>. | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|A | + | ! colspan="7" style="background:#ffdead;"|A |
|- | |- | ||
! | ! | ||
Строка 442: | Строка 408: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 451: | Строка 416: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 460: | Строка 424: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 469: | Строка 432: | ||
| align="center"| ● | | align="center"| ● | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 478: | Строка 440: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 487: | Строка 448: | ||
| | | | ||
| | | | ||
− | |||
|} | |} | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|B | + | ! colspan="7" style="background:#ffdead;"|B |
|- | |- | ||
! | ! | ||
Строка 507: | Строка 467: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 516: | Строка 475: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 525: | Строка 483: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 534: | Строка 491: | ||
| align="center"| ● | | align="center"| ● | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 543: | Строка 499: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 552: | Строка 507: | ||
| | | | ||
| | | | ||
− | |||
|} | |} | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|C | + | ! colspan="7" style="background:#ffdead;"|C |
|- | |- | ||
! | ! | ||
Строка 572: | Строка 526: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 581: | Строка 534: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 590: | Строка 542: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 599: | Строка 550: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 608: | Строка 558: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 617: | Строка 566: | ||
| | | | ||
| | | | ||
− | |||
|} | |} | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|D | + | ! colspan="7" style="background:#ffdead;"|D |
|- | |- | ||
! | ! | ||
Строка 637: | Строка 585: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 646: | Строка 593: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 655: | Строка 601: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 664: | Строка 609: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 673: | Строка 617: | ||
| align="center"| ● | | align="center"| ● | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 682: | Строка 625: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|} | |} | ||
− | {| border="1" class="wikitable" style="width: 150px; height: 150px; " | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|E | + | ! colspan="7" style="background:#ffdead;"|E |
|- | |- | ||
! | ! | ||
Строка 702: | Строка 644: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 711: | Строка 652: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 720: | Строка 660: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 729: | Строка 668: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 738: | Строка 676: | ||
| align="center"| ● | | align="center"| ● | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 747: | Строка 684: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|} | |} | ||
− | + | <div style="clear:both;"></div> | |
− | |||
− | |||
+ | Итерация <tex>m = 2</tex>. | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|A | + | ! colspan="7" style="background:#ffdead;"|A |
|- | |- | ||
! | ! | ||
Строка 772: | Строка 707: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 781: | Строка 715: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 790: | Строка 723: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 799: | Строка 731: | ||
| align="center"| ● | | align="center"| ● | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 808: | Строка 739: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 817: | Строка 747: | ||
| | | | ||
| | | | ||
− | |||
|} | |} | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|B | + | ! colspan="7" style="background:#ffdead;"|B |
|- | |- | ||
! | ! | ||
Строка 837: | Строка 766: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 846: | Строка 774: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 855: | Строка 782: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 864: | Строка 790: | ||
| align="center"| ● | | align="center"| ● | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 873: | Строка 798: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 882: | Строка 806: | ||
| | | | ||
| | | | ||
− | |||
|} | |} | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|C | + | ! colspan="7" style="background:#ffdead;"|C |
|- | |- | ||
! | ! | ||
Строка 902: | Строка 825: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 911: | Строка 833: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 920: | Строка 841: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 929: | Строка 849: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 938: | Строка 857: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 947: | Строка 865: | ||
| | | | ||
| | | | ||
− | |||
|} | |} | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|D | + | ! colspan="7" style="background:#ffdead;"|D |
|- | |- | ||
! | ! | ||
Строка 967: | Строка 884: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 976: | Строка 892: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 985: | Строка 900: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 994: | Строка 908: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 1003: | Строка 916: | ||
| align="center"| ● | | align="center"| ● | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 1012: | Строка 924: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|} | |} | ||
− | {| border="1" class="wikitable" style="width: 150px; height: 150px; " | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|E | + | ! colspan="7" style="background:#ffdead;"|E |
|- | |- | ||
! | ! | ||
Строка 1032: | Строка 943: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 1041: | Строка 951: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 1050: | Строка 959: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 1059: | Строка 967: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 1068: | Строка 975: | ||
| align="center"| ● | | align="center"| ● | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 1077: | Строка 983: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|} | |} | ||
− | + | <div style="clear:both;"></div> | |
− | |||
− | |||
+ | Итерация <tex>m = 3</tex>. | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|A | + | ! colspan="7" style="background:#ffdead;"|A |
|- | |- | ||
! | ! | ||
Строка 1102: | Строка 1006: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 1111: | Строка 1014: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 1120: | Строка 1022: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 1129: | Строка 1030: | ||
| align="center"| ● | | align="center"| ● | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 1138: | Строка 1038: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 1147: | Строка 1046: | ||
| | | | ||
| | | | ||
− | |||
|} | |} | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|B | + | ! colspan="7" style="background:#ffdead;"|B |
|- | |- | ||
! | ! | ||
Строка 1167: | Строка 1065: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 1176: | Строка 1073: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 1185: | Строка 1081: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 1194: | Строка 1089: | ||
| align="center"| ● | | align="center"| ● | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 1203: | Строка 1097: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 1212: | Строка 1105: | ||
| | | | ||
| | | | ||
− | |||
|} | |} | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|C | + | ! colspan="7" style="background:#ffdead;"|C |
|- | |- | ||
! | ! | ||
Строка 1232: | Строка 1124: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 1241: | Строка 1132: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 1250: | Строка 1140: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 1259: | Строка 1148: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 1268: | Строка 1156: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 1277: | Строка 1164: | ||
| | | | ||
| | | | ||
− | |||
|} | |} | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|D | + | ! colspan="7" style="background:#ffdead;"|D |
|- | |- | ||
! | ! | ||
Строка 1297: | Строка 1183: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 1306: | Строка 1191: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 1315: | Строка 1199: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 1324: | Строка 1207: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 1333: | Строка 1215: | ||
| align="center"| ● | | align="center"| ● | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 1342: | Строка 1223: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|} | |} | ||
− | {| border="1" class="wikitable" style="width: 150px; height: 150px; " | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|E | + | ! colspan="7" style="background:#ffdead;"|E |
|- | |- | ||
! | ! | ||
Строка 1362: | Строка 1242: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 1371: | Строка 1250: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 1380: | Строка 1258: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 1389: | Строка 1266: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 1398: | Строка 1274: | ||
| align="center"| ● | | align="center"| ● | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 1407: | Строка 1282: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|} | |} | ||
− | + | <div style="clear:both;"></div> | |
− | |||
− | |||
+ | Итерация <tex>m = 4</tex>. | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|A | + | ! colspan="7" style="background:#ffdead;"|A |
|- | |- | ||
! | ! | ||
Строка 1432: | Строка 1305: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 1441: | Строка 1313: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 1450: | Строка 1321: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 1459: | Строка 1329: | ||
| align="center"| ● | | align="center"| ● | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 1468: | Строка 1337: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 1477: | Строка 1345: | ||
| | | | ||
| | | | ||
− | |||
|} | |} | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|B | + | ! colspan="7" style="background:#ffdead;"|B |
|- | |- | ||
! | ! | ||
Строка 1497: | Строка 1364: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 1506: | Строка 1372: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 1515: | Строка 1380: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 1524: | Строка 1388: | ||
| align="center"| ● | | align="center"| ● | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 1533: | Строка 1396: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 1542: | Строка 1404: | ||
| | | | ||
| | | | ||
− | |||
|} | |} | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|C | + | ! colspan="7" style="background:#ffdead;"|C |
|- | |- | ||
! | ! | ||
Строка 1562: | Строка 1423: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 1571: | Строка 1431: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 1580: | Строка 1439: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 1589: | Строка 1447: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 1598: | Строка 1455: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 1607: | Строка 1463: | ||
| | | | ||
| | | | ||
− | |||
|} | |} | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|D | + | ! colspan="7" style="background:#ffdead;"|D |
|- | |- | ||
! | ! | ||
Строка 1627: | Строка 1482: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 1636: | Строка 1490: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 1645: | Строка 1498: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 1654: | Строка 1506: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 1663: | Строка 1514: | ||
| align="center"| ● | | align="center"| ● | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 1672: | Строка 1522: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|} | |} | ||
− | {| border="1" class="wikitable" style="width: 150px; height: 150px; " | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|E | + | ! colspan="7" style="background:#ffdead;"|E |
|- | |- | ||
! | ! | ||
Строка 1692: | Строка 1541: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 1701: | Строка 1549: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 1710: | Строка 1557: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 1719: | Строка 1565: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 1728: | Строка 1573: | ||
| align="center"| ● | | align="center"| ● | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 1737: | Строка 1581: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|} | |} | ||
− | + | <div style="clear:both;"></div> | |
− | |||
− | |||
+ | Итерация <tex>m = 5</tex>. | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|A | + | ! colspan="7" style="background:#ffdead;"|A |
|- | |- | ||
! | ! | ||
Строка 1762: | Строка 1604: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 1771: | Строка 1612: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 1780: | Строка 1620: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 1789: | Строка 1628: | ||
| align="center"| ● | | align="center"| ● | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 1798: | Строка 1636: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 1807: | Строка 1644: | ||
| | | | ||
| | | | ||
− | |||
|} | |} | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|B | + | ! colspan="7" style="background:#ffdead;"|B |
|- | |- | ||
! | ! | ||
Строка 1827: | Строка 1663: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 1836: | Строка 1671: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 1845: | Строка 1679: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 1854: | Строка 1687: | ||
| align="center"| ● | | align="center"| ● | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 1863: | Строка 1695: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 1872: | Строка 1703: | ||
| | | | ||
| | | | ||
− | |||
|} | |} | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|C | + | ! colspan="7" style="background:#ffdead;"|C |
|- | |- | ||
! | ! | ||
Строка 1892: | Строка 1722: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 1901: | Строка 1730: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 1910: | Строка 1738: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 1919: | Строка 1746: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 1928: | Строка 1754: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 1937: | Строка 1762: | ||
| | | | ||
| | | | ||
− | |||
|} | |} | ||
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
− | ! colspan="7"|D | + | ! colspan="7" style="background:#ffdead;"|D |
|- | |- | ||
! | ! | ||
Строка 1957: | Строка 1781: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 1966: | Строка 1789: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 1975: | Строка 1797: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 1984: | Строка 1805: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 1993: | Строка 1813: | ||
| align="center"| ● | | align="center"| ● | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 2002: | Строка 1821: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
|} | |} | ||
− | {| border="1" class="wikitable" style="width: 150px; height: 150px; " | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" |
− | ! colspan="7"|E | + | ! colspan="7" style="background:#ffdead;"|E |
|- | |- | ||
! | ! | ||
Строка 2022: | Строка 1840: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 2 | ! 2 | ||
Строка 2031: | Строка 1848: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 3 | ! 3 | ||
Строка 2040: | Строка 1856: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 4 | ! 4 | ||
Строка 2049: | Строка 1864: | ||
| | | | ||
| | | | ||
− | |||
|- | |- | ||
! 5 | ! 5 | ||
Строка 2058: | Строка 1872: | ||
| align="center"| ● | | align="center"| ● | ||
| | | | ||
− | |||
|- | |- | ||
! 6 | ! 6 | ||
Строка 2067: | Строка 1880: | ||
| | | | ||
| align="center"| ● | | align="center"| ● | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
|} | |} | ||
− | + | <div style="clear:both;"></div> | |
== См. также == | == См. также == | ||
Строка 2413: | Строка 1895: | ||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
[[Категория: Контекстно-свободные грамматики]] | [[Категория: Контекстно-свободные грамматики]] | ||
+ | [[Категория: Алгоритмы разбора]] |
Текущая версия на 19:17, 4 сентября 2022
Задача: |
Пусть дана контекстно-свободная грамматика в нормальной форме Хомского и слово . Требуется выяснить, выводится ли это слово в данной грамматике. |
Содержание
Контекстно-свободная грамматика
Определение: |
Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — способ описания формального языка, представляющий собой четверку
, где:
|
Пример
Терминалы
.Нетерминалы
.Правила вывода
:
Данная грамматика задает язык правильных скобочных последовательностей. Например, последовательность может быть выведена следующим образом:
Нормальная форма Хомского
Нормальная форма Хомского — нормальная форма КС-грамматик, в которой все продукции имеют вид:
- , где — нетерминал, а — терминал
- , где , , — нетерминалы, причем и не являются начальными нетерминалами
- , где — начальный нетерминал и — пустая строка (данная продукция необходима, если в языке присуствует пустая строка)
Можно показать, что любую КС-грамматику можно привести к нормальной форме Хомского.
Алгоритм
Алгоритм Кока-Янгера-Касами (англ. Cocke-Younger-Kasami algorithm, англ. CYK-алгоритм) — алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского. Любую КС-грамматику можно привести к НФХ, поэтому алгоритм является универсальным для любой КС-грамматики.
Будем решать задачу динамическим программированием. Дана строка размером . Заведем для неё трехмерный массив размером , состоящий из логических значений, и тогда и только тогда, когда из нетерминала правилами грамматики можно вывести подстроку .
Рассмотрим все пары
, где — константа и .- . Инициализируем массив для всех нетерминалов, из которых выводится какой-либо символ строки . В таком случае , если в грамматике присутствует правило . Иначе .
- . Значения для всех нетерминалов и пар уже вычислены, поэтому . То есть, подстроку можно вывести из нетерминала , если существует продукция вида и такое , что подстрока выводима из , а подстрока выводится из .
После окончания работы значение
содержит ответ на вопрос, выводима ли данная строка в данной грамматике, где — начальный символ грамматики.Модификации
Количество способов вывести слово
Если массив будет хранить целые числа, а формулу заменить на
, то — количество способов получить подстроку из нетерминала .Минимальная стоимость вывода слова
Пусть
— стоимость вывода по правилу . Тогда, если использовать формулу , то — минимальная стоимость вывода подстроки из нетерминала .Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является частным случаем задачи динамического программирования на подотрезке.
Асимптотика
Обработка правил вида
выполняется за .Проход по всем подстрокам выполняется за
. В обработке одной подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за . В итоге получаем конечную сложность .Следовательно, общее время работы алгоритма — нетерминалов грамматики.
. Кроме того, алгоритму требуется память на массив объемом , где — количествоПример работы
Дана грамматика правильных скобочных последовательностей в нормальной форме Хомского.
Дано слово
.
Инициализация массива .
A | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ||||||
3 | ||||||
4 | ||||||
5 | ||||||
6 |
B | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ||||||
3 | ||||||
4 | ||||||
5 | ||||||
6 |
C | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
D | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |
E | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |
Заполнение массива
.
Итерация .
A | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ||||||
4 | ● | |||||
5 | ||||||
6 |
B | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ||||||
4 | ● | |||||
5 | ||||||
6 |
C | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
D | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |
E | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |
Итерация
.A | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ||||||
4 | ● | |||||
5 | ||||||
6 |
B | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ||||||
4 | ● | |||||
5 | ||||||
6 |
C | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
D | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ● | |||||
5 | ● | |||||
6 | ● |
E | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |
Итерация
.A | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
B | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
C | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
D | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ● | |||||
5 | ● | |||||
6 | ● |
E | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |
Итерация
.A | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
B | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
C | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
D | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ● | |||||
5 | ● | |||||
6 | ● |
E | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |
Итерация
.A | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | ● | ||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
B | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | ● | ||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
C | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ● | |||||
2 | ||||||
3 | ● | |||||
4 | ● | |||||
5 | ||||||
6 |
D | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ● | |||||
5 | ● | |||||
6 | ● |
E | ||||||
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ||||||
2 | ● | |||||
3 | ||||||
4 | ||||||
5 | ● | |||||
6 | ● |