Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Контекстно-свободная грамматика: тире)
 
(не показано 11 промежуточных версий 3 участников)
Строка 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 ... B_n</tex>, где <tex>A \in N</tex>, <tex>B_i \in \Sigma \cup N</tex>, то есть у которых левые части {{---}} одиночные нетерминалы, а правые - последовательности терминалов и нетерминалов.
+
* <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 &rarr; a, где ''A'' - нетерминал, а ''a'' - терминал
+
* <tex>A \rightarrow a</tex>, где <tex>A</tex> {{---}} нетерминал, а <tex>a</tex> {{---}} терминал
* A &rarr; BC, где ''A'', ''B'', ''C'' - нетерминалы, причем ''B'' и ''C'' не являются начальными нетерминалами
+
* <tex>A \rightarrow BC</tex>, где <tex>A</tex>, <tex>B</tex>, <tex>C</tex> {{---}} нетерминалы, причем <tex>B</tex> и <tex>C</tex> не являются начальными нетерминалами
* S &rarr; ε, где 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 \dots j]</tex>.
+
 
 +
Будем решать задачу [[Динамическое_программирование|динамическим программированием]]. Дана строка <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 \dots j]</tex> можно вывести из нетерминала <tex>A</tex>, если существует продукция вида <tex>A \rightarrow BC</tex> и такое <tex>k</tex>, что подстрока <tex>w[i \dots k]</tex> выводима из <tex>B</tex>, а подстрока <tex>w[k + 1 \dots j]</tex> выводится из <tex>C</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 \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 \dots j]</tex> из нетерминала <tex>A</tex>.
+
Если массив будет хранить целые числа, а формулу заменить на <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 \dots 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 \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>.
+
Дано слово <tex>w = ()(())</tex>.
  
{| clear="both" |}
 
  
 
Инициализация массива <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"| ●  
 
 
|}
 
|}
{| clear="both" |}
+
<div style="clear:both;"></div>
  
 
Заполнение массива <tex>d</tex>.
 
Заполнение массива <tex>d</tex>.
  
{| clear="both" |}
 
 
Итерация m = <tex>1</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"| ●  
 
 
|}
 
|}
{| clear="both" |}
+
<div style="clear:both;"></div>
 
 
Итерация m = <tex>2</tex>.
 
  
 +
Итерация <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"| ●  
 
 
|}
 
|}
{| clear="both" |}
+
<div style="clear:both;"></div>
 
 
Итерация m = <tex>3</tex>.
 
  
 +
Итерация <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"| ●  
 
 
|}
 
|}
{| clear="both" |}
+
<div style="clear:both;"></div>
 
 
Итерация m = <tex>4</tex>.
 
  
 +
Итерация <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"| ●  
 
 
|}
 
|}
{| clear="both" |}
+
<div style="clear:both;"></div>
 
 
Итерация m = <tex>5</tex>.
 
  
 +
Итерация <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"| ●  
 
|}
 
{| clear="both" |}
 
 
Итерация m = <tex>6</tex>.
 
 
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
 
! colspan="7"|A
 
|-
 
!
 
! 1
 
! 2
 
! 3
 
! 4
 
! 5
 
! 6
 
|-
 
! 1
 
|
 
| align="center"| ●
 
|
 
|
 
|
 
| align="center"| ●
 
 
|-
 
! 2
 
|
 
|
 
|
 
|
 
|
 
|
 
 
|-
 
! 3
 
|
 
|
 
|
 
|
 
|
 
| align="center"| ●
 
 
|-
 
! 4
 
|
 
|
 
|
 
|
 
| align="center"| ●
 
|
 
 
|-
 
! 5
 
|
 
|
 
|
 
|
 
|
 
|
 
 
|-
 
! 6
 
|
 
|
 
|
 
|
 
|
 
|
 
 
|}
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
 
! colspan="7"|B
 
|-
 
!
 
! 1
 
! 2
 
! 3
 
! 4
 
! 5
 
! 6
 
|-
 
! 1
 
|
 
| align="center"| ●
 
|
 
|
 
|
 
| align="center"| ●
 
 
|-
 
! 2
 
|
 
|
 
|
 
|
 
|
 
|
 
 
|-
 
! 3
 
|
 
|
 
|
 
|
 
|
 
| align="center"| ●
 
 
|-
 
! 4
 
|
 
|
 
|
 
|
 
| align="center"| ●
 
|
 
 
|-
 
! 5
 
|
 
|
 
|
 
|
 
|
 
|
 
 
|-
 
! 6
 
|
 
|
 
|
 
|
 
|
 
|
 
 
|}
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
 
! colspan="7"|C
 
|-
 
!
 
! 1
 
! 2
 
! 3
 
! 4
 
