Редактирование: Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 3: Строка 3:
 
Пусть дана [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]] <tex>\Gamma</tex> в [[нормальная форма Хомского|нормальной форме Хомского]] и слово <tex>w \in \Sigma^{*}</tex>. Требуется выяснить, выводится ли это слово в данной грамматике.
 
Пусть дана [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]] <tex>\Gamma</tex> в [[нормальная форма Хомского|нормальной форме Хомского]] и слово <tex>w \in \Sigma^{*}</tex>. Требуется выяснить, выводится ли это слово в данной грамматике.
 
}}
 
}}
 
== Контекстно-свободная грамматика ==
 
{{Определение
 
|definition =
 
'''[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная грамматика]]''' ('''КС-грамматика''', '''бесконтекстная грамматика''') {{---}} способ описания формального языка, представляющий собой четверку
 
<tex>\Gamma =\langle \Sigma, N, S \in N, P \subset N^{+}\times (\Sigma\cup N)^{*}\rangle</tex>, где:
 
* <tex>\Sigma</tex> {{---}} [[Основные_определения: алфавит, слово, язык, конкатенация, свободный моноид слов|алфавит]], элементы которого называют '''терминалами''' (англ. ''terminals'')
 
* <tex>N</tex> {{---}} множество, элементы которого называют '''нетерминалами''' (англ. ''nonterminals'')
 
* <tex>S</tex> {{---}} начальный символ грамматики (англ. ''start symbol'')
 
* <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>, то есть у которых левые части {{---}} одиночные нетерминалы, а правые {{---}} последовательности терминалов и нетерминалов.
 
}}
 
=== Пример ===
 
 
Терминалы <tex>\Sigma = \{(, )\}</tex>.
 
 
Нетерминалы <tex>N = \{S\}</tex>.
 
 
Правила вывода <tex>P</tex>:
 
 
<tex>\begin{array}{l l} 
 
S \rightarrow \varepsilon\\
 
S \rightarrow SS\\
 
S \rightarrow (S)\\
 
\end{array}</tex>
 
 
Данная грамматика задает язык [[Правильные_скобочные_последовательности|правильных скобочных последовательностей]]. Например, последовательность <tex>(()(()))</tex> может быть выведена следующим образом:
 
 
<tex> S \Rightarrow (S) \Rightarrow (SS) \Rightarrow (()(S)) \Rightarrow (()(())) </tex>
 
 
== Нормальная форма Хомского ==
 
 
'''[[Нормальная форма Хомского]]''' {{---}} нормальная форма КС-грамматик, в которой все продукции имеют вид:
 
* <tex>A \rightarrow a</tex>, где <tex>A</tex> {{---}} нетерминал, а <tex>a</tex> {{---}} терминал
 
* <tex>A \rightarrow BC</tex>, где <tex>A</tex>, <tex>B</tex>, <tex>C</tex> {{---}} нетерминалы, причем <tex>B</tex> и <tex>C</tex> не являются начальными нетерминалами
 
* <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>|\Gamma| \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 \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>.
+
* <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>.
 
[[Файл:CYK_rule_2.jpg|400px]]
 
[[Файл:CYK_rule_2.jpg|400px]]
  
Строка 58: Строка 20:
  
 
=== Количество способов вывести слово ===
 
=== Количество способов вывести слово ===
Если массив будет хранить целые числа, а формулу заменить на <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>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>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>.
+
Пусть <tex>P(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] + P(A \rightarrow BC) )</tex>, то <tex>d[A][i][j]</tex> {{---}} минимальная стоимость вывода подстроки <tex>w[i \dots j]</tex> из нетерминала <tex>A</tex>.
  
Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является частным случаем задачи динамического программирования на подотрезке.
+
Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является обобщением задачи динамического программирования на подотрезке.
  
 
== Асимптотика ==
 
== Асимптотика ==
Обработка правил вида <tex>A \rightarrow w[i]</tex> выполняется за <tex>O(n \cdot |\Gamma|)</tex>.
+
Обработка правил вида <tex>A \rightarrow w[i]</tex> в шаге 1 выполняется за <tex>O(n \cdot |\Gamma|)</tex>.
  
