Контрольная работа №1 по курсу Алгоритмы и алгоритмическая сложность. Вариант №9

Тип работы: Работа Контрольная
Форматы файлов: Microsoft Word
Сдано в учебном заведении: БГУИР (институт информатики и радиоэлектроники)

Описание:
1. Написать правила машины Тьюринга для решения следующей задачи:
На вход поступает последовательность из 0 и 1. Машина должна дописать к ней слева единицу. Пример: 011001 заменяется на 1011001 (слева появилась 1).

Входной алфавит (алфавит ленты) – S={0,1,ε}, где:
0, 1 – символы;
ε – пустой символ;
Алфавит состояний машины – Q={Q0, Q1, Q2}, где:
Q0 – начальное состояние; Q2 – конечное состояние;
Алфавит движения – D={L, R, H}, где:
L – движение влево; R – движение вправо; H – без движения;