Сборник задач по теории автоматов (стр. 4 )

b)  Строим вспомогательные множества : , , , .

c)  Фиксируем в множестве продукцию вида , например, зафиксируем продукцию .

d)  Добавляем в множество всевозможные продукции вида , т. е. .

e)  Если все продукции из просмотрены, то завершаем процедуру, иначе повторяем шаги c и d:

-  фиксируем ;

-  ;

-  фиксируем ;

-  ;

-  фиксируем ;

-  .

f)  Так как все продукции из просмотрены, то завершаем процедуру.

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

Задача 15

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

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

Решение

1.  Грамматика является КС-грамматикой, так как все её продукции имеют вид .

2.  Строим множество достижимых знаков .

a)  Задаём начальное приближение множества достижимых знаков , куда включаем аксиому достижимую по определению грамматики и те нетерминальные знаки, которые содержаться в правых частях продукций .

b)  Строим следующее приближение множества достижимых знаков , где - множество всех нетерминальных знаков из правых частей продукций вида . Тогда получаем .

c)  Повторяем шаг b до тех пор, пока приближение множества достижимых знаков на текущей итерации не сравнится с приближением множества достижимых знаков на предыдущей итерации, либо пока приближение множества достижимых знаков на текущей итерации не будет содержать все нетерминальные знаки, т. е. все знаки множества .

d)  Так как , то .

3.  Строим множество производящих знаков .

a)  Задаём начальное приближение множества производящих знаков , куда включаем те нетерминальные знаки, которые непосредственно порождают терминальные строки.

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

c)  Повторяем шаг b до тех пор, пока приближение множества производящих знаков на текущей итерации не сравнится с приближением множества производящих знаков на предыдущей итерации, либо пока приближение множества производящих знаков на текущей итерации не будет содержать все нетерминальные знаки, т. е. все знаки множества :

-  ;

-  .

d)  Так как , то .

4.  Строим приведённую грамматику .

a)  Определим множество существенных знаков .

b)  В включаем те продукции из , которые не содержат бесполезных знаков . Тогда

c)  В множество включаем те терминальные знаки из , которые встречаются в продукциях . Тогда .

Задача 16

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

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

Задача 17

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

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

Занятие 1.5. Разрешимость языков

Задача 18

Грамматика задана множеством продукций

Определить принадлежит ли строка языку .

Решение

1.  Грамматика является КС-грамматикой, так как все её продукции имеют вид . Строка является строкой в терминальном алфавите, так как .