Изменения

* 1) Множество '''терминальных символов''' ('''терминалов''') == Контекстно- символов алфавита, слова над которым определяет свободная грамматика, то есть символов, непосредственно присутствующих в словах языка.* 2) Множество '''нетерминальных символов''' ('''нетерминалов''') - объектов, выражающих некоторые структурные части языка, не имеющие конкретного представления как слова над алфавитом (таких, как формула или часть программы).* 3) Множество '''правил вывода''' ('''продукций''') - правил вида L → R, где:** L - непустая последовательность терминальных и нетерминальных символов, содержищий по крайней мере один нетерминал.** R - любая (возможно, пустая) последовательность терминальных и нетерминальных символов.* 4) S - стартовый нетерминал.==

{{Определение|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>, то есть у которых левые части - критерий принадлежности слова языкуодиночные нетерминалы, определяемому грамматикойа правые - последовательности терминалов и нетерминалов.}}

Терминалы: a, b. Нетерминалы: S, A, B. Продукции:* S &rarr; AB* A &rarr; AB* AB &rarr; ba* A &rarr; a* B &rarr; b Слова, выводимые в данной грамматике: ab, ba, abb, bab, abbb, babb, ... Слова, невыводимые в данной грамматике: a, b, baa, baba, ... = Контекстно-свободная грамматика = '''Контекстно-свободная грамматика''' ('''КС-грамматика''', '''бесконтекстная грамматика''') — частный случай формальной грамматики, у которой левые части всех правил являются одиночными нетерминалами, то есть все её продукции имеют вид L &rarr; R, где L - нетерминал, а R - последовательность терминалов и нетерминалов. === Пример === Терминалы: {(, )}. Нетерминалы: {S}. Продукции:

Очевидно, что данная Данная грамматика задает язык правильных скобочных последовательностей. Например, последовательность (()(())) может быть выведена следующим образом:* <tex> S &rarr; \Rightarrow (S) &rarr; \Rightarrow (SS) &rarr; \Rightarrow (()(S)) &rarr; \Rightarrow (()(()))</tex>

== Нормальная форма Хомского ==

'''[[Нормальная форма Хомского]]''' - нормальная форма КС-грамматик, в которой все продукции имеют вид:

Покажем[[Нормальная форма Хомского|Можно показать]], что любую КС-грамматику можно привести к нормальной форме Хомского. Рассмотрим продукцию этой грамматики: <tex>A \Rightarrow A_1 A_2 A_3 ... A_n</tex>, где <tex>A_i</tex> - терминалы или нетерминалы. Добавим к грамматике нетерминалы <tex>B_1 ... B_n</tex>, <tex>C_k</tex> для таких k, что <tex>A_k</tex> - нетерминал, и продукции вида* <tex>A \Rightarrow B_1</tex>* <tex>B_i \Rightarrow A_i B_{i+1}</tex> если <tex>A_i</tex> - нетерминал* <tex>B_i \Rightarrow C_i B_{i+1}</tex> и <tex>C_i \Rightarrow A_i</tex>, если <tex>A_i</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>O(nd[A,i,j] = \sum\limits_{A \rightarrow BC}\sum\limits_{k = i}^3){j-1} d[B,i,k] \cdot d[C,k+1,j]</tex> (где , то <tex>nd[A,i,j]</tex> - длина строки) и требует количество способов получить подстроку <tex>a_i...a_j</tex> из нетерминала <tex>O(n^2)A</tex> памяти (обе оценки с точностью до константных множителей, зависящих от конкретной грамматики).

ЗаметимПусть <tex>P_{A \rightarrow BC}</tex> - ''стоимость'' вывода по правилу <tex>A \rightarrow BC</tex>. Тогда, что если массив будет хранить целые числа, а использовать формулу динамики заменить на <tex>d[A][,i,j] = \summin\limits_{A \Rightarrow rightarrow BC}\summin\limits_{k = i}^{j-1} ( d[B][,i,k] \cdot + 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>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} )n</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])Псевдокод ===

// дописать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