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

2.  Зададим вектор, где , ,,. Строим систему уравнений относительно множеств вектора следующим образом: если в множестве есть продукции , то запишем уравнение . Тогда получим систему:

3.  Решаем систему уравнений .

a)  Задаём начальное приближение .

b)  Задаём следующее приближение . Тогда получим систему

c)  Удаляем из множеств те строки, которые не могут быть подстрокой искомой строки.

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

-  ;

-  ;

-  ;

-  ;

-  ;

-  ;

-  ;

-  .

e)  Так как искомая строка появилась в множестве , то завершаем процедуру и делаем вывод, что строка принадлежит языку .

Задача 19

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

Определить является ли язык пустым.

Решение

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

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

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

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

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

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

3.  Так как , то .

Задача 20

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

a)  ;

b)  .

Определить является ли язык бесконечным.

Решение для пункта а

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

2.  Найдём множество существенных нетерминальных знаков.

A.  Найдём множество достижимых знаков. Так как в первой продукции множества содержатся все нетерминальные знаки множества , то есть множество достижимых знаков.

B.  Найдём множество производящих знаков .

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

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

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

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

C.  Таким образом, получили, что все нетерминальные знаки грамматики существенны.

3.  Строим такой вывод в грамматике из существенного нетерминального знака , что и , где и состоят из существенных и терминальных знаков: .

4.  Так как и существенные знаки, то фрагмент может породить счётное множество строк, т. е. язык бесконечен.