РАЗРАБОТКА ПРОГРАММЫ ДЛЯ МАШИНЫ ТЬЮРИНГА

Идея решения

Идея решения заключается в том, чтобы, сместив каретку к крайнему правому символу, сменить его на следующий по порядку, согласно пятеричной системе счисления, если же нам встретиться символ 4, то мы меняем его на 0, смещаемся влево и повторяем операцию, до тех пор, пока не встретим пробел, после смещаемся вправо и заканчиваем программу.

Внешний алфавит машины Тьюринга: A={ ,0,1,2,3,4}

Для определения внутреннего алфавита составим пошаговый алгоритм:

1. Двигаемся вправо до первого пробела.

2. Сдвигаемся влево и меняем число на следующее, повторяем, пока не встретим (,0,1,2 или 3).

3. Сдвигаемся вправо пока не встретим пробел, если уже встретили – заканчиваем работу.

Отсюда можно выделить 4 состояние автомата:

· q1 – двигаемся вправо до пробела;

· q2 – двигаемся влево меняя символы на следующие;

· q3 – двигаемся влево до пробела;

· qZ – выход.

Не нашли, что искали? Воспользуйтесь поиском: