54
правки
Изменения
Нет описания правки
[[Файл:table.jpg|300px|thumb|right|Таблица разбора алгоритма для цепочки из шести символов. В клетку <tex>t_{34}</tex> должны быть помещены нетерминалы, из которых выводится фрагмент входной строки длиной четыре символа, начинающийся с <tex>a_{3}</tex>, т.е. это цепочка <tex>a_{3}a_{4}a_{5}a_{6}</tex>. Этот фрагмент тремя способами можно разбить на пары непустых соседних фрагментов: (1) <tex>a_{3}</tex> и <tex>a_{4}a_{5}a_{6}</tex>, (2): <tex>a_{3}a_{4}</tex> и <tex>a_{5}a_{6}</tex>, (3): <tex>a_{3}a_{4}a_{5}</tex> и <tex>a_{6}</tex>. Этим трем парам фрагментов соответствуют пары клеток, в которых могут стоять нетерминалы, из которых эти фрагменты выводятся: (1) <tex>t_{31}</tex> и <tex>t_{43}</tex>, (2): <tex>t_{32}</tex> и <tex>t_{52}</tex>, (3): <tex>t_{33}</tex> и <tex>t_{61}</tex>. Если в этих клетках находятся соответственно нетерминалы B и C и существует правило A→BC, то A заносится в <tex>t_{34}</tex>]]
= Формальная грамматика =
'''Формальная грамматика''' - способ описания формального языка, то есть некоторого подмножества слов данного конечного алфавита. Выделяют ''порождающие'' грамматики, состоящие из следующих компонентов:
* 1) Множество '''терминальных символов''' ('''терминалов''') - символов алфавита, слова над которым определяет грамматика, то есть символов, непосредственно присутствующих в словах языка.
* 2) Множество '''нетерминальных символов''' ('''нетерминалов''') - объектов, выражающих некоторые структурные части языка, не имеющие конкретного представления как слова над алфавитом (таких, как формула или часть программы).
* 3) Множество '''правил вывода''' ('''продукций''') - правил вида L → R, где:
** L - непустая последовательность терминальных и нетерминальных символов, содержищий по крайней мере один нетерминал.
** R - любая (возможно, пустая) последовательность терминальных и нетерминальных символов.
* 4) S - стартовый нетерминал.
'''Выводом''' называется последовательность строк из терминалов и нетерминалов, такая, что:
* Первая строка состоит из стартового нетерминала
* Каждая следующая строка получена из предыдущей путем замена некоторой подстроки по некоторому правилу
* Последняя строка состоит только из терминалов (и, следовательно, не может быть преобразована по правилу грамматики).
Существование в грамматике вывода для получения конкретного слова - критерий принадлежности слова языку, определяемому грамматикой.
=== Пример ===
Терминалы: a, b. Нетерминалы: S, A, B. Продукции:
* S → AB
* A → AB
* AB → ba
* A → a
* B → b
Слова, выводимые в данной грамматике: ab, ba, abb, bab, abbb, babb, ...
Слова, невыводимые в данной грамматике: a, b, baa, baba, ...
= Контекстно-свободная грамматика =
'''Контекстно-свободная грамматика ''' ('''КС-грамматика''', '''бесконтекстная грамматика''') — частный случай формальной грамматики, у которой левые части всех правил являются одиночными нетерминалами, то есть все её продукции имеют вид L → R, где L - нетерминал, а R - последовательность терминалов и нетерминалов.Для того=== Пример === Терминалы: (, чтобы определить контекстно-свободную грамматику, необходимо). Нетерминалы: S. Продукции:* 1) Задать конечное множество A - алфавитS → егоSSэлементы называют символами, а конечные последовательности симво-лов называют словами * S → (в данном алфавите);* 2S → (S) Разделить все символы алфавита A на две группы: терми-нальные Очевидно, что данная грамматика задает язык правильных скобочных последовательностей. Например, последовательность (("окончательные") и нетерминальные ("промежуточные"());) может быть выведена следующим образом:* 3S → (S) Выбрать один из нетерминальных символов, который будет считаться начальным→ (SS) →* 4(() Указать конечное число правил грамматики(продукцийS)) вида: K → Xгде K - некоторый нетерминальный символ, а X - слово, которое может состоять как из терминальных, так и не из терминальных символов.Выводом в контекстно-свободной грамматике называется последовательность слов X[0], X[1], ... ,X[n], где X[0] состоит только из начального символа, а каждое слово X[i+1] получается из X[i] заменой какого-либо нетерминального символа на слово по одному из правил грамматики.(()(()))
==Пример=Нормальная форма Хомского =
= Алгоритм Кока-Янгера-Касами =
'''Алгоритм является универсальным для всех Кока-Янгера-Касами''' (''Cocke — Younger — Kasami algorithm'', '''CYK - алгоритм''') - универсальный алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматик, которые должны быть приведены грамматике в нормальную форму нормальной форме Хомского без ε-правил. Правила такой Пусть дана строка <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 a_i</tex>, иначе <tex>false</tex>* Остальные элементы массива заполняются динамически: <tex>d[A][i, либо А→j] = \bigvee\limits_{A \Rightarrow BC}\bigvee\limits_{k = i}^{j-1} d[B][i, где a - терминалk] \wedge d[C][k+1,j]</tex>. То есть, подстроку <tex>a_i...a_j</tex> можно вывести из нетерминала <tex>A</tex>, B если существует продукция <tex>A \Rightarrow BC</tex> и C нетерминалы такое <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(n^3)</tex> (где <tex>n</tex> - длина строки) и требует <tex>O(n^2)</tex> памяти(обе оценки с точностью до константных множителей, зависящих от конкретной грамматики). В алгоритме осуществляется для каждой ячейки перебор по всем разделениям фрагмента строки Заметим, выводимого из нетерминалов в этой ячейкечто если массив будет хранить целые числа, и по всем элементам алфавита, поэтому сложность можно оценить как а формулу динамики заменить на <tex>O(nd[A][i,j] = \sum\limits_{A \Rightarrow BC}\sum\limits_{k = i}^3 {j-1} d[B][i,k] \cdot |G|)d[C][k+1,j]</tex>, где G то <tex>d[A][i,j]</tex> - алфавитколичество способов получить подстроку <tex>a_i...a_j</tex> из нетерминала <tex>A</tex>.
=ЛитератураСсылки =
* [http://www.intuit.ru/department/algorithms/mathformlang/7/]
* [http://en.wikipedia.org/wiki/CYK_algorithm Википедия - CYK algorithm]
* [http://www.ctc.msiu.ru/program/t-system/diploma/node39.html Алгоритм Кока-Янгера-Касами]
