Решите с кругом эйлера ​">

1. На ленте машины Тьюринга содержится последовательностью символов “+”. Напишите программу для машины Тьюринга, которая каждый второй символ “+” заменит на “–”. Замена начинается с правого конца последовательности. Автомат в состоянии q1 обозревает один из символов указанной последовательности. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

2. Дано число n в восьмеричной системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное число n на 1. Автомат в состоянии q1 обозревает некую цифру входного слова. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

3. Дана десятичная запись натурального числа n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1. Автомат в состоянии q1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

4. Дано натуральное число n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1, при этом в выходном слове старшая цифра не должна быть 0. Например, если входным словом было “100”, то выходным словом должно быть “99”, а не “099”. Автомат в состоянии q1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

5. Дан массив из открывающих и закрывающих скобок. Построить машину Тьюринга, которая удаляла бы пары взаимных скобок, т.е. расположенных подряд “( )”.

Например, дано “) ( ( ) ( ( )”, надо получить “) . . . ( ( ”.

Автомат в состоянии q1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

6. Дана строка из букв “a” и “b”. Разработать машину Тьюринга, которая переместит все буквы “a” в левую, а буквы “b” — в правую части строки. Автомат в состоянии q1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Var used: Set of Char;
    s1, s2: string;
    i: integer;
    done: boolean;
    c: char;

function IsLetter(c: char): boolean;
begin
  IsLetter := ((c >= 'a') and (c <= 'z')) or ((c >= 'A') and (c <= 'Z'));
end;

function UpperCase(c: char): char;
begin
  if (c >= 'a') and (c <= 'z') then
    UpperCase := Chr(Ord(c) - Ord('a') + Ord('A'))
  else
    UpperCase := c;
end;

begin
used := [];

readln(s1);
readln(s2);

for i := 1 to length(s1) do
  if (IsLetter(s1[i])) then
    include(used, UpperCase(s1[i]));

for i := 1 to length(s2) do
  if (IsLetter(s2[i])) then
    include(used, UpperCase(s2[i]));

done := False;
for c := 'A' to 'Z' do
  if not (c in used) then
  begin
    done := True;
    write(c);
  end;

if not done then
  write(0);

writeln;
end.