Проход по всем подстрокам выполняется за <tex>O(n^2)</tex>. В обработке одной подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за <tex>O(n \cdot |\Gamma|)</tex>. В итоге получаем конечную сложность <tex>O(n^3 \cdot |\Gamma|)</tex>.
+
Проход по всем подстрокам в шаге 2 выполняется за <tex>O(n^2)</tex>. В обработке одной подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за <tex>O(n \cdot |\Gamma|)</tex>. В итоге получаем конечную сложность <tex>O(n^3 \cdot |\Gamma|)</tex>.
  
Следовательно, общее время работы алгоритма {{---}} <tex>O(n^3 \cdot |\Gamma|)</tex>. Кроме того, алгоритму требуется память на массив <tex>d</tex> объемом <tex>O(n^2 \cdot |N|)</tex>, где <tex>|N|</tex> {{---}}  количество [[Формальные_грамматики#Определения|нетерминалов]] грамматики.
+
Следовательно, общее время работы алгоритма {{---}} <tex>O(n^3 \cdot |\Gamma|)</tex>. Кроме того, алгоритму требуется память (на массив <tex>d</tex>) объемом <tex>O(n^2 \cdot |N|)</tex>, где <tex>|N|</tex> {{---}}  количество [[Формальные_грамматики#Определения|нетерминалов]] грамматики.
  
 
== Пример работы ==
 
== Пример работы ==
Дана грамматика [[Правильные_скобочные_последовательности|правильных скобочных последовательностей]] <tex>\Gamma</tex> в нормальной форме Хомского.
+
Дана грамматика [[Правильные_скобочные_последовательности|правильных скобочных последовательностей]] <tex>\Gamma</tex>:
  
 
<tex>\begin{array}{l l}   
 
<tex>\begin{array}{l l}   
A \rightarrow \varepsilon\ |\ BB\ |\ CD\\
+
    A \rightarrow \varepsilon|BC\\
B \rightarrow BB\ |\ CD\\
+
    D \rightarrow BC\\
C \rightarrow (\\
+
    B \rightarrow (\\
D \rightarrow BE\ |\ )\\
+
    C \rightarrow )|DE\\
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" style="background:#ffdead;"|A
+
! colspan="7"|A
 
|-
 
|-
 
!  
 
!  
Строка 106: Строка 70:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 2
 
! 2
Строка 114: Строка 79:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 3
 
! 3
Строка 122: Строка 88:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 4
 
! 4
Строка 130: Строка 97:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 138: Строка 106:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 146: Строка 115:
 
|  
 
|  
 
|  
 
|  
 +
 
|}
 
|}
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
! colspan="7" style="background:#ffdead;"|B
+
! colspan="7"|B
 
|-
 
|-
 
!  
 
!  
Строка 159: Строка 129:
 
|-
 
|-
 
! 1
 
! 1
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 164: Строка 135:
 
|  
 
|  
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 2
 
! 2
Строка 173: Строка 144:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 3
 
! 3
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 4
 
! 4
Строка 186: Строка 159:
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 5
 
! 5
Строка 197: Строка 171:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 205: Строка 180:
 
|  
 
|  
 
|  
 
|  
 +
 
|}
 
|}
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
! colspan="7" style="background:#ffdead;"|C
+
! colspan="7"|C
 
|-
 
|-
 
!  
 
!  
Строка 218: Строка 194:
 
|-
 
|-
 
! 1
 
! 1
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
Строка 224: Строка 199:
 
|  
 
|  
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 2
 
! 2
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 3
 
! 3
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 4
 
! 4
Строка 245: Строка 224:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 254: Строка 234:
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 6
 
! 6
Строка 263: Строка 244:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 +
 
 
|}
 
|}
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
! colspan="7" style="background:#ffdead;"|D
+
! colspan="7"|D
 
|-
 
|-
 
!  
 
!  
Строка 283: Строка 265:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 2
 
! 2
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 3
 
! 3
Строка 299: Строка 283:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 4
 
! 4
Строка 307: Строка 292:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 313: Строка 299:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 322: Строка 309:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
 +
 
 
|}
 
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; "  
! colspan="7" style="background:#ffdead;"|E
+
! colspan="7"|E
 
|-
 
|-
 
!  
 
!  
Строка 342: Строка 330:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 2
 
! 2
Строка 350: Строка 339:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 3
 
! 3
Строка 358: Строка 348:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 4
 
! 4
Строка 366: Строка 357:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 374: Строка 366:
 
