Построить машину Тьюринга применимую ко всем словам x1x2…xn в алфавите. Бесплатный доступ к решению задач

Реферат.Справочник
Решенные задачи по высшей математике
Построить машину Тьюринга применимую ко всем словам x1x2…xn в алфавите

Построить машину Тьюринга применимую ко всем словам x1x2…xn в алфавите .pdf

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

Условие

Построить машину Тьюринга, применимую ко всем словам x1x2…xn в алфавите {a,b} и переводящую их в слово α. Задание по вариантам представлено в таблице 7.1. Таблица 7.1 № вар. α 7 baba, если слово начинается на ba, x1x2…xna в других случаях Задание Построить машину Тьюринга, применимую ко всем словам x1x2…xn в алфавите {a,b} и переводящую их в слово baba, если слово начинается на ba, x1x2…xna в других случаях.

Нужно полное решение этой работы?

Решение

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

Машина начинает работу из стандартного состояния, т. е. обозревает ячейку с буквой xn. q1 – начальное состояние, q0 – заключительное состояние, a0 – пустой символ.
Сначала машина должна пройти все слово влево и проверить, начинается ли слово на ba. Если первая буква a, или вторая буква b или пустой символ (слово не начинается на ba), то машина должна пройти все слово вправо, вместо первого пустого символа записать букву a и закончить работу . Если первая буква b, то проверяется вторая буква. Если вторая буква a (слово начинается на ba), то в следующие две ячейки записывается ba, затем машина должна пройти все слово вправо, стирая все оставшиеся буквы, после этого вернуться к последнему символу полученного слова и закончить работу.
q1a→q1aЛ, q1b→q1bЛ, (проход слова влево в начальном состоянии q1)
q1a0→q2a0П, (переход в состояние q2 при достижении пустого символа и сдвиг вправо к первой букве слова)
q2a→q8aП, (переход в состояние q8 означает, что слово не начинается на ba)
q2b→q3bП, (переход в состояние q3 для проверки второй буквы)
q3b→q8bП, q3a0→q8a0, (слово не начинается на ba)
q3a→q4aП, (переход в состояние q4 означает, что слово начинается на ba)
q4a→q5bП, q4b→q5bП, q4a0→q5bП, (замена 3-го символа на b)
q5a→q6aП, q5b→q6aП, q5a0→q6aП, (замена 4-го символа на a)
q6a→q6a0П, q6b→q6a0П, q6a0→q7a0Л, (стирание всех оставшихся букв)
q7a0→q7a0Л, q7a→q0a

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

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

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