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


           

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


Теорема 8.2.1.

Пусть язык

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

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

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

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

и

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

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

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

Пример 8.2.2.

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

Язык

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

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



Содержание  Назад  Вперед





Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий