Приведение КС-грамматики к нормальному виду
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?очки ? называется цепочка, символы которой записаны в обратном порядке.
Обращение цепочки ? будем обозначать ?R.
Например, если ? = abcdef, то ?R = fedcba.
Для пустой цепочки: l = lR.
n-ой степенью цепочки ? (будем обозначать ?n) называется конкатенация n цепочек ?
?0 = l; ?n = ??n-1 = ?n-1?.
Длина цепочки - это число составляющих ее символов.
Например, если ? = abcdefg, то длина ? равна 7.
Длину цепочки ? будем обозначать |?|. Длина l равна 0.
Язык в алфавите V - это подмножество цепочек конечной длины в этом алфавите.
Обозначим через V* множество, содержащее все цепочки в алфавите V, включая пустую цепочку l.
Например, если V={0,1}, то V* = {l, 0, 1, 00, 11, 01, 10, 000, 001, 011,. }.
Обозначим через V+ множество, содержащее все цепочки в алфавите V, исключая пустую цепочку l.
Следовательно, V* = V+ U {l}.
Ясно, что каждый язык в алфавите V является подмножеством множества V*.
Известно несколько различных способов описания языков. Один из них использует порождающие грамматики. Именно этот способ описания языков используется чаще всего.
Задание
Приведение КС-грамматики к нормальному виду
Приведенные грамматики
Приведенные грамматики - это КС-грамматики, которые не содержат недостижимых и бесплодных символов, циклов и l-правил ("пустых" правил). Приведенные грамматики называют также КС-грамматиками в каноническом виде.
Для того, чтобы преобразовать произвольную КС-грамматику к приведенному виду, необходимо выполнить следующие действия:
- удалить все бесплодные символы;
- удалить все недостижимые символы;
- удалить l-правила;
- удалить цепные правила.
Следует подчеркнуть, что шаги преобразования должны выполняться именно в указанном порядке, и никак иначе.
Преобразования грамматик
В некоторых случаях КС-грамматика может содержать недостижимые и бесплодные символы, которые не участвуют в порождении цепочек языка и поэтому могут быть удалены из грамматики.
Определение: символ A СФ VN называется бесплодным в грамматике G = (VT, VN, P, S), если множество { a | a СФ VT*, A => a} пусто.
Определение: символ x СФ (VT U VN) называется недостижимым в грамматике G = (VT, VN, P, S), если он не появляется ни в одной сентенциальной форме этой грамматики.
Алгоритм удаления бесплодных символов
Вход: КС-грамматика G = (VT, VN, P, S).
Выход: КС-грамматика G = (VT, VN, P, S), не содержащая бесплодных символов, для которой L (G) = L (G).
Метод:
Рекурсивно строим множества N0, N1,.
1.N0 = , i = 1.
2.Ni = {A | (A > a) СФ P и a СФ (Ni-1 U VT) *} U Ni-1.
3.Если Ni ? Ni-1, то i = i+1 и переходим к шагу 2, иначе VN = Ni; P состоит из правил множества P, содержащих только символы из VN VT; G = (VT, VN, P, S).
Алгоритм удаления недостижимых символов
Вход: КС-грамматика G = (VT, VN, P, S)
Выход: КС-грамматика G = (VT, VN, P, S), не содержащая недостижимых символов, для которой L (G) = L (G).
Метод:
1.V0 = {S}; i = 1.
.Vi = {x | x СФ (VT U VN), (A > axb) P и A СФ Vi-1} U Vi-1.
3.Если Vi ? Vi-1, то i = i+1 и переходим к шагу 2, иначе VN = Vi VN; VT = Vi VT; P состоит из правил множества P, содержащих только символы из Vi; G = (VT, VN, P, S).
Удаление символов сопровождается удалением правил вывода, содержащих эти символы.
Если в этом алгоритме переставить шаги (1) и (2), то не всегда результатом будет правильным.
В качестве примера рассмотрим контекстно-свободную грамматику G с правилами S > U, S > VZ, T > aa, T > bb, U > aUa, U > bUb, V > aTb, V > bTa, W > YZY, W > aab, X > Xa, X > Xb, X > ?, Y > YY, Y > aU, Y > ?, Z > W, Z > b. Удалив четыре правила, содержащие бесплодный символ U, получим грамматику G1: S > VZ, T > aa, T > bb, V > aTb, V > bTa, W > YZY, W > aab, X > Xa, X > Xb, X > ?, Y > YY, Y > ?, Z > W, Z > b.
В ней символ X является недостижимым. Удалив три правила, содержащие X, получим грамматику G2 с правилами: S > VZ, T > aa, T > bb, V > aT b, V > bT a, W > YZY, W > aab, Y > YY, Y > ?, Z > W, Z > b. Очевидно, L (G) = L (G2) и грамматика G2 не содержит бесплодных и недостижимых символов.
Преобразование неукорачивающих грамматик
Последний вид рассматриваемых преобразований связан с удалением из грамматики правил с пустой правой частью.
Определение. Правило вида A > l называется "пустым" (аннулирующим) правилом.
Определение. Грамматика называется неукорачивающей или грамматикой без "пустых" правил, если либо
) схема грамматики не содержит аннулирующих правил,
) либо схема грамматики содержит только одно правило вида S > l, где S - начальный символ грамматики, и символ S не встречается в правых частях остальных правил грамматики.
Для грамматик, содержащих аннулирующие правила, справедливо следующее утверждение.
Утверждение. Для каждой КС-грамматики G', содержащей аннулирующие правила, можно построить эквивалентную ей неукорачивающую грамматику G, такую что L (G') =L (G).
Построение неукорачивающей грамматики приведет к увеличению числа правил заданной грамматики из-за построения дополнительных правил, получаемых в результате исключения нетерминалов аннулирующих правил. Чтобы построить дополнительные правила необходимо выполнить все возможные подстановки пустой цепочки вместо аннулирующего нетерминала во все правила грамматики.
Если же в грамматике есть правило вида S > l, где S - начальный символ грамматики, и символ S входит в пра