Контекстно-свободные языки и грамматики

V=VT∪VN (неукорачивающие КС-грамматики),

Контекстно-свободные (КС) языки определяются грамматиками типа
G(VT, VN, P, S), в которых правила Р имеют вид:

А→β, где А∈VN , β∈V*, V=VT∪VN (укорачивающие КС-грамматики).

Приведенные грамматики – это КС-грамматики, которые не содержат недостижимых и бесплодных символов, циклов и λ-правил («пустых» правил).

Для преобразования произвольной КС-грамматики к приведенному виду, необходимо удалить:

все бесплодные символы;

все недостижимые символы;

λ-правила;

цепные правила.

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