1. solvetop.com
  2. Информатика
  3. Напишите программу для машины...

Напишите программу для машины Тьюринга, которая перемещает последний символ в начало строки. Каретка находится

  • 58
Напишите программу для машины Тьюринга, которая перемещает последний символ в начало строки. Каретка находится над первым символом строки.

Рекомендуется сохранять верные ответы и всегда делиться с друзьями, ведь они могут тебе ещё пригодиться!

Telegram Whatsapp ВКонтакте
Вечный_Странник_5291
35
Хорошо! Чтобы написать программу для машины Тьюринга, которая перемещает последний символ в начало строки, будем использовать следующий алгоритм:

1. Поставим машину Тьюринга над первым символом строки.

2. Сначала проверим, является ли текущая ячейка последней в строке. Для этого будем смещаться вправо, пока не достигнем конца строки.

3. Если мы достигли конца строки, запомним текущий символ.

4. Теперь сдвинемся в самое начало строки.

5. Копируем каждый символ вправо до тех пор, пока не достигнем предпоследнего символа. Это можно сделать, перемещаясь вправо, копируя символ из текущей ячейки и затем смещаясь вправо.

6. Когда мы достигнем предпоследнего символа, скопируем сохраненный символ (последний символ строки) в текущую ячейку.

7. Программа завершена.

Опишем этот алгоритм на языке Тьюринга:

Состояния:
- A: начальное состояние
- B: смещение вправо для поиска последнего символа
- C: смещение влево после нахождения последнего символа
- D: копирование символа вправо
- E: закончить программу

Символы:
- X: текущий символ
- _: пустая ячейка

Таблица переходов:


      | A             | B             | C             | D             |

------------------------------------------------------------------------

  X   | (B, X, R)     | (C, _, L)     | (E, _, L)     | (D, X, R)     |

  _   | (E, _, L)     | (E, _, L)     | (E, _, L)     | (E, _, L)     |

------------------------------------------------------------------------


Шаги решения по Тьюрингу:
```
1: A X _ _ _ _ _ 12: D X X X X _ _ 23: D X X X X X X 34: B X X X X X X 42: C X _ X X X X X
2: B X _ _ _ _ _ 13: B X X X X _ _ 24: B X X X X X X 35: C X _ X X X X X 43: D X X _ X X X
3: B X X _ _ _ _ 14: B X X X X X _ 25: D X X X X X X 36: D X X _ X X X 44: D X X X _ X X
4: B X X X _ _ _ 15: B X X X X X X 26: D X X X X X X 37: D X X X _ X X 45: C X X X _ X X
5: B X X X X _ _ 16: C X X _ X X X 27: C X X _ X X X 38: C X X X X _ X 46: D X X X X _ X
6: B X X X