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



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


 

    Определение. Правило грамматики вида <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


          со схемой :