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


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



 
 

Определение. Символ <X> ОVA

называется непроизводящим, если из него не может быть выведена конечная терминальная цепочка. 

     Рассматривая правила грамматики,  можно сделать  вывод,  что если все символы правой части являются производящими, то производящим является и символ, стоящий в левой части. Последнее утверждение позволяет написать процедуру обнаружения непроизводящих символов в следующем виде:
    1. Составить список нетерминалов,  для которых найдется хотя  бы одно правило, правая часть которого не содержит нетерминалов.
    2. Если найдено такое правило,  что все нетерминалы, стоящие  в его правой части уже занесены в список,  то добавить  в  список  нетерминал, стоящий в его левой части.
    3. Если на шаге 2 список больше не пополняется,  то  получен  список всех производящих нетерминалов грамматики,  а все нетерминалы не попавшие в него являются непроизводящими.
Анализируя в соответствии с приведенными правилами следующую грамматику :
                                Г2. 0:          R = {<I>®a<I>a,

<I>®b<A>d,


<I>®c,


<A>®c<B>d,


<A>®a<A>d,


<B>®d<A>f  },

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

R' = {<I> ®a<I>a, <I>® c}.


 

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

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


  •  

     




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