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


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


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

 

    Определение. Символ 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  }.

 

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

 

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

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

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

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


  •  




    - Начало -  - Назад -  - Вперед -