Устранение эпсилон-правил

Теорема 8.2.1. Пусть язык является контекстно-свободным. Тогда язык порождается некоторой контекстно-свободной грамматикой без - правил.

Доказательство. Пусть дана контекстно-свободная грамматика , порождающая язык L. Проведем серию преобразований множества P.

Если для каких-то , , и множество P содержит правила и , но не содержит правила , то добавим это правило в P. Повторяем эту процедуру, пока возможно.

Теперь исключим из множества P все правила вида . Полученная грамматика порождает язык .

Пример 8.2.2. Рассмотрим язык L, порождаемый грамматикой

Язык порождается грамматикой