Пред.Страница  След.Страница   Раздел   Содержание

1.2.2. Примеры, иллюстрирующие первичные понятия

Рассмотрим несколько примеров, иллюстрирующих введенные понятия:

а) Задана грамматика Г_{1. 0} и требуется определить язык, порождаемый этой грамматикой:

Г_{1. 0}:      V_т = {a, b, c}, V_a = {<I>}, R = {<I> ® abc}.
Схема грамматики содержит одно правило, поэтому Г_{1. 0} порождает язык из одного слова
L(Г_{1. 0}) = {abc}.
 b) Задана грамматика Г_{1. 1} и требуется определить язык, порождаемый этой грамматикой .
Г_{1. 1} :      V_т = {a, b, c}, V_a = {<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} :   V_a = {<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}, V_a = {<I>, <A>},
R = { <I> ® a<A>,
        <A> ® b<A>}.
Попытка построения вывода в этой грамматике приводит нас к цепочке:
<I> Ю a<A> Ю ab<A> Ю abb<A> Ю... ,
которая оказывается бесконечной. Другими словами, Г_{1. 3} порождает пустой язык.

---

Пред.Страница  След.Страница   Раздел   Содержание