Изменения

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

{{Определение|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 &rarr; R, где L - нетерминалодиночные нетерминалы, а R правые - последовательность последовательности терминалов и нетерминалов.}}

* <tex> S &rarr; \Rightarrow (S) &rarr; \Rightarrow (SS) &rarr; \Rightarrow (()(S)) &rarr; \Rightarrow (()(()))</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[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>Od[A,i,j] = \min\limits_{A \rightarrow BC} \min\limits_{k = i}^{j-1} (n^3d[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>n</tex> - длина входной строки) и требует , а <tex>O(n^2)m</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>rightarrow a_i...a_j</tex> из нетерминала выполняется за <tex>AO(nm)</tex>.

Пусть Проход по всем подстрокам выполняется за <tex>P_{A \Rightarrow BC}O(n^2)</tex> - ''стоимость'' . В обработке подстроки присутствует цикл по всем правилам вывода и по правилу <tex>A \Rightarrow BC</tex>. Тогдавсем разбиениям на две подстроки, если использовать формулу следовательно обработка работает за <tex>d[A,i,j] = \min\limits_{A \Rightarrow BC} \min\limits_{k = i}^{j-1} O( d[B,i,k] + d[C,k+1,j] + P_{A \Rightarrow BC} nm)</tex>, то <tex>d[A,i,j]</tex> . В итоге - минимальная стоимость вывода подстроки <tex>a_i...a_j</tex> из нетерминала <tex>AO(n^3 m)</tex>.

Таким образомСледовательно, задача о выводе в КСобщее время работы алгоритма -грамматике в нормальной форме Хомского является обобщением задачи динамического программирования <tex>O(n^3 m)</tex>. Кроме того, алгоритму требуется память (на подотрезкемассив <tex>d</tex>) объемом <tex>O(n^2 m)</tex>.

<tex>a</tex> - входная строка. <tex>A</tex> - нетерминалы.<tex>P[i,j,k] = true</tex> если есть продукция <tex>A_i \Rightarrow A_j A_k</tex>.<tex>S[i,j] = true</tex> если есть продукция <tex>A_i \Rightarrow a_j</tex>.<tex>d[i,j,k]</tex> - можно ли вывести из нетерминала <tex>A_i</tex> подстроку <tex>a_j...a_k</tex>.Считаем, что <tex>A_1</tex> - стартовый нетерминал.  function CYK (a: array [1..- строка длины n] of char, P: array [1..m,1..m,1..G - набор правил вывода грамматики с m] of boolнетерминалами, S: array []- стартовый нетерминал) : bool var d: array [1..m,1..n,1..n] of -> bool

for i = d : array [1 to ..m,1..n,1..n] of bool for j i = 1 to n if (A -> a[i] - продукция) d[A,i,j,ji] = S[i,j]true for l len = 2 1 to n-1 for i = 1 to n+1-l for j = 1 to m d[j,i,i+l(A -> BC -1] = falseпродукция) for k = i to i+jlen-21 d[jA,i,i+l-1len] = d[jA,i,i+l-1len] or (d[jB,i,k] and d[jC,k+1,i+l-1len]) result = return d[1S,1,n]