Условие:
Построить Машину Тьюринга, которая применима только к словам вида 11…1 (3n единиц) n>=1. Внешний алфавит машины (а0,1) q1- начальное состояние, q0- конечное.
Решение:
Ниже приведём подробное рассуждение и конструирование машины Тьюринга, которая работает только на строках, состоящих из 3n единиц (n ≥ 1). Внешний алфавит – {0, 1} (но так как вход содержит только единицы, 0 не встречается во входном слове). Начальное состояние обозначим q1, а конечное – q0. При этом для внутренней работы разрешается использовать дополнительные символы (например, специальную метку X, чтобы отметить, что 1 уже обработана).
Общая идея алгоритма следующая:
- Из начального состояния q1 машина ищет первую неопробованную 1, изменяет её на X (заметка) и переход...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Что нужно знать по теме:
Что нужно знать по теме
Алгоритм решения
Топ 3 ошибок
Что спросит препод
Похожие задачи