Доброго времени суток дорогие формучане, мне очень очень нужна ваша помощь, ниже будут представленны задания с которыми мне никак не справиться, прошу вас о помощи
:
Задание 1. Пусть для слов в алфавите А={a,b,c} заданы следующие подстановки:
а) b->a; г) bc->ca; ж) bc->^; к); bcab->^
б) c->b; д) ca->ab; з) ca->^; л); a->b.
в) ab->bc; е) abc->^; и) abca->a;
Примените каждую из них к предложенному слову максимально возможное число раз.
cbacbacbacba
Задание 2. Машина Тьюринга определяется следующей функциональной схемой:
q1 q2 q3 q4
a0 q4a0П q3a0Л q1a0П q0a0Л
1 q2α q1β q11П q11Л
α q1αЛ q2αП q31Л q4a0П
β q1βЛ q2βП q3a0Л q41П
Для предложенного слова определите, в какое слово оно перерабатывается данной машиной, исходя из начального положения, при котором машина находится в состоянии q1 и обозревается указываемая ячейка:
11a0111a0(обозревается ячейка 2, считая слева)
Задание 3. Составьте композицию машин Тьюринга {Т1 ,Т2 ,Т3 ,Т4 ,Т5}, которая вычисляет предложенную числовую функцию. Для проверки использовать слово х=111111.
y=2(x-1)
Линейный вид
