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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
{{Задача
 
{{Задача
 
|definition =  
 
|definition =  
Пусть дана [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]] <tex>\Gamma</tex> в [[нормальная форма Хомского|нормальной форме Хомского]] и слово <tex>w \in \Sigma^{*}</tex>. Требуется выяснить, выводится ли это слово в данной грамматике.
+
Пусть дана [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]] грамматика <tex>\Gamma</tex> в [[нормальная форма Хомского|нормальной форме Хомского]] и слово <tex>w \in \Sigma^{*}</tex>. Требуется выяснить, выводится ли это слово в данной грамматике.
 
}}
 
}}
  
== Контекстно-свободная грамматика ==
+
== Алгоритм ==
{{Определение
+
'''Алгоритм Кока-Янгера-Касами''' (''Cocke — Younger — Kasami algorithm'', '''CYK - алгоритм''') - универсальный алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского.
|definition =  
+
Будем решать задачу [[Динамическое_программирование|динамическим программированием]]. Заведем трехмерный массив <tex>d</tex>, состоящий из логических значений, и <tex>d[A][i][j] = true</tex> тогда и только тогда, когда из нетерминала <tex>A</tex> правилами грамматики можно вывести подстроку <tex>w[i \dots j]</tex>.
'''[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная грамматика]]''' ('''КС-грамматика''', '''бесконтекстная грамматика''') {{---}} способ описания формального языка, представляющий собой четверку
 
<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>\lbrace \langle j, i \rangle | j-i=m \rbrace</tex>, где <tex>m</tex> - константа и <tex>m < n</tex>. <tex>|w| = n</tex>.
  
== Нормальная форма Хомского ==
+
=== Шаг 1. База ===
 +
<tex>m = 0</tex>. В таком случае <tex>i = j</tex>.
  
'''[[Нормальная форма Хомского]]''' {{---}} нормальная форма КС-грамматик, в которой все продукции имеют вид:
+
Инициализируем массив для всех нетерминалов, из которых выводится какой-либо символ строки <tex>w</tex>. В таком случае:
* <tex>A \rightarrow a</tex>, где <tex>A</tex> {{---}} нетерминал, а <tex>a</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>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> {{---}} пустая строка (данная продукция необходима, если в языке присуствует пустая строка)
 
  
[[Нормальная форма Хомского|Можно показать]], что любую КС-грамматику можно привести к нормальной форме Хомского.
+
=== Шаг 2. Переход ===
 +
[[Файл:CYK_rule_2.jpg|thumb|400px]]
  
== Алгоритм ==
+
<tex>m = j - i</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>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>\lbrace \langle j, i \rangle | j-i=m \rbrace</tex>, где <tex>m</tex> {{---}} константа и <tex>m < n</tex>.
+
=== Завершение ===
 
+
После окончания работы значение <tex>d[S][1][n]</tex> содержит ответ на вопрос, выводима ли данная строка в данной грамматике, где <tex>S</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>.
 
[[Файл:CYK_rule_2.jpg|400px]]
 
 
 
После окончания работы значение <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 \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>.
  
Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является частным случаем задачи динамического программирования на подотрезке.
+
Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является обобщением задачи динамического программирования на подотрезке.
 +
 
 +
== Псевдокод ==
 +
'''boolean''' CYK('''char'''[] w, '''list''' <tex>\Gamma</tex>, '''int''' S):
 +
    '''int''' n = length(w)
 +
    '''boolean''' d[<tex>|\Gamma|</tex>][n][n]
 +
    '''for''' i = 1 ... n
 +
      '''for''' (A <tex>\rightarrow</tex> w[i] <tex>\in</tex> <tex>\Gamma</tex>)
 +
          d[A][i][i] = ''true''
 +
    '''for''' m = 1 .. n - 1
 +
      '''for''' i = 1 .. n - m
 +
          '''int''' j = i + m
 +
          '''for''' (A <tex>\rightarrow</tex> BC <tex>\in</tex> <tex>\Gamma</tex>)
 +
            '''for''' k = i .. j - 1
 +
                d[A][i][j] = d[A][i][j] '''or''' d[B][i][k] '''and''' d[C][k + 1][j]
 +
'''return''' d[S][1][n]
  
 
== Асимптотика ==
 
== Асимптотика ==
Обработка правил вида <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>.
 
 
 
Следовательно, общее время работы алгоритма {{---}} <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>.
+
Проход по всем подстрокам в шаге 2 выполняется за <tex>O(n^2)</tex>. В обработке одной подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за <tex>O(n \cdot |\Gamma|)</tex>. В итоге получаем конечную сложность <tex>O(n^3 \cdot |\Gamma|)</tex>.
  
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
+
Следовательно, общее время работы алгоритма - <tex>O(n^3 \cdot |\Gamma|)</tex>. Кроме того, алгоритму требуется память (на массив <tex>d</tex>) объемом <tex>O(n^2 \cdot |N|)</tex>, где <tex>|N|</tex> - количество [[Формальные_грамматики#Определения|нетерминалов]] грамматики.
! 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>
 
  
 
== См. также ==  
 
== См. также ==  
Строка 1895: Строка 70:
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Контекстно-свободные грамматики]]
 
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Алгоритмы разбора]]
 

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

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

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

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