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




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


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

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

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

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




                          Содержание  Назад  Вперед