| align="center"| ●  
 
| align="center"| ●  
 
|  
 
|  
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 382: Строка 375:
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
 +
 
|}
 
|}
<div style="clear:both;"></div>
+
{| clear="both" |}
 +
{| clear="both" |}
  
 
Заполнение массива <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" style="background:#ffdead;"|A
+
! colspan="7"|A
 
|-
 
|-
 
!  
 
!  
Строка 408: Строка 405:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 2
 
! 2
Строка 416: Строка 414:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 3
 
! 3
Строка 424: Строка 423:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 4
 
! 4
Строка 432: Строка 432:
 
| align="center"| ●  
 
| align="center"| ●  
 
|  
 
|  
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 440: Строка 441:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 448: Строка 450:
 
|  
 
|  
 
|  
 
|  
 +
 
|}
 
|}
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
! colspan="7" style="background:#ffdead;"|B
+
! colspan="7"|B
 
|-
 
|-
 
!  
 
!  
Строка 461: Строка 464:
 
|-
 
|-
 
! 1
 
! 1
 +
| align="center"| ●
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 2
 
! 2
Строка 475: Строка 479:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 3
 
! 3
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 4
 
! 4
Строка 488: Строка 494:
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 499: Строка 506:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 507: Строка 515:
 
|  
 
|  
 
|  
 
|  
 +
 
|}
 
|}
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
! colspan="7" style="background:#ffdead;"|C
+
! colspan="7"|C
 
|-
 
|-
 
!  
 
!  
Строка 520: Строка 529:
 
|-
 
|-
 
! 1
 
! 1
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
Строка 526: Строка 534:
 
|  
 
|  
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 2
 
! 2
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 3
 
! 3
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 4
 
! 4
Строка 547: Строка 559:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 556: Строка 569:
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 6
 
! 6
Строка 565: Строка 579:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 +
 
 
|}
 
|}
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
! colspan="7" style="background:#ffdead;"|D
+
! colspan="7"|D
 
|-
 
|-
 
!  
 
!  
Строка 580: Строка 595:
 
! 1
 
! 1
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 2
 
! 2
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 3
 
! 3
Строка 601: Строка 618:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 4
 
! 4
Строка 607: Строка 625:
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 5
 
! 5
Строка 615: Строка 634:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 624: Строка 644:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
 +
 
 
|}
 
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; "  
! colspan="7" style="background:#ffdead;"|E
+
! colspan="7"|E
 
|-
 
|-
 
!  
 
!  
Строка 644: Строка 665:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 2
 
! 2
Строка 652: Строка 674:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 3
 
! 3
Строка 660: Строка 683:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 4
 
! 4
Строка 668: Строка 692:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 676: Строка 701:
 
| align="center"| ●  
 
| align="center"| ●  
 
|  
 
|  
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 684: Строка 710:
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
 +
 
|}
 
|}
<div style="clear:both;"></div>
+
{| clear="both" |}
 +
 
 +
Итерация 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" style="background:#ffdead;"|A
+
! colspan="7"|A
 
|-
 
|-
 
!  
 
!  
Строка 707: Строка 735:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 2
 
! 2
Строка 715: Строка 744:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 3
 
! 3
Строка 723: Строка 753:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 4
 
! 4
Строка 731: Строка 762:
 
| align="center"| ●  
 
| align="center"| ●  
 
|  
 
|  
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 739: Строка 771:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 747: Строка 780:
 
|  
 
|  
 
|  
 
|  
 +
 
|}
 
|}
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
! colspan="7" style="background:#ffdead;"|B
+
! colspan="7"|B
 
|-
 
|-
 
!  
 
!  
Строка 760: Строка 794:
 
|-
 
|-
 
! 1
 
! 1
 +
| align="center"| ●
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 2
 
! 2
Строка 774: Строка 809:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 3
 
! 3
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 4
 
! 4
Строка 787: Строка 824:
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 798: Строка 836:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 806: Строка 845:
 
|  
 
|  
 
|  
 
|  
 +
 
|}
 
|}
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
! colspan="7" style="background:#ffdead;"|C
+
! colspan="7"|C
 
|-
 
|-
 
!  
 
!  
Строка 819: Строка 859:
 
|-
 
|-
 
! 1
 
! 1
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
Строка 825: Строка 864:
 
|  
 
|  
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 2
 
! 2
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 3
 
! 3
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 4
 
! 4
Строка 846: Строка 889:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 855: Строка 899:
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 6
 
! 6
Строка 864: Строка 909:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 +
 
 
|}
 
|}
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
! colspan="7" style="background:#ffdead;"|D
+
! colspan="7"|D
 
|-
 
|-
 
!  
 
!  
Строка 879: Строка 925:
 
! 1
 
! 1
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 2
 
! 2
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 3
 
! 3
Строка 900: Строка 948:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 4
 
! 4
Строка 906: Строка 955:
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
| align="center"| ●
+
 
 
|-
 
|-
 
! 5
 
! 5
Строка 914: Строка 964:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 923: Строка 974:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
 +
 
 
|}
 
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; "  
! colspan="7" style="background:#ffdead;"|E
+
! colspan="7"|E
 
|-
 
|-
 
!  
 
!  
Строка 943: Строка 995:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 2
 
! 2
Строка 951: Строка 1004:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 3
 
! 3
Строка 959: Строка 1013:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 4
 
! 4
Строка 967: Строка 1022:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 975: Строка 1031:
 
| align="center"| ●  
 
| align="center"| ●  
 
|  
 
|  
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 983: Строка 1040:
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
 +
 
|}
 
|}
<div style="clear:both;"></div>
+
{| clear="both" |}
 +
 
 +
Итерация 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" style="background:#ffdead;"|A
+
! colspan="7"|A
 
|-
 
|-
 
!  
 
!  
Строка 1006: Строка 1065:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 2
 
! 2
Строка 1014: Строка 1074:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 3
 
! 3
Строка 1022: Строка 1083:
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
 +
 
|-
 
|-
 
! 4
 
! 4
Строка 1030: Строка 1092:
 
| align="center"| ●  
 
| align="center"| ●  
 
|  
 
|  
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 1038: Строка 1101:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 1046: Строка 1110:
 
|  
 
|  
 
|  
 
|  
 +
 
|}
 
|}
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
! colspan="7" style="background:#ffdead;"|B
+
! colspan="7"|B
 
|-
 
|-
 
!  
 
!  
Строка 1059: Строка 1124:
 
|-
 
|-
 
! 1
 
! 1
 +
| align="center"| ●
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 2
 
! 2
Строка 1073: Строка 1139:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 3
 
! 3
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
 
 
|-
 
|-
 
! 4
 
! 4
Строка 1086: Строка 1154:
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 1097: Строка 1166:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 1105: Строка 1175:
 
|  
 
|  
 
|  
 
|  
 +
 
|}
 
|}
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
! colspan="7" style="background:#ffdead;"|C
+
! colspan="7"|C
 
|-
 
|-
 
!  
 
!  
Строка 1118: Строка 1189:
 
|-
 
|-
 
! 1
 
! 1
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
Строка 1124: Строка 1194:
 
|  
 
|  
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 2
 
! 2
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 3
 
! 3
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 4
 
! 4
Строка 1145: Строка 1219:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 1154: Строка 1229:
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 6
 
! 6
Строка 1163: Строка 1239:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 +
 
 
|}
 
|}
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
! colspan="7" style="background:#ffdead;"|D
+
! colspan="7"|D
 
|-
 
|-
 
!  
 
!  
Строка 1178: Строка 1255:
 
! 1
 
! 1
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 2
 
! 2
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 3
 
! 3
Строка 1198: Строка 1277:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 +
 
 
|-
 
|-
 
! 4
 
! 4
Строка 1205: Строка 1285:
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
| align="center"| ●
+
 
 
|-
 
|-
 
! 5
 
! 5
Строка 1213: Строка 1294:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 1222: Строка 1304:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
 +
 
 
|}
 
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; "  
! colspan="7" style="background:#ffdead;"|E
+
! colspan="7"|E
 
|-
 
|-
 
!  
 
!  
Строка 1242: Строка 1325:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 2
 
! 2
Строка 1250: Строка 1334:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 3
 
! 3
Строка 1258: Строка 1343:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 4
 
! 4
Строка 1266: Строка 1352:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 1274: Строка 1361:
 
| align="center"| ●  
 
| align="center"| ●  
 
|  
 
|  
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 1282: Строка 1370:
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
 +
 
|}
 
