Порождающая грамматика

Формальные языки и грамматики

Теория формальных языков занимается описанием, распознаванием и переработкой языков.

Существует два основных способа описания отдельных классов языков - с помощью порождающей процедуры (набора правил - грамматики) и с помощью распознающей процедуры (автомата).

Пусть А алфавит, тогда А* - множество всех слов над А, А⁺ - множество непустых слов на А.

Определение. Формальной порождающей грамматикой называется четверка G=<N,T,P,S>, где

Т - конечное непустое множество символов - терминальный (основной) словарь грамматики G (терминалы)

N - конечное непустое множество символов - нетерминальный (вспомогательный) словарь G (нетерминалы)

SÎN - начальный символ (аксиома) грамматики G (главный нетерминал или цель).

Р - конечное множество правил грамматики вида j®Y (продукции), при этом j,Y - цепочки в словаре V=TÈN и jÎV*NV*, YÎV*

Продукция интерпретируется как «заменить j на Y».

Обозначения:

Нетерминальные символы - А,В,С, ...

Терминальные символы - а,в,с, ...

Произвольные цепочки - a,b,g, ...

Определения:

Цепочка w¢ непосредственно выводима из цепочки w в грамматике G (wÞw¢), если w=x₁jx₂, w¢=x₁yx₂ и в Р найдется правило j®Y.

Цепочка w¢ выводима из цепочки w в G (wÞ*w¢), если найдется последовательность цепочек w=w₀,w₁, ... ,w_n=w¢, что w_iÞw_i+1 при i = 0,1, ... n-1, либо w=w¢.

Отношение Þ* называется транзитивным замыканием в G, а цепочка - выводом в G.

Множество всех цепочек терминальных символов, выводимых из аксиомы грамматики, называется языком, порожденным этой грамматикой, то есть L(G)={x | SÞ*x, xÎT*}.

Пример:

G=<N,T,P,S>, где N={I}, T={a,b,c,V,&,-,(,)}, S={I},

P={ I®(IVI), I®(I&I), I®-I, I®a, I®b, I®c }

Эта грамматика описывает язык булевых формул с переменными a,b,c.

Пример вывода: IÞ(IVI)Þ((I&I)VI)Þ((a&I)VI)Þ((a&b)VI)Þ((aVb)&c).

Описание порождения L(G) - не алгоритмическое, однако можно построить алгоритм, перечисляющий L(G).

Язык называется распознаваемым, если существует алгоритм, который за конечное число шагов распознает принадлежность языку данной цепочки. Если число шагов такого алгоритма зависит от длины цепочки и может быть оценено заранее, то такой язык называется легко распознаваемым.