Выводимость

Рассмотрим, как грамматики используются для порождения языков. Правила грамматики используются для того, чтобы задавать способы подстановки или замены цепочек языка. Подстановка осуществляется путем замены некоторого нетерминала и в какой-нибудь заданной цепочке терминалов и нетерминалов на правую часть правила, левой частью которого является этот нетерминал (см. 4.1).

Определение: Из цепочки a непосредственно выводится цепочка b в граматике G (обозначение a®b) если:

1) цепочку a можно представить в виде конкатенации a= mtg;

2) цепочку b можно представить в виде конкатенации b= mzg;

3) в грамматике G есть правило t®z.

Пример:

a= bAaSB

b= bAbAcB

Из цепочки a®b в грамматике G₀, так как существует правило aS®bAc.

Определение: Из цепочки a выводится цепочка b в грамматике G, если цепочка b может быть получена из a за конечное число шагов применения операции непосредственной выводимости: .

Пример:

a= bAaSB, b= abcabccB

a= bAaSB®abcaSB®abcbAcB®abcabccB= b

Определение: Язык порождающей грамматики – это множество терминальных цепочек, выводимых из начальных символов грамматики (обозначается L(G)):

Промежуточные цепочки могут состоять как из терминальных, так и из нетерминальных символов.

Определение: Промежуточные цепочки будем называть сентенциальными формами (или сентенциями).

Вопросы и упражнения

Пусть грамматика G содержит следующие правила: bA®acBc, aBc®c. Выводимы ли в данной из цепочки a=acbAacaBc цепочки b= acacBcacc, g= acacBcaca ? Докажите.

Дана грамматика G: G= (Т, N, S, R), Т= {a, b}, N= {A, B, S},

R: S®aS

bA®ab

aS®bA

Какой язык задает данная грамматика? Постройте вывод цепочки языка. Приведите пример сентенциальной формы для данного вывода.