|}
<div style="clear:both;"></div>
+
{| clear="both" |}
 +
 
 +
Итерация 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" style="background:#ffdead;"|A
+
! colspan="7"|A
 
|-
 
|-
 
!  
 
!  
Строка 1305: Строка 1395:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 2
 
! 2
Строка 1313: Строка 1404:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 3
 
! 3
Строка 1321: Строка 1413:
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
 +
 
|-
 
|-
 
! 4
 
! 4
Строка 1329: Строка 1422:
 
| align="center"| ●  
 
| align="center"| ●  
 
|  
 
|  
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 1337: Строка 1431:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 1345: Строка 1440:
 
|  
 
|  
 
|  
 
|  
 +
 
|}
 
|}
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
! colspan="7" style="background:#ffdead;"|B
+
! colspan="7"|B
 
|-
 
|-
 
!  
 
!  
Строка 1358: Строка 1454:
 
|-
 
|-
 
! 1
 
! 1
 +
| align="center"| ●
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 2
 
! 2
Строка 1372: Строка 1469:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 3
 
! 3
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
 
 
|-
 
|-
 
! 4
 
! 4
Строка 1385: Строка 1484:
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 1396: Строка 1496:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 1404: Строка 1505:
 
|  
 
|  
 
|  
 
|  
 +
 
|}
 
|}
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
! colspan="7" style="background:#ffdead;"|C
+
! colspan="7"|C
 
|-
 
|-
 
!  
 
!  
Строка 1417: Строка 1519:
 
|-
 
|-
 
! 1
 
! 1
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
Строка 1423: Строка 1524:
 
|  
 
|  
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 2
 
! 2
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 3
 
! 3
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 4
 
! 4
Строка 1444: Строка 1549:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 1453: Строка 1559:
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 6
 
! 6
Строка 1462: Строка 1569:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 +
 
 
|}
 
|}
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
! colspan="7" style="background:#ffdead;"|D
+
! colspan="7"|D
 
|-
 
|-
 
!  
 
!  
Строка 1477: Строка 1585:
 
! 1
 
! 1
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 2
 
! 2
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 3
 
! 3
Строка 1497: Строка 1607:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 +
 
 
|-
 
|-
 
! 4
 
! 4
Строка 1504: Строка 1615:
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
| align="center"| ●
+
 
 
|-
 
|-
 
! 5
 
! 5
Строка 1512: Строка 1624:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 1521: Строка 1634:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
 +
 
 
|}
 
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; "  
! colspan="7" style="background:#ffdead;"|E
+
! colspan="7"|E
 
|-
 
|-
 
!  
 
!  
Строка 1541: Строка 1655:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 2
 
! 2
Строка 1549: Строка 1664:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 3
 
! 3
Строка 1557: Строка 1673:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 4
 
! 4
Строка 1565: Строка 1682:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 1573: Строка 1691:
 
| align="center"| ●  
 
| align="center"| ●  
 
|  
 
|  
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 1581: Строка 1700:
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
 +
 
|}
 
|}
<div style="clear:both;"></div>
+
{| clear="both" |}
 +
 
 +
Итерация 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" style="background:#ffdead;"|A
+
! colspan="7"|A
 
|-
 
|-
 
!  
 
!  
Строка 1603: Строка 1724:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
 +
 
 
|-
 
|-
 
! 2
 
! 2
Строка 1612: Строка 1734:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 3
 
! 3
Строка 1620: Строка 1743:
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
 +
 
|-
 
|-
 
! 4
 
! 4
Строка 1628: Строка 1752:
 
| align="center"| ●  
 
| align="center"| ●  
 
|  
 
|  
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 1636: Строка 1761:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 1644: Строка 1770:
 
|  
 
|  
 
|  
 
|  
 +
 
|}
 
|}
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
! colspan="7" style="background:#ffdead;"|B
+
! colspan="7"|B
 
|-
 
|-
 
!  
 
!  
Строка 1657: Строка 1784:
 
|-
 
|-
 
! 1
 
! 1
 +
| align="center"| ●
 +
|
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
 
 
|-
 
|-
 
! 2
 
! 2
Строка 1671: Строка 1799:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 3
 
! 3
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
 
 
|-
 
|-
 
! 4
 
! 4
Строка 1684: Строка 1814:
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 1695: Строка 1826:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 1703: Строка 1835:
 
