Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
Постройте машину Тьюринга, на ленте которой в начале работы находится набор из нулей и единиц. После окончания работы на ленте должна быть «1», если число единиц больше числа нулей, «0» — если меньше и «=» в случае равенства. Кроме «0», «1» и «=»
можно использовать вспомогательные символы «a» и «b».
В качестве начального решения приведена последовательность команд, которая 1) удаляет текущий символ, 2) все символы, находящиеся правее него, сдвигает на одну позицию влево, 3) возвращает считывающую головку в начальную позицию. Последовательность запускается переходом в состояние t1. В ней использованы состояния q0, q1, qa, qb, q=, q3, q4, q5. Последовательность команд заканчивает работу в состоянии t2.
При добавлении новых команд не забывайте, что для машины Тьюринга их порядок не существенен.
Начальное состояние s, конечное f.
Алгоритм работы машины: При нахождении 0 меняем его на а и двигаемся по ленте вправо. Если дошли до * (конец ленты) -- то переходим в qa(состояние для стирания ленты и вывод 0) (нулей больше) Иначе при нахождении 1 меняем ее на b и двигаемся по ленте влево до начала(q3), затем просматриваем последовательно все ячейки ленты с начала. При нахождении 1 меняем ее на а и двигаемся по ленте вправо. Если дошли до * (конец ленты) -- то переходим в qb(состояние для стирания ленты и вывод 1) (единиц больше) Иначе при нахождении 0 меняем его на a и двигаемся по ленте влево до начала(q3), затем просматриваем последовательно все ячейки ленты с начала. Если просмотрены все ячейки ленты (дошли до *), то двигаемся влево (q4). При нахождении непарного числа меняем состояние на qa или qb(стирание ленты и вывод 0 или стирание ленты и вывод 1). При проходе ленты до конца меняем состояние на (стирание ленты и вывод =).