Логотип Автор24реферат
Задать вопрос
%
уникальность
не проверялась
Решение задач на тему:

Постройте машину Тьюринга перерабатывающую слово 01x (в слове x единиц) в это же слово 01x0 из стандартного начального положения

уникальность
не проверялась
Аа
730 символов
Категория
Другое
Решение задач
Постройте машину Тьюринга перерабатывающую слово 01x (в слове x единиц) в это же слово 01x0 из стандартного начального положения .pdf

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

Постройте машину Тьюринга, перерабатывающую слово 01x (в слове x единиц) в это же слово 01x0 из стандартного начального положения, причем в момент остановки должна обозревается крайняя левая ячейка. (Эта машина называется «левый сдвиг» и обозначается Б-).

Решение

Потяни, чтобы посмотреть
Пусть внешний алфавит машины Тьюринга A={a0, 0,1}.
Состояний у машины будет три: q0 – остановка, q1, q2 – рабочие состояния, т.е . Q = {q0, q1, q2}.
Функциональная схема (программа) машины:
q11 → q11П,
q1 a0 → q2 0Л,
q2 1 → q2 1Л,
q2 0 → q0 0.
Начальное положение машины стандартное.
Приведем последовательность конфигураций, получаемых при переработке этой машиной слова 01111 (014):
0111q11 → 01111q1a0 → 0111 q210 → 011 q2110 → 01 q21110
→ 0 q211110 → q2 011110 → q0 011110
50% задачи недоступно для прочтения
Переходи в Кампус, регистрируйся и получай полное решение
Получить задачу
Больше решений задач по другому:
Все Решенные задачи по другому
Закажи решение задач
Оставляя свои контактные данные и нажимая «Найти работу», я соглашаюсь пройти процедуру регистрации на Платформе, принимаю условия Пользовательского соглашения и Политики конфиденциальности в целях заключения соглашения.

Наш проект является банком работ по всем школьным и студенческим предметам. Если вы не хотите тратить время на написание работ по ненужным предметам или ищете шаблон для своей работы — он есть у нас.