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


Беговые дорожки в Алматы по материалам сайта. |

Слаборазделенные грамматики


Используя введенные понятия,  можно дать определение слаборазделенной грамматики.
 

Определение. КС-грамматика называется слаборазделенной, если выполняются 
                         следующие три условия: 

правая часть каждого правила представляет собой либо пустую цепочку $, либо начинается с терминального символа, 

если два правила имеют одинаковые левые части, то правые части правил должны начинаться разными символами, 

для каждого нетерминала A, такого что A ==>* $ множество начальных символов не должно пересекаться  с множеством символов, следующих за A.:

ПЕРВ(A) З

СЛЕД(A) = $ 
 

Используя приведенное определение, выясним, является ли следующая грамматика слаборазделенной:

    Г3. 3 

    : R = {(1) <I>  ®

    a<A> ,

               (2) <I>  ®

      b ,
               (3) <A> ®

      c<I>a ,
               (4) <A> ®

      $ }.

      Эта грамматика не содержит правил с одинаковой левой  частью, начинающихся одинаковыми терминалами, поэтому нужно проверить только условие (3) для правила (4). Вычисляя функции

          ПЕРВ(<A>) = {c} и СЛЕД(<A>) = СЛЕД(<I>) = {a},

        находим, что множество значений функции ПЕРВ(<A>) и множество значений функции СЛЕД(<A>) не имеют общих элементов. Следовательно, грамматика Г3.3 является слаборазделенной.
        Проверка выполнения условия (3) для грамматики

        Г3. 4: R = { <I>  ®

        a<I><A> | $ ,

                 <A> 

          ® a | b }

          дает следующие результаты:

              ПЕРВ(<I>) = {a} и СЛЕД(<I>) = ПЕРВ(<A>) = {a,b},

            которые показывают, что пересечение множеств ПЕРВ(<I>) и СЛЕД(<I>) не пусто. Следовательно грамматика Г3.4

            не является  слаборазделенной.
             

          Пред.Страница 

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




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