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

Определения бесполезных символов


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

 

    Определение. Символ X, который принадлежит VтU Va называется бесполезным

    в 
    КС-грамматике Г, если он является недостижимым или непроизводящим.

 

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

         Г2. 2 : R = {<I>®ac,

          <I>® b<A>,


          <A>® c<B><C>,




          <B>® a<I><A>,


          <C>® bc,


          <C>® d  }.

        Вначале находим, что <А> и <В> являются непроизводящими символами и, исключая правила с непроизводящими символами , получаем:
         

            R' = {<I>®ac,


                     <C>® bc,


                     <C>® d  }.

          В полученной схеме символ <C>  является недостижимым символом. Исключая правила, содержащие этот символ, получаем:
           

              R" = {<I>®ac  }.

             

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

             

              В дальнейшем изложении рассматриваются только

              приведенные КС-грамматики. Другие виды преобразований грамматик, описываемые ниже, предназначены для  исключения правил определенного вида из схемы грамматики.

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

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


             



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