ЦЕПНЫЕ ПРОДУКЦИИ


Определение. ЦЕПНОЙ ПРОДУКЦИЕЙ называется продукция вида.
ТЕОРЕМА 1.2. О КС грамматике без цепных продукций.
Для произвольной КС грамматике содержащей цепные продукции вида , где существует эквивалентная ей КС грамматика не содержащая цепных продукций.

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

Зададим некоторое множество .В множество будут добавляться новые продукции, которые в последствии станут продукциями КС грамматики .
Шаг 2. Строим вспомогательное множество нетерминальных знаков , в которое включаем все нетерминальные знаки которые достижимы из нетерминального знака .

Шаг 3. Зафиксируем из множества , где , продукцию вида , где -строка не принадлежащая нетерминальным строкам из одного знака, .
Шаг 4. В множество продукций добавляем всевозможные продукции вида для всех нетерминальных знаков принадлежащих множеству .

Шаг 5. Если все продукции из множества просмотрены, то завершаем эффективную процедуру, иначе возвращаемся к шагу 3.

C. Строим КС грамматику , эквивалентную исходной КС грамматике , без цепных продукций, где в множества включаем те нетерминальные знаки, которые принадлежат продукциям множества .Аксиома .
D. Приведенная эффективная процедура результативна, то есть завершается за конечное число шагов, так как множество продукций исходной КС грамматики конечно.
E. Для любого вывода в КС грамматике строки существует вывод этой строки вэквивалентной ей КС грамматике . Верно и обратное. То есть .
Окончание доказательства.

Пример. Задана КС грамматика . Получить эквивалентную ей грамматику без цепных продукций.

Применем эффективную процедуру удаления цепных продукций.
Шаг 1. Разбиваем множество продукций на множества и , таких что , где множество цепных продукций .
Шаг 2. Строим вспомогательные множества , куда включаем все нетерминальные знаки достижимые из нетерминального знака .

Шаг 3. Зафиксируем продукцию из множества .
Шаг 4. Добавляем в множество те продукции из множества продукций у которых правая часть незменна, а левая часть является нетерминальным знаком – индексом множества, которому принадлежит исходный нетерминальный знак левой части.
Шаг 5. Если все продукции из просмотрены, завершаем эффективную процедуру, иначе повторяем шаги 3,4.

В итоге получаем КС грамматику , где
с множеством продукций .

КС грамматика полностью определена и эквивалентна исходной грамматике .

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

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