Написать программу, эмулирующую машину Тьюринга. Программа читает со стандартного ввода программу для машины Тьюринга в табличном виде (синтаксис описан тут, с упрощением: полностью «пустых» правил, как в третьем примере, быть не должно), если в очередной строке не содержится пробелов — она последняя, и содержит входное слово. Выводится результат работы МТ (предполагается, что программа применима к этому слову). Если программа не заканчивается после 100000 шагов, эмулятор останавливается без какой-либо диагностики. Пояснение к синтаксису см. в подсказках:
Более конкретно про синтаксис программы в табличном виде:
- Первая строка — алфавит MT (пробельные символы не учитываются)
Пустой символ (которым заполнена вся лента) обозначается подчёркиванием ("_")
- Вторая и последующая строки:
- Номер состояния (стартовое состояние всегда 0)
- Тройка, соответствующая поведению MT, когда в текущем состоянии обозревает начальный символ алфавита
- Тройка, соответствующая поведению MT, когда в текущем состоянии обозревает следующий символ алфавита
- … таких троек столько же, сколько символов в алфавите
Тройка имеет вид C,M,S, где:
C — символ алфавита, который надо записать в ячейку
- если он пуст, записывается обозреваемый символ, или, что то же самое, ничего не записывается
M — команда перемещения головки (L — left, N — none, R — right)
если оно пусто, по умолчанию N, т. е .перемещения не происходит
S — номер состояния, в которое надо перейти после перемещения головки
- если он пуст, состояние не меняется
! — переход в финальное состояние, коорое не имеет номера и в таблице не отражается (по сути — останов MT)
В отличие от примера по ссылке, полностью пустые тройки не допускаются, вместо них в тексте программы будет правило ",," («ничего не делать»)
- Разумеется, количество пробелов более одного не имеет значения!
a b c _ # 0 ,R, ,R, ,R, #,L,1 ,N, 1 ,L, ,L, ,L, ,R,2 ,L, 2 _,R, _,R,3 _,R,4 ,R,! _,R,! 3 ,R, ,R, ,R, b,L,1 ,R, 4 ,R, ,R, ,R, c,L,1 ,R, bacab
bcb