! 5
 
! 6
 
|-
 
! 1
 
| align="center"| ●
 
|
 
|
 
|
 
|
 
|
 
 
|-
 
! 2
 
|
 
|
 
|
 
|
 
|
 
|
 
 
|-
 
! 3
 
|
 
|
 
| align="center"| ●
 
|
 
|
 
|
 
 
|-
 
! 4
 
|
 
|
 
|
 
| align="center"| ●
 
|
 
|
 
 
|-
 
! 5
 
|
 
|
 
|
 
|
 
|
 
|
 
 
|-
 
! 6
 
|
 
|
 
|
 
|
 
|
 
|
 
 
|}
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
 
! colspan="7"|D
 
|-
 
!
 
! 1
 
! 2
 
! 3
 
! 4
 
! 5
 
! 6
 
|-
 
! 1
 
|
 
|
 
|
 
|
 
|
 
|
 
 
|-
 
! 2
 
|
 
| align="center"| ●
 
|
 
|
 
|
 
|
 
 
|-
 
! 3
 
|
 
|
 
|
 
|
 
|
 
|
 
 
|-
 
! 4
 
|
 
|
 
|
 
|
 
|
 
| align="center"| ●
 
 
|-
 
! 5
 
|
 
|
 
|
 
|
 
| align="center"| ●
 
|
 
 
|-
 
! 6
 
|
 
|
 
|
 
|
 
|
 
| align="center"| ●
 
 
|}
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; "
 
! colspan="7"|E
 
|-
 
!
 
! 1
 
! 2
 
! 3
 
! 4
 
! 5
 
! 6
 
|-
 
! 1
 
|
 
|
 
|
 
|
 
|
 
|
 
 
|-
 
! 2
 
|
 
| align="center"| ●
 
|
 
|
 
|
 
|
 
 
|-
 
! 3
 
|
 
|
 
|
 
|
 
|
 
|
 
 
|-
 
! 4
 
|
 
|
 
|
 
|
 
|
 
|
 
 
|-
 
! 5
 
|
 
|
 
|
 
|
 
| align="center"| ●
 
|
 
 
|-
 
! 6
 
|
 
|
 
|
 
|
 
|
 
| align="center"| ●
 
 
 
|}
 
|}
{| clear="both" |}
+
<div style="clear:both;"></div>
  
 
== См. также ==  
 
== См. также ==  
Строка 2413: Строка 1895:
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Контекстно-свободные грамматики]]
 
[[Категория: Контекстно-свободные грамматики]]
 +
[[Категория: Алгоритмы разбора]]

Текущая версия на 22:51, 23 мая 2019

Задача:
Пусть дана контекстно-свободная грамматика [math]\Gamma[/math] в нормальной форме Хомского и слово [math]w \in \Sigma^{*}[/math]. Требуется выяснить, выводится ли это слово в данной грамматике.


Контекстно-свободная грамматика[править]

Определение:
Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — способ описания формального языка, представляющий собой четверку

[math]\Gamma =\langle \Sigma, N, S \in N, P \subset N^{+}\times (\Sigma\cup N)^{*}\rangle[/math], где:

  • [math]\Sigma[/math]алфавит, элементы которого называют терминалами (англ. terminals)
  • [math]N[/math] — множество, элементы которого называют нетерминалами (англ. nonterminals)
  • [math]S[/math] — начальный символ грамматики (англ. start symbol)
  • [math]P[/math] — набор правил вывода (англ. production rules или productions) вида [math]A \rightarrow B_1 B_2 \ldots B_n[/math], где [math]A \in N[/math], [math]B_i \in \Sigma \cup N[/math], то есть у которых левые части — одиночные нетерминалы, а правые — последовательности терминалов и нетерминалов.

Пример[править]

Терминалы [math]\Sigma = \{(, )\}[/math].

Нетерминалы [math]N = \{S\}[/math].

Правила вывода [math]P[/math]:

[math]\begin{array}{l l} S \rightarrow \varepsilon\\ S \rightarrow SS\\ S \rightarrow (S)\\ \end{array}[/math]

Данная грамматика задает язык правильных скобочных последовательностей. Например, последовательность [math](()(()))[/math] может быть выведена следующим образом:

[math] S \Rightarrow (S) \Rightarrow (SS) \Rightarrow (()(S)) \Rightarrow (()(())) [/math]

Нормальная форма Хомского[править]

Нормальная форма Хомского — нормальная форма КС-грамматик, в которой все продукции имеют вид:

  • [math]A \rightarrow a[/math], где [math]A[/math] — нетерминал, а [math]a[/math] — терминал
  • [math]A \rightarrow BC[/math], где [math]A[/math], [math]B[/math], [math]C[/math] — нетерминалы, причем [math]B[/math] и [math]C[/math] не являются начальными нетерминалами
  • [math]S \rightarrow \varepsilon[/math], где [math]S[/math] — начальный нетерминал и [math]\varepsilon[/math] — пустая строка (данная продукция необходима, если в языке присуствует пустая строка)

