3.Выяснить, применима ли машина Тьюринга к слову S. P = {1: q1'0 > 0Rq1; 2: q1'1 > 1Lq2; 3: q2'0 > 0Lq3; 4: q2'1 > 0Rq1; 5: q3'0 >0Rq0; 6: q3'1 >1Lq3};

S = 110111.

Применима

Пошаговое объяснение:

Начальное состояние:            

1) - сдвиг влево:      

2)  - сдвиг влево:    

3)  - сдвиг вправо:  

Машина Тьюринга пришла в конечное состояние и закончила работу. Значит, она применима к данному слову.