Условие:
Написать машину Тьюринга, которая определяет, каких букв во входном слове больше: a (ответ a) или b (ответ b).
Если их поровну — ответ c. Входные слова в алфавите {a, b, c}. Можно расширять используемый алфавит.
Решение:
Ниже приведён один из вариантов описания машины Тьюринга, решающей задачу. Алгоритм основан на поочерёдном «обнулении» по одной букве a и по одной букве b до тех пор, пока не останется неподпаренных букв. Если после такой процедуры остались только неподпаренные a – значит, их было больше, и выводится буква a; если только b – выводится b; если ни одной – выводится c. Машина работает с расширённым алфавитом, например, можно использовать специальные символы X и Y для пометки уже обработанных букв a и b соответственно.
Описание алгоритма пошагово:
- Исходное состояние...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Что нужно знать по теме:
Что нужно знать по теме
Алгоритм решения
Топ 3 ошибок
Что спросит препод
Похожие задачи