Машина Тьюринга определяется следующей функциональной схемой. Бесплатный доступ к решению задач

Реферат.Справочник
Решенные задачи по другому
Машина Тьюринга определяется следующей функциональной схемой

Машина Тьюринга определяется следующей функциональной схемой .pdf

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

Условие

Машина Тьюринга определяется следующей функциональной схемой: Для следующих слов определите, в какое слово перерабатывается каждое из них данной машиной, исходя из начального положения, при котором машина находится состоянии q1 и обозревается указываемая ячейка: 111111 (обозревается ячейка 2)

Решение

Потяни, чтобы посмотреть

Запишем последовательность конфигураций:
1 q1 11111 → 1 q2 α1111→ 1 α q2 1111→ 1 α q1 β111 → 1 q1 α β111
→ q1 1αβ111→ q2 ααβ111→ α q2 αβ111→ α α q2 β111→ α α β q2 111
→ α α β q1 β11→ α α q1β β11→ α q1α β β11→ q1α α β β11→ q1 a0α α β β11
→ a0 q4 α α β β11→ a0 a0 q4α β β11→ a0 a0 a0 q4 β β11→ a0 a0 a0 1 q4 β11
→ a0 a0 a0 11 q411→ a0 a0 a0 1 q11 11→ a0 a0 a0 1 q2α 11→ a0 a0 a0 1 α q211
→ a0 a0 a0 1 α q1β1→ a0 a0 a0 1 q1α β1→ a0 a0 a0 q11 α β1→ a0 a0 a0 q2α α β1
→ a0 a0 a0 α q2α β1→ a0 a0 a0 α α q2 β1→ a0 a0 a0 α α β q21
→ a0 a0 a0 α α β q1β → a0 a0 a0 α α q1β β → a0 a0 a0 α q1 α β β
→ a0 a0 a0 q1α α β β → a0 a0 q1a0 α α β β → a0 a0 a0 q4α α β β
→ a0 a0 a0 a0 q4α β β → a0 a0 a0 a0 a0 q4β β → a0 a0 a0 a0 a0 1 q4β
→ a0 a0 a0 a0 a0 1 1 q4 a0→ a0 a0 a0 a0 a0 1 q01 a0

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу