Загрузка...

ПРИВЕДЕНИЕ КС ГРАММАТИК


Определение. ДОСТИЖИМЫМ(ВЫВОДИМЫМ) нетерминальным знаком называется такой нетерминальный знак , что в грамматике существует вывод ;  
Определение. ПРОИЗВОДЯЩИМ называется такой нетерминальный знак , что в грамматике существует вывод , .

Определение. СУЩЕСТВЕННЫЙ нетерминальный знак – это такой нетерминальный знак , который достижимый и производящий. В противном случае этот нетерминальный знак НЕСУЩЕСТВЕННЫЙ(БЕСПОЛЕЗНЫЙ).

Определение. КС грамматика называется ПРИВЕДЕННОЙ если она не содержит бесполезных нетерминальных знаков.

ТЕОРЕМА 1.3. О приведении КС грамматик.
Для любой КС грамматики существует эквивалентная ей приведенная КС грамматика .

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

Шаг 2. Множество нетерминальных знаков КС грамматики есть множество существенных знаков, то есть тех знаков, которые как достижимые, так и производящие.

Шаг 3. — это множество тех терминальных знаков, которые содержатся в правых частях продукций множества продукций .
B. Для любого вывода в КС грамматике существует вывод в грамматике и наоборот. .
Окончание доказательства.

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

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

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

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

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

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

Шаг 3. Повторяем шаг 2 до тех пор, пока множество на текущем шаге итерации не сравняется с множеством на предыдущем шаге итерации или когда
.Так как , тогда .
3. Строим приведенную грамматику .
А) Определяем множество существенных знаков как .
Б) В множество продукций включаем те продукции из множества продукций , которые не содержат бесполезных знаков.
В) Определим множество терминальных знаков куда включаем те терминальные знаки из множества , которые встречаются в продукциях множества.
Замечание. Если аксиома грамматики не производящий знак, то язык пуст. Аксиома является достижимым знаком по определению, так как любой вывод в грамматике начинается с аксиомы. Следовательно, для того, чтобы язык содержал строки, аксиома должна быть производящим нетерминальным знаком.

Загрузка...