|  
 
|  
 
|  
 
|  
 +
 
|}
 
|}
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
! colspan="7" style="background:#ffdead;"|C
+
! colspan="7"|C
 
|-
 
|-
 
!  
 
!  
Строка 1716: Строка 1849:
 
|-
 
|-
 
! 1
 
! 1
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
Строка 1722: Строка 1854:
 
|  
 
|  
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 2
 
! 2
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 3
 
! 3
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 4
 
! 4
Строка 1743: Строка 1879:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 1752: Строка 1889:
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 6
 
! 6
Строка 1761: Строка 1899:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 +
 
 
|}
 
|}
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
! colspan="7" style="background:#ffdead;"|D
+
! colspan="7"|D
 
|-
 
|-
 
!  
 
!  
Строка 1776: Строка 1915:
 
! 1
 
! 1
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
|
+
 
 
|-
 
|-
 
! 2
 
! 2
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 3
 
! 3
Строка 1796: Строка 1937:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 +
 
 
|-
 
|-
 
! 4
 
! 4
Строка 1803: Строка 1945:
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
| align="center"| ●
+
 
 
|-
 
|-
 
! 5
 
! 5
Строка 1811: Строка 1954:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 +
|
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 1820: Строка 1964:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
 +
 
 
|}
 
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; "  
! colspan="7" style="background:#ffdead;"|E
+
! colspan="7"|E
 
|-
 
|-
 
!  
 
!  
Строка 1840: Строка 1985:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 2
 
! 2
Строка 1848: Строка 1994:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 3
 
! 3
Строка 1856: Строка 2003:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 4
 
! 4
Строка 1864: Строка 2012:
 
|  
 
|  
 
|  
 
|  
 +
 
|-
 
|-
 
! 5
 
! 5
Строка 1872: Строка 2021:
 
| align="center"| ●  
 
| align="center"| ●  
 
|  
 
|  
 +
 
|-
 
|-
 
! 6
 
! 6
Строка 1880: Строка 2030:
 
|  
 
|  
 
| 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"| ●
 +
|
 +
|
 +
|
 +
|
 +
 +
|-
 +
! 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"| ●
 +
|
 +
|
 +
|
 +
|
 +
|
 +
 +
|-
 +
! 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
 +
|
 +
|
 +
|
 +
|
 +
|
 +
|
 +
 +
|-
 +
! 2
 +
|
 +
| align="center"| ●
 +
|
 +
|
 +
|
 +
|
 +
 +
|-
 +
! 3
 +
|
 +
|
 +
|
 +
|
 +
|
 +
|
 +
 +
|-
 +
! 4
 +
|
 +
|
 +
|
 +
|
 +
|
 +
| align="center"| ●
 +
 +
|-
 +
! 5
 +
|
 +
|
 +
|
 +
|
 +
| align="center"| ●
 +
|
 +
 +
|-
 +
! 6
 +
|
 +
|
 +
|
 +
|
 +
|
 +
| align="center"| ●
 +
 +
|}
 +
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
 +
! colspan="7"|D
 +
|-
 +
!
 +
! 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; "
 +
! colspan="7"|E
 +
|-
 +
!
 +
! 1
 +
! 2
 +
! 3
 +
! 4
 +
! 5
 +
! 6
 +
|-
 +
! 1
 +
|
 +
|
 +
|
 +
|
 +
|
 +
|
 +
 +
|-
 +
! 2
 +
|
 +
| align="center"| ●
 +
|
 +
|
 +
|
 +
|
 +
 +
|-
 +
! 3
 +
|
 +
|
 +
|
 +
|
 +
|
 +
|
 +
 +
|-
 +
! 4
 +
|
 +
|
 +
|
 +
|
 +
|
 +
|
 +
 +
|-
 +
! 5
 +
|
 +
|
 +
|
 +
|
 +
| align="center"| ●
 +
|
 +
 +
|-
 +
! 6
 +
|
 +
|
 +
|
 +
|
 +
|
 +
| align="center"| ●
 +
 
|}
 
|}
<div style="clear:both;"></div>
+
{| clear="both" |}
  
 
== См. также ==  
 
== См. также ==  
Строка 1895: Строка 2376:
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Контекстно-свободные грамматики]]
 
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Алгоритмы разбора]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: