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

Задача:

Пусть дана контекстно-свободная грамматика [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].

После окончания работы значение [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						●

См. также

• Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики
• Алгоритм Эрли

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

• Wikipedia — CYK algorithm
• David Rodriguez-Velazquez, "The CYK Algorithm"
• Princeton University, "The CYK Algorithm"