Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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





Помощь в написании учебных работ
1500+ квалифицированных специалистов готовы вам помочь

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

Лекция 13

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

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

Класс 1. j®Y, где j=x1Аx2, y=x1bx2, x1,x2Î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=x1jx2, w¢=x1yx2 и в Р найдется правило j®Y.



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

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

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

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

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





Дата добавления: 2013-12-13; Просмотров: 250; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:
studopedia.su - Студопедия (2013 - 2022) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.019 сек.