Изменения

{{Определение|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>, то есть у которой которых левые части всех продукций- одиночные нетерминалы, а правые - последовательности терминалов и нетерминалов.}} === Пример === Терминалы: {(правил этой грамматики, ) являются одиночными нетерминалами}. Нетерминалы: {S}.Продукции:* S &rarr; SS* S &rarr; ()* S &rarr; (S) Для тогоДанная грамматика задает язык правильных скобочных последовательностей. Например, чтобы определить контекстнопоследовательность (()(())) может быть выведена следующим образом:* <tex> S \Rightarrow (S) \Rightarrow (SS) \Rightarrow (()(S)) \Rightarrow (()(())) </tex> == Нормальная форма Хомского == '''[[Нормальная форма Хомского]]''' -свободную грамматикунормальная форма КС-грамматик, необходимов которой все продукции имеют вид:* 1) Задать конечное множество A &rarr; a, где ''A'' - алфавит; егоэлементы называют символаминетерминал, а конечные последовательности симво''a'' -терминаллов называют словами (в данном алфавите)* A &rarr;BC, где ''A'', ''B'', ''C'' - нетерминалы, причем ''B'' и ''C'' не являются начальными нетерминалами* 2) Разделить все символы алфавита A на две группы: термиS &rarr; ε, где S -нальные ("окончательные") начальный нетерминал и нетерминальные ε - пустая строка ("промежуточные"данная продукция необходима, если в языке присуствует пустая строка);* 3) Выбрать один из нетерминальных символов[[Нормальная форма Хомского|Можно показать]], который будет считаться начальным;что любую КС-грамматику можно привести к нормальной форме Хомского.* 4) Указать конечное число правил грамматики вида: K = Алгоритм Кока-> XЯнгера-Касами =где K '''Алгоритм Кока-Янгера-Касами''' (''Cocke — Younger — Kasami algorithm'', '''CYK - алгоритм''') - некоторый нетерминальный символуниверсальный алгоритм, позволяющий по слову узнать, а X выводимо ли оно в заданной КС- словограмматике в нормальной форме Хомского. Пусть дана строка <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>, если в контекстно-свободной грамматике называется последовательность слов Xприсутствует правило <tex>A \rightarrow a_i</tex>, иначе <tex>false</tex>* Остальные элементы массива заполняются динамически: <tex>d[0A,i,j]= \bigvee\limits_{A \rightarrow BC}\bigvee\limits_{k = i}^{j-1} d[B, Xi,k] \wedge d[C,k+1,j]</tex>. То есть, подстроку <tex>a_i... a_j</tex> можно вывести из нетерминала <tex>A</tex>, если существует продукция <tex>A \rightarrow BC</tex> и такое <tex>k</tex>,Xчто подстрока <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> содержит ответ на вопрос, выводима ли данная строка в данной грамматике. Заметим, что если массив будет хранить целые числа, где Xа формулу заменить на <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[0A,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, а каждое слово Xi,j] = \min\limits_{A \rightarrow BC} \min\limits_{k = i}^{j-1} ( d[B,i,k] + d[C,k+1,j] получается из X+ P_{A \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 a_i</tex> выполняется за <tex>O(nm)</tex>. Проход по всем подстрокам выполняется за <tex>O(n^2)</tex>. В обработке подстроки присутствует цикл по всем правилам вывода и по одному из всем разбиениям на две подстроки, следовательно обработка работает за <tex>O(nm)</tex>. В итоге - <tex>O(n^3 m)</tex>. Следовательно, общее время работы алгоритма - <tex>O(n^3 m)</tex>. Кроме того, алгоритму требуется память (на массив <tex>d</tex>) объемом <tex>O(n^2 m)</tex>. === Псевдокод ===  function CYK (a - строка длины n, G - набор правил вывода грамматикис m нетерминалами, S - стартовый нетерминал) -> bool 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 len = 1 to n-1 for i = 1 to n-l for (A -> BC - продукция) for k = i to i+len-1 d[A,i,i+len] = d[A,i,i+len] or (d[B,i,k] and d[C,k+1,i+len]) return d[S,1,n] end = Ссылки = * [http://en.wikipedia.org/wiki/CYK_algorithm Википедия - CYK algorithm]* [http://www.ctc.msiu.ru/program/t-system/diploma/node39.html Алгоритм Кока-Янгера-Касами]