О е-свободной грамматике.


Для произвольной КС грамматики существует эквивалентная ей КС грамматика такая, что . То есть язык порождаемый КС грамматикой эквивалентен языку порождаемому КС грамматикой с точностью до пустой строки.
Очевидно, что КС грамматика не содержит продукций вида .
ДОКАЗАТЕЛЬСТВО.
А. Пусть в продукциях КС грамматики имеются продукции вида , где .
B. Приведем эффективную процедуру эквивалентного преобразования КС — грамматики в эквивалентную ей КС – грамматику .
Шаг 1. Представим множество продукций КС грамматики как объединение непересекающихся множеств и , таких что содержит все
е-продукции из множества продукций .

Шаг 2. Фиксируем некоторую продукцию из множества .
Шаг 3. Добавляем в множество продукции из множества продукций в которых опущены е-порождающие нетерминальные знаки .
Шаг 4. Удаляем из множества выбранную продукцию и переносим из множества в множество новые е-продукции, которые появились в множестве на шаге 3.
Шаг 5. Если все е-продукции из множества просмотрены, то есть , то завершаем эффективную процедуру. Иначе переходим к шагу 2.
C. Строим грамматику следующим образом:
1. Множества содержат те терминальные и нетерминальные знаки, которые присутствуют в продукциях множества .
2. Аксиома /
3. Множество продукций содержит продукции множества полученного в пункте B.
Мы задали все четыре элемента КС грамматики следовательно мы полностью определили грамматику .
D. Приведенная в пункте B эффективная процедура результативна, то есть завершается за конечное число шагов так как мощность множества продукций конечно. Может получиться, что множество и на каждом шаге 3 будет появляться новая такая же продукция в множестве . Это может служить еще одним условием завершения эффективной процедуры.
E. Для каждого вывода в КС грамматике существует вывод в КС грамматике
результатом которой будет та же строка. Верно и обратное.

F. Если множество будет состоять из продукции когда мы остановили эффективную процедуру, удалив эту продукцию из , то тем самым мы исключили из языка пустую строку.
. Это означает, что КС грамматика эквивалентна исходной КС грамматике с точностью до пустой строки.
Окончание доказательства.

Пример. Пусть задана КС грамматика . .
Множество продукций

Применим эффективную процедуру получения эквивалентной грамматики
свободной от е-продукций.
1. , .
2. Зафиксируем из множества продукций продукцию . Тогда множество . Зафиксируем из множества продукций продукцию . Тогда множество . Зафиксируем из множества продукций продукцию . Тогда множество .Тогда множество продукций

3. Тогда получаем эквивалентную КС грамматику

Полученная КС грамматика эквивалентна исходной КС грамматике, так как они порождают одн и тот же язык .