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

Исключение цепных правил


 

    Определение. Правило грамматики вида <A> ®

    <B>,  где <A>,<B> ОVA
                             называется цепным.

 



    Утверждение. Для КС-грамматики Г, содержащей цепные правила , можно 
                       построить эквивалентную ей грамматику Г', не содержащую цепных правил.

 

    Идея доказательства заключается в следующем. Если схема грамматики имеет вид
     

        R = {...,<A> ®

        <B>,...,<B> ®

        <C>, ... , <C> ® a<X>

        },

      то такая грамматика  эквивалентна грамматике со схемой
       

          R' = {...,<A> ®

          a<X>,...},

        поскольку вывод в грамматике со схемой R цепочки a<X> :

            <A> Ю<

            B> Ю <C>

            Ю a<X>

          может быть получен  в грамматике со схемой R' с помощью правила <A>

          ® a<X>.
          В общем случае доказательство последнего утверждения можно выполнить так.
          Разобьем R на два подмножества R1 и R2, включая в R1 все правила вида <A> ® < B>.
          Для каждого правила из R1 найдем множество правил S(<Ai>), которые строятся так:
          если <Ai> Ю

          * <Aj> и в R2 есть правило <Aj>

          ® a

          , где a - цепочка словаря (Vт

          ИVA)* ,
          то в S(<Ai>) включим правило <Ai>  ®   a .
          Построим новую схему R' путем объединения правил R2 и всех построенных
          множеств S(<Ai>). Получим грамматику Г' = {Vт ,Va , I , R'}, которая эквивалентна


          заданной и не содержит правил вида <A> ®

          <B>.
          В качестве примера выполним исключение цепных правил из грамматики

          Г1. 9


          со схемой :

              Г1. 9:     

              R={<E> ®   <E> + <T> | <T>,


                                < T> ® < T> * <F> | <F>,



                                 <F> ® ( <E> ) | a}.


              Вначале разобьем правила грамматики на два подмножества:
               
                R1 = { <E> ®

                <T>,<T> ®   <F> } ,
                R2 = { <E> ®

                <E>+<T>, <T> ®

                <T>*<F>, <F>® (<E>) | a }


              Для каждого правила из R1 построим соответствующее подмножество.
               
                S(<E>) = { <E> ®<

                T>*<F>, <E> ® (<E>) | a },
                S(<T>) = { <T> ®

                (<E>) | a}


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

              R2 U S(<E>) U S(<T>) = { <E> ®

              --> <T>+<T> | <T>*<F> | (<E>) | a,


                  <T> ®

                  <T>*<F> | (<E>) | a,
                  <F> ®

                  (<E>) | a }


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


               
                Определение. Правило вида <A> ®

                $ называется аннулирующим правилом.


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

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

               


              Содержание раздела