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

a)  Вычислим вектора смены маркировок , , где - это вектора срабатывания переходов, а - это вектора возбуждения переходов. Заметим, что в таблице инцидентности находятся числа /, . Тогда получим:

,

,

,

,

,

.

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

c)  Выбираем переход, который сработает на этом шаге. Пусть сработал переход , тогда .

d)  Повторяем шаги b и c до тех пор, пока не получим тупиковую маркировку, либо пока маркировка на текущем шаге не будет равна одной из маркировок на предыдущих шагах:

-  ;

-  пусть сработал переход , тогда ;

-  ;

-  пусть сработал переход , тогда ;

-  ;

-  сработал переход , тогда ;

-  ;

-  пусть сработал переход , тогда ;

-  ;

-  пусть сработал переход , тогда .

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

Задача 32

Сеть Петри задана двудольным графом. Получить её формальное описание.

Занятие 2.3. Магазинный автомат (МА)

Задача 33

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

Синтезировать МА принимающий язык .

Решение

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

2.  Построим МА в соответствии с теоремой о КС-грамматике и МА.

a)  .

b)  Алфавит входных знаков .

c)  Множество состояний .

d)  Стековый алфавит .

e)  Начальная конфигурация .

f)  Магазинное отображение строим следующим образом:

3.  Проверка.

A.  Получим строку, принадлежащую языку :

.

B.  Определим строку, не принадлежащую языку следующим образом:

a)  Вычислим множество строк языка с длиной не более 3:

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

- ;

- ;

- ;

- ;

- ;

- ;

- ;

- ;

b)  Так как , то есть множество строк языка с длиной не более 3.

c)  Пусть строка, не принадлежащая языку , есть .

C.  Проверим, распознаёт ли МА строку .

	Конфигурация
		*

D.  Проверим, не распознаёт ли МА строку .