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

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

Лекция 13

Классификация языков по Хомскому (Н. Хомский 1959 г.).

Класс 0. j®Y без ограничений (модель естественных языков).

Класс 1. j®Y, где j=x₁Аx₂, y=x₁bx₂, x₁,x₂ÎV*, АÎN, bÎV⁺. Непосредственно составляющая (контекстная) грамматика (НС-грамматика). Такая грамматика является неукорачивающей.

Класс 2. А®b, где AÎN, bÎV⁺. Замена происходит без учета контекста (контекстно свободная грамматика - КС - грамматика). Если bÎV*, то грамматика будет укорачивающей (УКС) - используются при описании языков программирования.

Класс 3. Правила вывода имеют форму А®bB и А®b, где A,ВÎN, bÎT. Это язык с конечным числом состояний или автоматный (регулярный) язык. А - грамматика.

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

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

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

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

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

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

Дата добавления: 2013-12-13