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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Асимптотика)
м (Контекстно-свободная грамматика: тире)
(не показаны 24 промежуточные версии 3 участников)
Строка 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 - алгоритм''') - универсальный алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского.
+
{{Определение
Будем решать задачу [[Динамическое_программирование|динамическим программированием]]. Заведем трехмерный массив d, состоящий из логических значений, и <tex>d[A][i][j] = true</tex> тогда и только тогда, когда из нетерминала <tex>A</tex> правилами грамматики можно вывести подстроку <tex>w[i..j]</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> {{---}} пустая строка (данная продукция необходима, если в языке присуствует пустая строка)
  
Рассмотрим все пары <tex>\lbrace \langle j, i \rangle | j-i=m \rbrace</tex>, где <tex>m</tex> - константа и <tex>m < n</tex>.
+
[[Нормальная форма Хомского|Можно показать]], что любую КС-грамматику можно привести к нормальной форме Хомского.
  
=== Шаг 1. База ===
+
== Алгоритм ==
<tex>m = 0</tex>. В таком случае <tex>i = j</tex>.
+
'''Алгоритм Кока-Янгера-Касами''' (англ. ''Cocke-Younger-Kasami algorithm'', англ. ''CYK-алгоритм'') {{---}} алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского. Любую КС-грамматику можно привести к НФХ, поэтому алгоритм является универсальным для любой КС-грамматики.
  
Инициализируем массив для всех нетерминалов, из которых выводится какой-либо символ строки <tex>w</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>d[A][i][i] = true</tex>, если в грамматике <tex>\Gamma</tex> присутствует правило <tex>A \rightarrow w[i]</tex>. Иначе <tex>d[A][i][i] = false</tex>.
 
  
=== Шаг 2. Переход ===
+
Рассмотрим все пары <tex>\lbrace \langle j, i \rangle | j-i=m \rbrace</tex>, где <tex>m</tex> {{---}} константа и <tex>m < n</tex>.
[[Файл:CYK_rule_2.jpg|thumb|400px]]
 
  
<tex>m = j - i</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 \dots j]</tex> можно вывести из нетерминала <tex>A</tex>, если существует продукция вида <tex>A \rightarrow BC</tex> и такое <tex>k</tex>, что подстрока <tex>w[i \dots k]</tex> выводима из <tex>B</tex>, а подстрока <tex>w[k + 1 \dots j]</tex> - из <tex>C</tex>.
+
* <tex>i \ne j</tex>. Значения для всех нетерминалов и пар <tex>\lbrace \langle j', i' \rangle | j' - i' < m \rbrace</tex> уже вычислены, поэтому <tex>d[A][i][j] = \bigvee\limits_{A \rightarrow BC}\bigvee\limits_{k = i}^{j-1} d[B][i][k] \wedge d[C][k+1][j] \ \ </tex>. То есть, подстроку <tex>w[i \ldots j]</tex> можно вывести из нетерминала <tex>A</tex>, если существует продукция вида <tex>A \rightarrow BC</tex> и такое <tex>k</tex>, что подстрока <tex>w[i \ldots k]</tex> выводима из <tex>B</tex>, а подстрока <tex>w[k + 1 \ldots j]</tex> выводится из <tex>C</tex>.
 +
[[Файл:CYK_rule_2.jpg|400px]]
  
=== Завершение ===
+
После окончания работы значение <tex>d[S][1][n]</tex> содержит ответ на вопрос, выводима ли данная строка в данной грамматике, где <tex>S</tex> {{---}} начальный символ грамматики.
\После окончания работы значение <tex>d[S][1][n]</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>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>a_i...a_j</tex> из нетерминала <tex>A</tex>.
+
=== Количество способов вывести слово ===
 +
Если массив будет хранить целые числа, а формулу заменить на <tex>d[A][i][j] = \sum\limits_{A \rightarrow BC}\sum\limits_{k = i}^{j-1} d[B][i][k] \cdot d[C][k + 1][j] \ \ </tex>, то <tex>d[A][i][j]</tex> {{---}} количество способов получить подстроку <tex>w[i \ldots j]</tex> из нетерминала <tex>A</tex>.
  
Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является обобщением задачи динамического программирования на подотрезке.
+
=== Минимальная стоимость вывода слова ===
 +
Пусть <tex>H(A \rightarrow BC)</tex> {{---}} стоимость вывода по правилу <tex>A \rightarrow BC</tex>. Тогда, если использовать формулу <tex>d[A][i][j] = \min\limits_{A \rightarrow BC} \min\limits_{k = i}^{j-1}  ( d[B][i][k] + d[C][k + 1][j] + H(A \rightarrow BC) ) \ \ </tex>, то <tex>d[A][i][j]</tex> {{---}} минимальная стоимость вывода подстроки <tex>w[i \ldots 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> в шаге 1 выполняется за <tex>O(n \cdot |\Gamma|)</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>O(n^2)</tex>. В обработке подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за <tex>O(n \cdot |\Gamma|)</tex>. В итоге получаем конечную сложность <tex>O(n^3 \cdot |\Gamma|)</tex>.
+
Итерация <tex>m = 5</tex>.
  
Следовательно, общее время работы алгоритма - <tex>O(n^3 \cdot |\Gamma|)</tex>. Кроме того, алгоритму требуется память (на массив <tex>d</tex>) объемом <tex>O(n^2 \cdot |N|)</tex>, где <tex>|N|</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>
  
 
== См. также ==  
 
== См. также ==  
Строка 67: Строка 1895:
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Контекстно-свободные грамматики]]
 
[[Категория: Контекстно-свободные грамматики]]
 +
[[Категория: Алгоритмы разбора]]

Версия 22:51, 23 мая 2019

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


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

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

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

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

Пример

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

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

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

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

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

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

Нормальная форма Хомского

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

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

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

Алгоритм

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

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

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

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

CYK rule 2.jpg

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

Модификации

Количество способов вывести слово

Если массив будет хранить целые числа, а формулу заменить на [math]d[A][i][j] = \sum\limits_{A \rightarrow BC}\sum\limits_{k = i}^{j-1} d[B][i][k] \cdot d[C][k + 1][j] \ \ [/math], то [math]d[A][i][j][/math] — количество способов получить подстроку [math]w[i \ldots j][/math] из нетерминала [math]A[/math].

Минимальная стоимость вывода слова

Пусть [math]H(A \rightarrow BC)[/math] — стоимость вывода по правилу [math]A \rightarrow BC[/math]. Тогда, если использовать формулу [math]d[A][i][j] = \min\limits_{A \rightarrow BC} \min\limits_{k = i}^{j-1} ( d[B][i][k] + d[C][k + 1][j] + H(A \rightarrow BC) ) \ \ [/math], то [math]d[A][i][j][/math] — минимальная стоимость вывода подстроки [math]w[i \ldots j][/math] из нетерминала [math]A[/math].

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

Асимптотика

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

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

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

Пример работы

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

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

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


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

A
1 2 3 4 5 6
1
2
3
4
5
6
B
1 2 3 4 5 6
1
2
3
4
5
6
C
1 2 3 4 5 6
1
2
3
4
5
6
D
1 2 3 4 5 6
1
2
3
4
5
6
E
1 2 3 4 5 6
1
2
3
4
5
6

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


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

A
1 2 3 4 5 6
1
2
3
4
5
6
B
1 2 3 4 5 6
1
2
3
4
5
6
C
1 2 3 4 5 6
1
2
3
4
5
6
D
1 2 3 4 5 6
1
2
3
4
5
6
E
1 2 3 4 5 6
1
2
3
4
5
6

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

A
1 2 3 4 5 6
1
2
3
4
5
6
B
1 2 3 4 5 6
1
2
3
4
5
6
C
1 2 3 4 5 6
1
2
3
4
5
6
D
1 2 3 4 5 6
1
2
3
4
5
6
E
1 2 3 4 5 6
1
2
3
4
5
6

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

A
1 2 3 4 5 6
1
2
3
4
5
6
B
1 2 3 4 5 6
1
2
3
4
5
6
C
1 2 3 4 5 6
1
2
3
4
5
6
D
1 2 3 4 5 6
1
2
3
4
5
6
E
1 2 3 4 5 6
1
2
3
4
5
6

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

A
1 2 3 4 5 6
1
2
3
4
5
6
B
1 2 3 4 5 6
1
2
3
4
5
6
C
1 2 3 4 5 6
1
2
3
4
5
6
D
1 2 3 4 5 6
1
2
3
4
5
6
E
1 2 3 4 5 6
1
2
3
4
5
6

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

A
1 2 3 4 5 6
1
2
3
4
5
6
B
1 2 3 4 5 6
1
2
3
4
5
6
C
1 2 3 4 5 6
1
2
3
4
5
6
D
1 2 3 4 5 6
1
2
3
4
5
6
E
1 2 3 4 5 6
1
2
3
4
5
6

См. также

Источники информации