Выяснить применима ли машина Тьюринга заданная программой P к слову S. Бесплатный доступ к контрольной работе

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

Выяснить применима ли машина Тьюринга заданная программой P к слову S .pdf

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

Условие

Выяснить, применима ли машина Тьюринга, заданная программой P к слову S, и если применима, то указать результат применения машины Тьюринга к данному слову. P=q10→1Rq1q11→1Rq2q20→0q3q21→0Rq1q30→1Lq0q31→1Rq2;S=101001

Решение

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

Будем подписывать состояние машины Тьюринга под рассматриваемым символом строки (Λ – пустой символ, R,L – направление движения):
Λ1q101001Λ→Λ10q21001Λ→Λ10q31001Λ→Λ1q011001Λ
Перешли в конечное состояние q0, поэтому машина Тьюринга применима к слову S

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

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

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