Question

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.

Answer 1

Ответ:

Применима

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

Начальное состояние:             $...00q_1110111...$

1) $q_11\to1Lq_2$ - сдвиг влево:      $...0q_20110111...$

2) $q_20\to0Lq_3$  - сдвиг влево:    $...q_300110111...$

3) $q_30\to0Rq_0$  - сдвиг вправо:  $...0q_00110111...$

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