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


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


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

    а) Задана грамматика Г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

    порождает пустой язык.

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




- Начало -  - Назад -  - Вперед -