Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ — различия между версиями
Kabanov (обсуждение | вклад) м (→Алгоритм) |
Gaporf (обсуждение | вклад) м (→Контекстно-свободная грамматика: тире) |
||
(не показана 21 промежуточная версия 3 участников) | |||
Строка 1: | Строка 1: | ||
{{Задача | {{Задача | ||
|definition = | |definition = | ||
− | Пусть дана [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]] | + | Пусть дана [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]] <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-алгоритм'') {{---}} алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского. Любую КС-грамматику можно привести к НФХ, поэтому алгоритм является универсальным для любой КС-грамматики. | |
− | + | Будем решать задачу [[Динамическое_программирование|динамическим программированием]]. Дана строка <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> | + | * <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>\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]] | ||
− | + | После окончания работы значение <tex>d[S][1][n]</tex> содержит ответ на вопрос, выводима ли данная строка в данной грамматике, где <tex>S</tex> {{---}} начальный символ грамматики. | |
− | После окончания работы значение <tex>d[S][1][n]</tex> содержит ответ на вопрос, выводима ли данная строка в данной грамматике, где <tex>S</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 \ | + | Если массив будет хранить целые числа, а формулу заменить на <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> | + | Пусть <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>A \rightarrow w[i]</tex> выполняется за <tex>O(n \cdot |\Gamma|)</tex>. | ||
+ | |||
+ | Проход по всем подстрокам выполняется за <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>\Gamma</tex> в нормальной форме Хомского. | ||
+ | |||
+ | <tex>\begin{array}{l l} | ||
+ | A \rightarrow \varepsilon\ |\ BB\ |\ CD\\ | ||
+ | B \rightarrow BB\ |\ CD\\ | ||
+ | C \rightarrow (\\ | ||
+ | D \rightarrow BE\ |\ )\\ | ||
+ | E \rightarrow )\\ | ||
+ | \end{array}</tex> | ||
+ | |||
+ | Дано слово <tex>w = ()(())</tex>. | ||
+ | |||
+ | |||
+ | Инициализация массива <tex>d</tex>. | ||
+ | |||
+ | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
+ | ! colspan="7" style="background:#ffdead;"|A | ||
+ | |- | ||
+ | ! | ||
+ | ! 1 | ||
+ | ! 2 | ||
+ | ! 3 | ||
+ | ! 4 | ||
+ | ! 5 | ||
+ | ! 6 | ||
+ | |- | ||
+ | ! 1 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 2 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 3 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 4 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 5 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 6 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |} | ||
+ | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
+ | ! colspan="7" style="background:#ffdead;"|B | ||
+ | |- | ||
+ | ! | ||
+ | ! 1 | ||
+ | ! 2 | ||
+ | ! 3 | ||
+ | ! 4 | ||
+ | ! 5 | ||
+ | ! 6 | ||
+ | |- | ||
+ | ! 1 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 2 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 3 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 4 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 5 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 6 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |} | ||
+ | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
+ | ! colspan="7" style="background:#ffdead;"|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" style="background:#ffdead;"|D | ||
+ | |- | ||
+ | ! | ||
+ | ! 1 | ||
+ | ! 2 | ||
+ | ! 3 | ||
+ | ! 4 | ||
+ | ! 5 | ||
+ | ! 6 | ||
+ | |- | ||
+ | ! 1 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 2 | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 3 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 4 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 5 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | |- | ||
+ | ! 6 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | |} | ||
+ | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
+ | ! colspan="7" style="background:#ffdead;"|E | ||
+ | |- | ||
+ | ! | ||
+ | ! 1 | ||
+ | ! 2 | ||
+ | ! 3 | ||
+ | ! 4 | ||
+ | ! 5 | ||
+ | ! 6 | ||
+ | |- | ||
+ | ! 1 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 2 | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 3 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 4 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 5 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | |- | ||
+ | ! 6 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | |} | ||
+ | <div style="clear:both;"></div> | ||
− | + | Заполнение массива <tex>d</tex>. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | == | + | Итерация <tex>m = 1</tex>. |
− | + | ||
+ | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
+ | ! colspan="7" style="background:#ffdead;"|A | ||
+ | |- | ||
+ | ! | ||
+ | ! 1 | ||
+ | ! 2 | ||
+ | ! 3 | ||
+ | ! 4 | ||
+ | ! 5 | ||
+ | ! 6 | ||
+ | |- | ||
+ | ! 1 | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 2 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 3 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 4 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | |- | ||
+ | ! 5 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 6 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |} | ||
+ | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
+ | ! colspan="7" style="background:#ffdead;"|B | ||
+ | |- | ||
+ | ! | ||
+ | ! 1 | ||
+ | ! 2 | ||
+ | ! 3 | ||
+ | ! 4 | ||
+ | ! 5 | ||
+ | ! 6 | ||
+ | |- | ||
+ | ! 1 | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 2 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 3 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 4 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | |- | ||
+ | ! 5 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 6 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |} | ||
+ | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
+ | ! colspan="7" style="background:#ffdead;"|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" style="background:#ffdead;"|D | ||
+ | |- | ||
+ | ! | ||
+ | ! 1 | ||
+ | ! 2 | ||
+ | ! 3 | ||
+ | ! 4 | ||
+ | ! 5 | ||
+ | ! 6 | ||
+ | |- | ||
+ | ! 1 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 2 | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 3 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 4 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 5 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | |- | ||
+ | ! 6 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | |} | ||
+ | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
+ | ! colspan="7" style="background:#ffdead;"|E | ||
+ | |- | ||
+ | ! | ||
+ | ! 1 | ||
+ | ! 2 | ||
+ | ! 3 | ||
+ | ! 4 | ||
+ | ! 5 | ||
+ | ! 6 | ||
+ | |- | ||
+ | ! 1 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 2 | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 3 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 4 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 5 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | |- | ||
+ | ! 6 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | |} | ||
+ | <div style="clear:both;"></div> | ||
+ | |||
+ | Итерация <tex>m = 2</tex>. | ||
+ | |||
+ | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
+ | ! colspan="7" style="background:#ffdead;"|A | ||
+ | |- | ||
+ | ! | ||
+ | ! 1 | ||
+ | ! 2 | ||
+ | ! 3 | ||
+ | ! 4 | ||
+ | ! 5 | ||
+ | ! 6 | ||
+ | |- | ||
+ | ! 1 | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 2 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 3 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 4 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | |- | ||
+ | ! 5 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 6 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |} | ||
+ | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
+ | ! colspan="7" style="background:#ffdead;"|B | ||
+ | |- | ||
+ | ! | ||
+ | ! 1 | ||
+ | ! 2 | ||
+ | ! 3 | ||
+ | ! 4 | ||
+ | ! 5 | ||
+ | ! 6 | ||
+ | |- | ||
+ | ! 1 | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 2 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 3 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 4 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | |- | ||
+ | ! 5 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 6 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |} | ||
+ | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
+ | ! colspan="7" style="background:#ffdead;"|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" style="background:#ffdead;"|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; float: left;" | ||
+ | ! colspan="7" style="background:#ffdead;"|E | ||
+ | |- | ||
+ | ! | ||
+ | ! 1 | ||
+ | ! 2 | ||
+ | ! 3 | ||
+ | ! 4 | ||
+ | ! 5 | ||
+ | ! 6 | ||
+ | |- | ||
+ | ! 1 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 2 | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 3 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 4 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 5 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | |- | ||
+ | ! 6 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | |} | ||
+ | <div style="clear:both;"></div> | ||
+ | |||
+ | Итерация <tex>m = 3</tex>. | ||
+ | |||
+ | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
+ | ! colspan="7" style="background:#ffdead;"|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" style="background:#ffdead;"|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" style="background:#ffdead;"|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" style="background:#ffdead;"|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; float: left;" | ||
+ | ! colspan="7" style="background:#ffdead;"|E | ||
+ | |- | ||
+ | ! | ||
+ | ! 1 | ||
+ | ! 2 | ||
+ | ! 3 | ||
+ | ! 4 | ||
+ | ! 5 | ||
+ | ! 6 | ||
+ | |- | ||
+ | ! 1 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 2 | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 3 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 4 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 5 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | |- | ||
+ | ! 6 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | |} | ||
+ | <div style="clear:both;"></div> | ||
+ | |||
+ | Итерация <tex>m = 4</tex>. | ||
+ | |||
+ | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | ||
+ | ! colspan="7" style="background:#ffdead;"|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" style="background:#ffdead;"|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" style="background:#ffdead;"|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" style="background:#ffdead;"|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; float: left;" | ||
+ | ! colspan="7" style="background:#ffdead;"|E | ||
+ | |- | ||
+ | ! | ||
+ | ! 1 | ||
+ | ! 2 | ||
+ | ! 3 | ||
+ | ! 4 | ||
+ | ! 5 | ||
+ | ! 6 | ||
+ | |- | ||
+ | ! 1 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 2 | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 3 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 4 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 5 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | |- | ||
+ | ! 6 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | |} | ||
+ | <div style="clear:both;"></div> | ||
− | + | Итерация <tex>m = 5</tex>. | |
− | + | {| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;" | |
+ | ! colspan="7" style="background:#ffdead;"|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" style="background:#ffdead;"|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" style="background:#ffdead;"|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" style="background:#ffdead;"|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; float: left;" | ||
+ | ! colspan="7" style="background:#ffdead;"|E | ||
+ | |- | ||
+ | ! | ||
+ | ! 1 | ||
+ | ! 2 | ||
+ | ! 3 | ||
+ | ! 4 | ||
+ | ! 5 | ||
+ | ! 6 | ||
+ | |- | ||
+ | ! 1 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 2 | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 3 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 4 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | ! 5 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | | | ||
+ | |- | ||
+ | ! 6 | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | | ||
+ | | align="center"| ● | ||
+ | |} | ||
+ | <div style="clear:both;"></div> | ||
== См. также == | == См. также == | ||
Строка 70: | Строка 1895: | ||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
[[Категория: Контекстно-свободные грамматики]] | [[Категория: Контекстно-свободные грамматики]] | ||
+ | [[Категория: Алгоритмы разбора]] |
Версия 22:51, 23 мая 2019
Задача: |
Пусть дана контекстно-свободная грамматика в нормальной форме Хомского и слово . Требуется выяснить, выводится ли это слово в данной грамматике. |
Содержание
Контекстно-свободная грамматика
Определение: |
Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — способ описания формального языка, представляющий собой четверку
, где:
|
Пример
Терминалы
.Нетерминалы
.Правила вывода
:
Данная грамматика задает язык правильных скобочных последовательностей. Например, последовательность может быть выведена следующим образом:
Нормальная форма Хомского
Нормальная форма Хомского — нормальная форма КС-грамматик, в которой все продукции имеют вид:
- , где — нетерминал, а — терминал
- , где , , — нетерминалы, причем и не являются начальными нетерминалами
- , где — начальный нетерминал и — пустая строка (данная продукция необходима, если в языке присуствует пустая строка)
Можно показать, что любую КС-грамматику можно привести к нормальной форме Хомского.
Алгоритм
Алгоритм Кока-Янгера-Касами (англ. 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 | ● |