Изменения

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

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

2666 байт добавлено, 16:33, 12 сентября 2015
м
Источники информации
Пусть дана [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]] <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 ... 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>|\Gamma| \times n \times n</tex>, состоящий из логических значений, и <tex>d[A][i][j] = true</tex> тогда и только тогда, когда из нетерминала <tex>A</tex> правилами любой КС-грамматики можно вывести подстроку <tex>w[i \dots j]</tex>.
Будем решать задачу [[Динамическое_программирование|динамическим программированием]]. Дана строка <tex>w</tex> размером <tex>n</tex>. Заведем для неё трехмерный массив <tex>d</tex> размером <tex>|N| \times n \times n</tex>, состоящий из логических значений, и <tex>d[A][i][j] = true</tex> тогда и только тогда, когда из нетерминала <tex>A</tex> правилами грамматики можно вывести подстроку <tex>w[i \dots j]</tex>. Рассмотрим все пары <tex>\lbrace \langle j, i \rangle | j-i=m \rbrace</tex>, где <tex>m</tex> {{---}} константа и <tex>m \leqslant < n</tex>.
* <tex>i = j</tex>. Инициализируем массив для всех нетерминалов, из которых выводится какой-либо символ строки <tex>w</tex>. В таком случае <tex>d[A][i][i] = true</tex>, если в грамматике <tex>\Gamma</tex> присутствует правило <tex>A \rightarrow w[i]</tex>. Иначе <tex>d[A][i][i] = false</tex>.
=== Минимальная стоимость вывода слова ===
Пусть <tex>PH(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] + PH(A \rightarrow BC) )</tex>, то <tex>d[A][i][j]</tex> {{---}} минимальная стоимость вывода подстроки <tex>w[i \dots j]</tex> из нетерминала <tex>A</tex>.
Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является обобщением частным случаем задачи динамического программирования на подотрезке.
== Асимптотика ==
Обработка правил вида <tex>A \rightarrow w[i]</tex> в шаге 1 выполняется за <tex>O(n \cdot |\Gamma|)</tex>.
Проход по всем подстрокам в шаге 2 выполняется за <tex>O(n^2)</tex>. В обработке одной подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за <tex>O(n \cdot |\Gamma|)</tex>. В итоге получаем конечную сложность <tex>O(n^3 \cdot |\Gamma|)</tex>.
Следовательно, общее время работы алгоритма {{---}} <tex>O(n^3 \cdot |\Gamma|)</tex>. Кроме того, алгоритму требуется память (на массив <tex>d</tex>) объемом <tex>O(n^2 \cdot |N|)</tex>, где <tex>|N|</tex> {{---}} количество [[Формальные_грамматики#Определения|нетерминалов]] грамматики.
== Пример работы ==
Дана грамматика [[Правильные_скобочные_последовательности|правильных скобочных последовательностей]] <tex>\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>.
{| clear="both" |}
Инициализация массива <tex>d</tex>.
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|A
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 3
|
|
 
|-
! 4
|
|
 
|-
! 5
|
|
 
|-
! 6
|
|
 
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|B
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 3
|
|
 
|-
! 4
|
|
 
|-
! 5
|
|
 
|-
! 6
|
|
 
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|C
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 3
|
|
 
|-
! 4
|
|
 
|-
! 5
|
|
 
|-
! 6
|
|
 
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|D
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 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
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 3
|
|
 
|-
! 4
|
|
 
|-
! 5
| align="center"| ●
|
 
|-
! 6
|
| align="center"| ●
 
|}
{| clear<div style="clear:both;" |}></div>
Заполнение массива <tex>d</tex>.
{| clear="both" |}
 
Итерация m = <tex>1</tex>.
Итерация <tex>m = 1</tex>.
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|A
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 3
|
|
 
|-
! 4
| align="center"| ●
|
 
|-
! 5
|
|
 
|-
! 6
|
|
 
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|B
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 3
|
|
 
|-
! 4
| align="center"| ●
|
 
|-
! 5
|
|
 
|-
! 6
|
|
 
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|C
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 3
|
|
 
|-
! 4
|
|
 
|-
! 5
|
|
 
|-
! 6
|
|
 
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|D
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 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
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 3
|
|
 
|-
! 4
|
|
 
|-
! 5
| align="center"| ●
|
 
|-
! 6
|
| align="center"| ●
 
|}
{| clear<div style="clear:both;" |} Итерация m = <tex>2</texdiv>.
Итерация <tex>m = 2</tex>.
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|A
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 3
|
|
 
|-
! 4
| align="center"| ●
|
 
|-
! 5
|
|
 
|-
! 6
|
|
 
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|B
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 3
|
|
 
|-
! 4
| align="center"| ●
|
 
