сайт учителя информатики

Есть бесконечная горизонтальная лента, разделенная на равные ячейки.

В каждой ячейке находится ровно один символ из алфавита исполнителя.

Исполнитель МТ - читающая и записывающая головка, которая может передвигаться вдоль ленты.

В начальный момент времени головка находится на неизвестном непутевом расстоянии справа от самого первого символа в начальном состоянии q0.

Команда состоит из трех элементов, разделенных запятыми:

1. записываемый в текущую ячейку символ алфавита
2. один из символов L, R, N, S
3. новое состояние головки после выполнения команды

Обозначения:
L - сдвиг влево
R - сдвиг вправо
N - отсутствие сдвига
S - завершение работы
Сдвиг происходит после записи символа в текущую ячейку.
Если пара «символ - состояние» невозможна, то клетка для команды остается пустой.

Например, команда 0, L, q3 - в текущую ячейку записать символ 0, сдвинуть головку в соседнюю слева ячейку и перейти в состояние q3. Чтобы понять работу МТ, решим задачу.

На ленте в соседних ячейках записана последовательность символов:

Сконструировать МТ для превращения этого слова в слово «дар».

Решение:

Эта же программа в табличном виде

Эта же программа в эмуляторе

Результат: