Лаба №3. Машины Тьюринга

Решение
Файл с решением: 
Задание

Целью данного занятия является закрепление знаний по теории распознавания языков. Требуется подробно ознакомиться с языком ВЫПОЛНИМОСТЬ, играющим ключевую роль в теории сложности алгоритмов.

Задание 1. Построить распознающую машину Тьюринга, распознающую слова, начинающиеся с двух и долее подряд идущих единиц.

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

Задание 3. Построить распознающую машину Тьюринга, распознающую слова, заканчивающиеся тремя подряд идущими единицами.

Задание 4. Какие еще виды слов распознает приведенная в таблице машина ?

Задание 5 (разобрать со студентами у доски)). Исследовать на эффективность процедуру проверки выполнимости системы дизъюнктов для заданной интерпретации.

....
[остальное в файле ниже]

Файл с заданием: