Бесполезный символ грамматики можно определить
следующим образом:
Определение. Символ X, который принадлежит VтU
Va называется бесполезным
в
КС-грамматике Г, если он является недостижимым или непроизводящим.
Исключить бесполезные символы из грамматики можно удаляя правила, содержащие
вначале непроизводящие, а затем недостижимые символы. В качестве иллюстрации
применения приведенных правил выполним преобразование следующей грамматики:
Вначале находим, что <А> и <В> являются непроизводящими символами
и, исключая правила с непроизводящими символами , получаем:
R' = {<I>®ac,
<C>® bc,
<C>® d }.
В полученной схеме символ <C> является недостижимым символом.
Исключая правила, содержащие этот символ, получаем:
R" = {<I>®ac
}.
Определение. КС-грамматика называется приведенной,
если она не содержит бесполезных символов.
В дальнейшем изложении рассматриваются только
приведенные КС-грамматики. Другие виды
преобразований грамматик, описываемые ниже, предназначены для исключения
правил определенного вида из схемы грамматики.