пользователей: 21219
предметов: 10452
вопросов: 177398
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


23. Определение порождающей грамматики. Терминальные и нетерминальные символы, правила, целевой (начальный) символ. Понятия вывода, выводимости, сентенциальной формы грамматики. Язык, порождаемый грамматикой.

Порождающей грамматикой G называется четверка G(T,N,P,S), где

T – конечное множество терминальных  (основных) символов представляет собой алфавит языка, то есть из терминальных символов и состоят цепочки языка, порождаемого грамматикой. Будем обозначать терминальные символы малыми латинскими буквами.

N – конечное множество нетерминальных символов  представляет собой вспомогательный алфавит, то есть это символы, которые используются при описании языка, но не входят в алфавит языка (слова, понятия, конструкции языка). Будем обозначать нетерминальные символы заглавными латинскими буквами.

P – множество правил вывода (продукций)  вида a ® b, aÎV+, bÎV*, где V=TÈN–полный алфавит грамматики G.

SÎN – начальный (целевой) нетерминальный символ грамматики G, с которого начинается процесс порождения цепочек языка.

Выводом называется процесс порождения цепочек языка на основе правил определяющей язык грамматики.

Цепочка b=d1gd2  называется непосредственно выводимой из цепочки a=d1wd2 в грамматике G(T,N,P,S), V=TÈN, d1,g,d2ÎV*, wÎV+, если в грамматике G существует правило w ® g Î P. Непосредственная выводимость обозначается aÞb. Т.е. цепочка b выводима из цепочки a в том случае, если можно взять несколько символов в цепочке a, заменить их на другие символы  согласно правилу грамматики и получить при этом цепочку b. В формальном определении любая из цепочек d1, d2 (или обе) может быть пустой. В пределе вся цепочка a может быть заменена на цепочку  b, тогда в грамматике должно существовать правило a ® b Î P.

Цепочка b называется выводимой из цепочки a – обозначается a Þ* b, если выполняется одно из двух следующих условий:

  • b непосредственно выводима из a: a Þ b;
  • $g, такая, что: g выводима из a и b непосредственно выводима из g (a Þ* g и g Þ b).

Цепочка символов aÎV* называется сентенциальной формой грамматики G(T,N,P,S), если она выводима из целевого символа грамматики S: S Þ* a. Если цепочка получена в результате законченного вывода, она называется сентенцией.

Язык, порождаемый грамматикой – это множество всех сентенций этой грамматики.

 


19.01.2016; 06:42
хиты: 47
рейтинг:0
Точные науки
информатика
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь