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



Смотрите shmelshop.ru балансировочное оборудование. | На http://www.ability-perm.ru создание логотипа. |

Пример построения грамматик


    Применение приведенных рекомендаций рассмотрим на следующем примере. Требуется построить грамматику для языка L ,терминальный словарь которого Vт = {*, |}, а цепочки, образующие язык, имеют следующую структуру:
      а) каждая цепочка начинается буквой * и заканчивается двумя буквами **.
      b) между началом и концом цепочек могут быть:
        b1) либо непустая последовательность палочек
        b2) либо несколько таких последовательностей, разделенных символами *.

      1. Вначале построим несколько цепочек заданного языка, которые могут быть представлены в следующем виде:
       

        * |**,
        * |*|*|**,
        * **|** ,
        * |*|**** .

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

        начало цепочки (символ * ),

        конец цепочки (символы ** ),

        непустая группа палочек,

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

        3. Обозначим группу палочек символом <A>, а последовательность групп палочек символом <B>.
        4. Выделенные структуры можно рассматривать как списки. Так последовательность палочек представляет собой список без разделителей, элементом которого является палочка. Правила грамматики, задающей такой список, имеют вид:

            <A> ® | <B>,


            <B> ® | <B>,


            <B> ® $.

          Последовательность групп палочек, разделенных звездочкой, представляет собой список с разделителем, элементом такого списка является группа палочек

          <A>, а разделителем - звездочка. Правила грамматики, задающей такой список, можно записать так:

              <C> ® <A><E>,


              <E> ® *<A><E>,


              <E> ® $.

            Учитывая, что каждая цепочка языка должна иметь начало и конец, и , выбирая в качестве начального символа грамматики <I>, получаем правило, определяющее общий вид цепочки:

                <I> ® *<C>**.

              5. Объединяя построенные правила, окончательно получаем схему искомой грамматики в виде:

                 

                    Г1. 19:    R = { <I> ® *<C>**,

                      <C> ® <A><E>,


                      <E> ® *<A><E>,




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