Изменения

#перенаправление [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]'''Задача о выводе в контекстно-свободной грамматике''' - задача о том, выводимо ли данное слово в данной контекстно-свободной грамматике. '''Алгоритм Кока-Янгера-Касами''' - алгоритм, решающий данную эту задачу.

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

{{Определение|definition='''[[Формальные Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Формальная Контекстно-свободная грамматика]]''' ('''КС- способ описания формального языкаграмматика''', то есть некоторого подмножества слов данного конечного алфавита. Выделяют ''порождающие'бесконтекстная грамматика' грамматики'') — способ описания формального языка, состоящие из следующих компонентовзадающийся:

# Множество '''* Множеством <tex>\Sigma</tex> терминальных символов''' ('''терминалов''') - символов алфавита, слова над которым определяет грамматика, то есть символов, непосредственно присутствующих в словах языка.# Множество '''нетерминальных символов''' ('''нетерминалов''') - объектов, выражающих некоторые структурные части языка, не имеющие конкретного представления как слова над алфавитом (таких, как формула или часть программы).# Множество '''правил вывода''' ('''продукций''') - правил вида L &rarr; R, где:## L - непустая последовательность терминальных и * Множеством <tex>N</tex> нетерминальных символов, содержищий по крайней мере один нетерминал.## R - любая (возможно, пустая) последовательность терминальных и нетерминальных символов.# S - стартовый нетерминал. '''Выводом''' называется последовательность строк из терминалов и нетерминалов, такая, что:* Первая строка состоит из стартового нетерминала* Каждая следующая строка получена из предыдущей путем замена некоторой подстроки по некоторому правилу* Последняя строка состоит только из терминалов (и, следовательно, не может быть преобразована по правилу грамматики). Существование в грамматике вывода для получения конкретного слова - критерий принадлежности слова языку, определяемому грамматикой. === Пример === Терминалы: {a, b}. Нетерминалы: {Стартовым нетерминалом <tex>S, A, B}. Продукции:* S &rarr; AB\in N</tex>* Множеством продукций вида <tex>A &rarr; AB* AB &rarr; ba* A &rarr; a* B &rarr; b Слова, выводимые в данной грамматике: ab, ba, abb, bab, abbb, babb, .\rightarrow B_1 B_2 .. Слова, невыводимые в данной грамматике: a, b, baa, baba, ... == Контекстно-свободная грамматика == '''[[Контекстно-свободные грамматикиB_n</tex>, выводгде <tex>A \in N</tex>, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная грамматика]]''' ('''КС-грамматика''', '''бесконтекстная грамматика''') — частный случай формальной грамматики<tex>B_i \in \Sigma \cup N</tex>, то есть у которой которых левые части всех правил являются одиночными нетерминалами, то есть все её продукции имеют вид L &rarr; R, где L - нетерминалодиночные нетерминалы, а R правые - последовательность последовательности терминалов и нетерминалов.}}

* <tex> S &rarr; \Rightarrow (S) &rarr; \Rightarrow (SS) &rarr; \Rightarrow (()(S)) &rarr; \Rightarrow (()(()))</tex>

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

Пусть дана строка <tex>a_1 a_2 ... a_n</tex>. Заведем трехмерный массив d, состоящий из логических значений, и <tex>d[A][,i,j] = true</tex> тогда и только тогда, когда из нетерминала <tex>A</tex> правилами грамматики можно вывести подстроку <tex>a_i a_{i+1} ... a_j</tex>. Тогда:* <tex>d[A][,i,i] = true</tex>, если в грамматике присутствует правило <tex>A \Rightarrow rightarrow a_i</tex>, иначе <tex>false</tex>* Остальные элементы массива заполняются динамически: <tex>d[A][,i,j] = \bigvee\limits_{A \Rightarrow rightarrow BC}\bigvee\limits_{k = i}^{j-1} d[B][,i,k] \wedge d[C][,k+1,j]</tex>. То есть, подстроку <tex>a_i...a_j</tex> можно вывести из нетерминала <tex>A</tex>, если существует продукция <tex>A \Rightarrow rightarrow BC</tex> и такое <tex>k</tex>, что подстрока <tex>a_i...a_k</tex> выводима из <tex>B</tex>, а подстрока <tex>a_{k+1}...a_j</tex> - из <tex>C</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>a_i...a_j</tex> из нетерминала <tex>A</tex>.

Значение Пусть <tex>P_{A \rightarrow BC}</tex> - ''стоимость'' вывода по правилу <tex>A \rightarrow BC</tex>. Тогда, если использовать формулу <tex>d[SA,i,j]= \min\limits_{A \rightarrow BC} \min\limits_{k = i}^{j-1} ( d[B,i,k] + d[C,k+1,nj]+ P_{A \rightarrow BC} )</tex> содержит ответ на вопрос, выводима ли данная строка в данной грамматикето <tex>d[A,i,j]</tex> - минимальная стоимость вывода подстроки <tex>a_i...a_j</tex> из нетерминала <tex>A</tex>.

ОчевидноТаким образом, что алгоритм работает за время <tex>O(n^3)</tex> (где <tex>n</tex> задача о выводе в КС- длина строки) и требует <tex>O(n^2)</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>a_i...a_j</tex> из нетерминала <tex>A</tex>.= Сложность алгоритма ===

Пусть , <tex>P_{A \Rightarrow BC}</tex> - ''стоимость'' вывода по правилу <tex>A \Rightarrow BCn</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]m</tex> - минимальная стоимость количество правил вывода подстроки <tex>a_i...a_j</tex> из нетерминала <tex>A</tex>в грамматике.

Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является обобщением задачи динамического программирования на подотрезкеОбработка правил вида <tex>A \rightarrow a_i</tex> выполняется за <tex>O(nm)</tex>.

<tex>a_1...a_n</tex> Следовательно, общее время работы алгоритма - входная строка. <tex>A_1...A_mO(n^3 m)</tex> - нетерминалы.<tex>P[iКроме того,j,k] = trueалгоритму требуется память (на массив </tex> если есть продукция <tex>A_i \Rightarrow A_j A_kd</tex>.<tex>S(i,c) = true</tex> если есть продукция объемом <tex>A_i \Rightarrow c</tex> O(где <tex>c</tex> - терминалn^2 m).<tex>d[i][j,k]</tex> - можно ли вывести из нетерминала <tex>A_i</tex> подстроку <tex>a_j...a_k</tex>.

for i = 1 to m for j = 1 to n d[i][j,j] = S(i,a[j])Псевдокод ===

for l = 2 to function CYK (a - строка длины n, G - набор правил вывода грамматики с m нетерминалами, S - стартовый нетерминал) -> bool begin d : array [1..m,1..n,1..n] of bool for i = 1 to n+1-l for j = 1 to mif (A -> a[i] - продукция) d[j][A,i,i+l] = true for len = 1 to n-1] for i = false1 to n-l for (A -> BC - продукция) for k = i to i+jlen-21 d[j][A,i,i+l-1len] = d[j][A,i,i+l-1len] or (d[j][B,i,k] and d[j][C,k+1,i+l-len]) return d[S,1,n]) end