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


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


 

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


    со схемой :