1.2.2. Примеры, иллюстрирующие первичные понятия
Рассмотрим несколько примеров, иллюстрирующих введенные понятия:
а) Задана грамматика Г1. 0 и требуется определить язык, порождаемый этой грамматикой:
Г1. 0: Vт = {a, b, c}, Va = {<I>}, R = {<I> ® abc}.
Схема грамматики содержит одно правило, поэтому Г1. 0 порождает язык из одного слова
L(Г1. 0) = {abc}.
b) Задана грамматика Г1. 1 и требуется определить язык, порождаемый этой грамматикой .
Г1. 1 : Vт = {a, b, c}, Va =
{<I>, <B>, <C>}
R = { <I> ® a<B>,
<B> ® <C>d,
<B> ® dc,
<C> ® $}.
Построим все выводы в этой грамматике:
<I> Þ a<B> Þ a<C>d Þ ad,
<I> Þ a<B> Þ adc.
Следовательно язык L(Г1. 1) = {adc, ad}.
в) Задана грамматика Г1. 2 и требуется определить язык,
порождаемый этой грамматикой .
Г1. 2 : Va = {<I>, <A>}, Vт = {0, 1},
R = {<I> ® 0<A>1,
0<A>
® 00<A>1,
<A> ® $}.
Рассмотрим несколько выводов с помощью правил грамматики Г1. 2. Применяя первое и третье правила, получаем:
<I> Þ 0<A>1 Þ 01.
Применяя два раза первое правило и третье, имеем
<I> Þ 0<A>1 Þ 00<A>11 Þ 0011.
В общем случае, применяя K раз
первое правило, получим в результате цепочку, содержащую K нулей и K единиц.
Следовательно, язык, порождаемый грамматикой Г1.
2, содержит всевозможные цепочки, в которых число нулей равно
числу единиц.
г) Задана грамматика Г1. 3 и требуется построить язык,
порождаемый этой грамматикой.
Г1. 3 : Vт = {a, b}, Va =
{<I>, <A>},
R = { <I> ® a<A>,
<A> ®
b<A>}.
Попытка построения вывода в этой грамматике приводит нас к цепочке:
<I> Þ a<A> Þ ab<A> Þ abb<A> Þ... ,
которая оказывается бесконечной. Другими словами, Г1. 3 порождает пустой язык.