Бесполезный символ грамматики можно определить следующим образом:
Определение. Символ X, который принадлежит Vт U VА называется бесполезным в КС-грамматике Г, если он является недостижимым или непроизводящим.
Исключить бесполезные символы из грамматики можно удаляя правила, содержащие вначале непроизводящие, а затем недостижимые символы. В качестве иллюстрации применения приведенных правил выполним преобразование следующей грамматики:
Г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 }
Определение. КС-грамматика называется приведенной, если она не содержит бесполезных символов.
В дальнейшем изложении рассматриваются только приведенные КС-грамматики. Другие виды преобразований грамматик, описываемые ниже, предназначены для исключения правил определенного вида из схемы грамматики.
