418
правок
Изменения
м
funtion function CYK (a - строка длины n, G - набор правил вывода грамматики с m нетерминалами, S - стартовый нетерминал) -> bool
Перенаправление на Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ
#перенаправление [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]'''Задача о выводе в контекстно-свободной грамматике''' - задача о том, выводимо ли данное слово в данной контекстно-свободной грамматике. '''Алгоритм Кока-Янгера-Касами''' - алгоритм, решающий данную эту задачу.
= Определения =
== Контекстно-свободная грамматика ==
{{Определение|definition='''[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная грамматика]]''' ('''КС-грамматика''', '''бесконтекстная грамматика''') — частный случай формальной грамматикиспособ описания формального языка, задающийся: * Множеством <tex>\Sigma</tex> терминальных символов* Множеством <tex>N</tex> нетерминальных символов* Стартовым нетерминалом <tex>S \in N</tex>* Множеством продукций вида <tex>A \rightarrow B_1 B_2 ... B_n</tex>, где <tex>A \in N</tex>, <tex>B_i \in \Sigma \cup N</tex>, то есть у которой которых левые части всех правил являются одиночными нетерминалами, то есть все её продукции имеют вид L → R, где L - нетерминалодиночные нетерминалы, а R правые - последовательность последовательности терминалов и нетерминалов.}}
=== Пример ===
Значение <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[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>.
=== Псевдокод ===
begin
d : array [1..m,1..n,1..n] of bool
