Математическая теория формальных языков
Устранение эпсилон-правил
Теорема 8.2.1.
Пусть язык
является контекстно-свободным. Тогда язык
порождается некоторой контекстно-свободной грамматикой без -правил.
Доказательство. Пусть дана контекстно-свободная грамматика , порождающая язык L. Проведем серию преобразований множества P.
Если для каких-то , ,
и
множество P содержит правила
и , но не содержит правила , то добавим это правило в P. Повторяем эту процедуру, пока возможно.
Теперь исключим из множества P все правила вида . Полученная грамматика порождает язык .
Пример 8.2.2.
Рассмотрим язык L, порождаемый грамматикой
Язык
порождается грамматикой
Упражнение 8.2.3. Найти контекстно-свободную грамматику без -правил, эквивалентную грамматике
