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> S → \Rightarrow (S) → \Rightarrow (SS) → \Rightarrow (()(S)) → \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 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 rightarrow BC}</tex> - ''стоимость'' вывода по правилу <tex>A \Rightarrow rightarrow BC</tex>. Тогда, если использовать формулу <tex>d[A,i,j] = \min\limits_{A \Rightarrow rightarrow BC} \min\limits_{k = i}^{j-1} ( d[B,i,k] + d[C,k+1,j] + P_{A \Rightarrow rightarrow BC} )</tex>, то <tex>d[A,i,j]</tex> - минимальная стоимость вывода подстроки <tex>a_i...a_j</tex> из нетерминала <tex>A</tex>.
Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является обобщением задачи динамического программирования на подотрезке.
Пусть, <tex>n</tex> - длина входной строки, а <tex>m</tex> - количество правил вывода в грамматике.
Обработка правил вида <tex>A \Rightarrow rightarrow a_i</tex> выполняется за <tex>O(nm)</tex>.
Проход по всем подстрокам выполняется за <tex>O(n^2)</tex>. В обработке подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за <tex>O(nm)</tex>. В итоге - <tex>O(n^3 m)</tex>.
=== Псевдокод ===
begin
d : array [1..m,1..n,1..n] of bool
for i = 1 to n
if (A -> a[i] - правило грамматикипродукция)
d[A,i,i] = true
for l len = 1 to n-1
for i = 1 to n-l
for (A -> BC - правило грамматикипродукция) for k = i to i+llen-1 d[A,i,i+llen] = d[A,i,i+llen] or (d[B,i,k] and d[C,k+1,i+llen]) result = return d[S,1,n]
end