|-
! 5
|
|
 
|-
! 6
|
|
 
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|C
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 3
|
|
 
|-
! 4
|
|
 
|-
! 5
|
|
 
|-
! 6
|
|
 
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|D
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 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
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 3
|
|
 
|-
! 4
|
|
 
|-
! 5
| align="center"| ●
|
 
|-
! 6
|
| align="center"| ●
 
|}
{| clear<div style="clear:both;" |} Итерация m = <tex>3</texdiv>.
Итерация <tex>m = 3</tex>.
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|A
|-
!
|
|
 
|-
! 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
|-
!
|
|
 
|-
! 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
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 3
|
|
 
|-
! 4
|
|
 
|-
! 5
|
|
 
|-
! 6
|
|
 
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|D
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 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
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 3
|
|
 
|-
! 4
|
|
 
|-
! 5
| align="center"| ●
|
 
|-
! 6
|
| align="center"| ●
 
|}
{| clear<div style="clear:both;" |} Итерация m = <tex>4</texdiv>.
Итерация <tex>m = 4</tex>.
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|A
|-
!
|
|
 
|-
! 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
|-
!
|
|
 
|-
! 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
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 3
|
|
 
|-
! 4
|
|
 
|-
! 5
|
|
 
|-
! 6
|
|
 
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|D
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 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
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 3
|
|
 
|-
! 4
|
|
 
|-
! 5
| align="center"| ●
|
 
|-
! 6
|
| align="center"| ●
 
|}
{| clear<div style="clear:both;" |} Итерация m = <tex>5</texdiv>.
Итерация <tex>m = 5</tex>.
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|A
|-
!
|
| 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
|-
!
|
| 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
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 3
|
|
 
|-
! 4
|
|
 
|-
! 5
|
|
 
|-
! 6
|
|
 
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7" style="background:#ffdead;"|D
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 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
|-
!
|
|
 
|-
! 2
|
|
 
|-
! 3
|
|
 
|-
! 4
|
|
 
|-
! 5
| align="center"| ●
|
 
|-
! 6
|
| align="center"| ●
 
|}
{| clear="both" |}
 
Итерация m = <tex>6</tex>.
 
 
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7"|A
|-
!
! 1
! 2
! 3
! 4
! 5
! 6
|-
! 1
|
| align="center"| ●
|
|
|
| align="center"| ●
 
|-
! 2
|
|
|
|
|
|
 
|-
! 3
|
|
|
|
|
| align="center"| ●
 
|-
! 4
|
|
|
|
| align="center"| ●
|
 
|-
! 5
|
|
|
|
|
|
 
|-
! 6
|
|
|
|
|
|
 
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7"|B
|-
!
! 1
! 2
! 3
! 4
! 5
! 6
|-
! 1
|
| align="center"| ●
|
|
|
| align="center"| ●
 
|-
! 2
|
|
|
|
|
|
 
|-
! 3
|
|
|
|
|
| align="center"| ●
 
|-
! 4
|
|
|
|
| align="center"| ●
|
 
|-
! 5
|
|
|
|
|
|
 
|-
! 6
|
|
|
|
|
|
 
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7"|C
|-
!
! 1
! 2
! 3
! 4
! 5
! 6
|-
! 1
| align="center"| ●
|
|
|
|
|
 
|-
! 2
|
|
|
|
|
|
 
|-
! 3
|
|
| align="center"| ●
|
|
|
 
|-
! 4
|
|
|
| align="center"| ●
|
|
 
|-
! 5
|
|
|
|
|
|
 
|-
! 6
|
|
|
|
|
|
 
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"
! colspan="7"|D
|-
!
! 1
! 2
! 3
! 4
! 5
! 6
|-
! 1
|
|
|
|
|
|
 
|-
! 2
|
| align="center"| ●
|
|
|
|
 
|-
! 3
|
|
|
|
|
|
 
|-
! 4
|
|
|
|
|
| align="center"| ●
 
|-
! 5
|
|
|
|
| align="center"| ●
|
 
|-
! 6
|
|
|
|
|
| align="center"| ●
 
|}
{| border="1" class="wikitable" style="width: 150px; height: 150px; "
! colspan="7"|E
|-
!
! 1
! 2
! 3
! 4
! 5
! 6
|-
! 1
|
|
|
|
|
|
 
|-
! 2
|
| align="center"| ●
|
|
|
|
 
|-
! 3
|
|
|
|
|
|
 
|-
! 4
|
|
|
|
|
|
 
|-
! 5
|
|
|
|
| align="center"| ●
|
 
|-
! 6
|
|
|
|
|
| align="center"| ●
 
|}
{| clear<div style="clear:both;" |}></div>
== См. также ==
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Алгоритмы разбора]]

Навигация