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

Задача 25

МТ задана таблицей.

\

Получить эквивалентную ей грамматику , реализующую тоже преобразование строк, что и заданная МТ.

Решение

1.  .

2.  . Пусть , тогда .

3.  Множество продукций строим следующим образом:

a)  Для всех команд вида в добавляем продукцию .

b)  Для всех команд вида в добавляем продукцию .

c)  Для всех команд вида в добавляем продукцию .

d)  В добавляем продукцию вида , порождающую исходные данные МТ.

Тогда получаем:

Задача 26

МТ задана таблицей.

\

По МТ записать аналитическое выражение для функции, которую она вычисляет (используется унитарное кодирование чисел на ленте). Определить область определения и область значения этой функции.

Решение

1.  На примере различных чисел записанных ленту получаем результаты вычислений МТ:

-  ;

-  .

2.  Запишем аналитическое выражение для функции, которую вычисляет МТ : .

3.  Область определения: .

4.  Область значения: .

Задача 27

МТ задана таблицей.

\

Найти её заключительную конфигурацию для следующих начальных конфигураций:

a)  ;

b)  .

Задача 28

Построить МТ в алфавите переводящую конфигурацию в конфигурацию (которая выполняет копирование числа представленное в унитарном коде).

Занятие 2.2. Сети Петри

Задача 29

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

Решение

1.  Сеть Петри есть.

2.  Множество позиций .

3.  Множество переходов .

4.  Начальная маркировка .

5.  Отношение инцидентности зададим в виде таблицы.

\
	/	/	/	/
	/	/	/	/
	/	/	/	/
	/	/	/	/

Задача 30

Задано формальное описание сети Петри: