Математическая теория формальных языков

         

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


Теорема 8.2.1.

Пусть язык

является контекстно-свободным. Тогда язык

порождается некоторой контекстно-свободной грамматикой без -правил.

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

Если для каких-то , ,

и

множество P содержит правила

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

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

Пример 8.2.2.

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

Язык

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

Упражнение 8.2.3. Найти контекстно-свободную грамматику без -правил, эквивалентную грамматике



Содержание раздела