Можно показать, что любую КС-грамматику можно привести к нормальной форме Хомского.

Алгоритм[править]

Алгоритм Кока-Янгера-Касами (англ. Cocke-Younger-Kasami algorithm, англ. CYK-алгоритм) — алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского. Любую КС-грамматику можно привести к НФХ, поэтому алгоритм является универсальным для любой КС-грамматики.

Будем решать задачу динамическим программированием. Дана строка [math]w[/math] размером [math]n[/math]. Заведем для неё трехмерный массив [math]d[/math] размером [math]|N| \times n \times n[/math], состоящий из логических значений, и [math]d[A][i][j] = true \ [/math] тогда и только тогда, когда из нетерминала [math]A[/math] правилами грамматики можно вывести подстроку [math]w[i \ldots j][/math].

Рассмотрим все пары [math]\lbrace \langle j, i \rangle | j-i=m \rbrace[/math], где [math]m[/math] — константа и [math]m \lt n[/math].

  • [math]i = j[/math]. Инициализируем массив для всех нетерминалов, из которых выводится какой-либо символ строки [math]w[/math]. В таком случае [math]d[A][i][i] = true \ [/math], если в грамматике [math]\Gamma[/math] присутствует правило [math]A \rightarrow w[i][/math]. Иначе [math]d[A][i][i] = false[/math].
  • [math]i \ne j[/math]. Значения для всех нетерминалов и пар [math]\lbrace \langle j', i' \rangle | j' - i' \lt m \rbrace[/math] уже вычислены, поэтому [math]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] \ \ [/math]. То есть, подстроку [math]w[i \ldots j][/math] можно вывести из нетерминала [math]A[/math], если существует продукция вида [math]A \rightarrow BC[/math] и такое [math]k[/math], что подстрока [math]w[i \ldots k][/math] выводима из [math]B[/math], а подстрока [math]w[k + 1 \ldots j][/math] выводится из [math]C[/math].

CYK rule 2.jpg

После окончания работы значение [math]d[S][1][n][/math] содержит ответ на вопрос, выводима ли данная строка в данной грамматике, где [math]S[/math] — начальный символ грамматики.

Модификации[править]

Количество способов вывести слово[править]

Если массив будет хранить целые числа, а формулу заменить на [math]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] \ \ [/math], то [math]d[A][i][j][/math] — количество способов получить подстроку [math]w[i \ldots j][/math] из нетерминала [math]A[/math].

Минимальная стоимость вывода слова[править]

Пусть [math]H(A \rightarrow BC)[/math] — стоимость вывода по правилу [math]A \rightarrow BC[/math]. Тогда, если использовать формулу [math]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) ) \ \ [/math], то [math]d[A][i][j][/math] — минимальная стоимость вывода подстроки [math]w[i \ldots j][/math] из нетерминала [math]A[/math].

Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является частным случаем задачи динамического программирования на подотрезке.

Асимптотика[править]

Обработка правил вида [math]A \rightarrow w[i][/math] выполняется за [math]O(n \cdot |\Gamma|)[/math].

Проход по всем подстрокам выполняется за [math]O(n^2)[/math]. В обработке одной подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за [math]O(n \cdot |\Gamma|)[/math]. В итоге получаем конечную сложность [math]O(n^3 \cdot |\Gamma|)[/math].

Следовательно, общее время работы алгоритма — [math]O(n^3 \cdot |\Gamma|)[/math]. Кроме того, алгоритму требуется память на массив [math]d[/math] объемом [math]O(n^2 \cdot |N|)[/math], где [math]|N|[/math] — количество нетерминалов грамматики.

Пример работы[править]

Дана грамматика правильных скобочных последовательностей [math]\Gamma[/math] в нормальной форме Хомского.

[math]\begin{array}{l l} A \rightarrow \varepsilon\ |\ BB\ |\ CD\\ B \rightarrow BB\ |\ CD\\ C \rightarrow (\\ D \rightarrow BE\ |\ )\\ E \rightarrow )\\ \end{array}[/math]

Дано слово [math]w = ()(())[/math].


Инициализация массива [math]d[/math].

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

Заполнение массива [math]d[/math].


Итерация [math]m = 1[/math].

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

Итерация [math]m = 2[/math].

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

Итерация [math]m = 3[/math].

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

Итерация [math]m = 4[/math].

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

Итерация [math]m = 5[/math].

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

См. также[править]

Источники информации[править]