Занятие 2.1. Машина Тьюринга (МТ)
Задача 23
МТ задана таблицей. 
Найти её заключительную конфигурацию.
Решение
Применяем к начальной конфигурации команды МТ до тех пор, пока МТ не перейдёт в заключительное состояние:
Задача 24
Построить МТ в алфавите переводящую конфигурацию в конфигурацию (которая умножает число представленное в унитарном коде на 2).
Решение
1. Приводим примеры работы МТ:
— при ;
— при .
2. Даём словесное описание алгоритма.
Проверяем, является ли текущим знаком знак . Если нет, то останавливаемся, иначе заменяем текущий знак на маркер , перемещаемся влево до первого знака и заменяем его на знак , перемещаемся вправо до маркера и заменяем его на знак , смещаемся вправо и повторяем сначала.
3. Задаём МТ реализующую действия из пункта 2 в виде таблицы.

4. Проверка:
Задача 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
Задано формальное описание сети Петри:
a) Сеть Петри есть ;
b) Множество позиций ;
c) Множество переходов ;
d) Начальная маркировка .
e) Отношение инцидентности задано в виде таблицы.

Получить двудольный граф изображающий сеть Петри .
Решение

Задача 31
Сеть Петри задана двудольным графом. Вычислить последовательность смены её маркировок.
Решение
1. Зададим формальное описание сети Петри.
a) Сеть Петри есть .
b) Множество позиций .
c) Множество переходов .
d) Начальная маркировка .
e) Отношение инцидентности зададим в виде таблицы.

2. Вычислим последовательность смены маркировок.
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. Проверим, не распознаёт ли МА строку .
Конфигурация
Очевидно, для того чтобы эта строка была распознана, нам необходимо на вершине стека получить знак , что невозможно ипользуя команды МА .
Задача 34
Задан МА :
a) алфавит входных знаков ;
b) множество состояний ;
c) стековый алфавит ;
d) начальная конфигурация ;
e) магазинное отображение
.
Построить грамматику, порождающую язык, принимаемый автоматом .
Решение
1. Для решения этой задачи воспользуемся теоремой о МА и КС-языке.
a) Грамматика .
b) Алфавит терминальных знаков .
c) Обозначим заключительное состояние как .
d) Аксиома , где .
e) Алфавит нетерминальных знаков , тогда .
f) Если в имеется команда , где , , , то в добавляем всевозможные продукции вида , где . Для команд вида в добавляем продукцию . Аксиому строим таким образом, что при извлечении из стека любого префикса начальной конфигурации автомат переходит из начального в заключительное состояние, что эквивалентно принятию такого множества строк, которые будут соответствовать построенной аксиоме. Тогда получим
2. Приведём полученную грамматику.
a) Удаляем из множества продукций грамматики все продукции, содержащие заключительное состояние не в конце строки в левой части. Получаем
b) Строим множество достижимых знаков .
c) Строим множество производящих знаков .
d) В итоге получаем:

Занятие 2.4. Конечный автомат (КА)
Задача 35
Пусть язык содержит строки в алфавите такие, что справа от знака всегда находится знак . Синтезировать КА, распознающий строки языка .
Решение
1. Построим регулярную грамматику
a) Множество продукций .
b) Алфавит терминальных знаков .
c) Алфавит нетерминальных знаков .
2. В соответствии с теоремой о представимости регулярных языков конечными автоматами строим КА , распознающий строки языка .
a) Входной алфавит .
b) Выходной алфавит .
c) Множество состояний , где — заключительное состояние.
d) Начальное состояние .
e) Систему команд строим следующим образом: для каждой продукции , где , в добавляем команду , а для каждой команды в добавляем команду . Тогда получим .
Задача 36
КА задан в виде графа.

Получить формальную грамматику для языка порождаемого этим КА и для языка распознаваемого этим КА.
Решение
1. Строим грамматику для языка, распознаваемого этим КА.
a) Алфавит терминальных знаков .
b) Алфавит нетерминальных знаков .
c) Аксиома .
d) Множество продукций строим следующим образом: в добавляем продукцию и для каждой команды , где , , в добавляем продукцию . Тогда получим .
2. Строим грамматику для языка, порождаемого этим КА.
e) Алфавит терминальных знаков .
f) Алфавит нетерминальных знаков .
g) Аксиома .
h) Множество продукций строим следующим образом: в добавляем продукцию и для каждой команды , где , , в добавляем продукцию . Тогда получим .
Задача 37
Построить КА, вычисляющий для пары строк над алфавитом их двоичную сумму. Входные данные начинаются с битов с наименьшим весом.
Задача 38
Построить КА, осуществляющий сложение двоичных чисел в дополнительном коде (см. задачу 36).
Замечание