Задачи по теме машина Тьюринга

1) A={a,b,c}. Если слово P имеет чётную длину, то оставить в нём

только левую половину. 2) A={0,1}. Считая непустое слово P записью двоичного числа,

получить это же число, но в четверичной системе. (Замечание: учесть,

что в двоичном числе может быть нечётное количество цифр.). 3) A={(, )}. Определить, сбалансировано ли слово P по круглым

скобкам. Ответ: Д (да) или Н (нет) 4)A={a,b,c}. Оставить в слове P только последний символ (пустое

слово не менять). 5) A={0,1,2}. Считая непустое слово P записью положительного

числа в троичной системе счисления, выполнить действие: разделить это число на 2 (с отбрасыванием остатка). 6) Пусть P имеет вид Q=R, где Q и R – любые слова из символов a и b. Выдать ответ a, если слова Q и R одинаковы, и пустое слово иначе.