Рубрики

ВОРОТА | GATE-CS-2003 | Вопрос 53

Одиночная ленточная машина Тьюринга M имеет два состояния q0 и q1, из которых q0 является начальным состоянием. Алфавит ленты M равен {0, 1, B}, а его входной алфавит — {0, 1}. Символ B — это пустой символ, используемый для обозначения конца входной строки. Функция перехода M описана в следующей таблице

 0 1 B
 q0 q1, 1, R q1, 1, R Halt
 q1 q1, 1, R q0, 1, L q0, B, L

Таблица интерпретируется как показано ниже.
Запись (q1, 1, R) в строке q0 и столбце 1 означает, что если M находится в состоянии q0 и читает 1 в текущем квадрате ленты, то он записывает 1 в тот же квадрат ленты, перемещает головку ленты на одну позицию в право и переходы в состояние q1.

Какое из следующих утверждений верно для M?
(A) M не останавливается ни на одной строке в (0 + 1) +
(B) M не останавливается ни на одной строке в (00 + 1) *
(C) M останавливается на всей строке, заканчивающейся на 0
(D) M останавливается на всей строке, заканчивающейся на 1

Ответ: (А)
Объяснение:
Всякий раз, когда B задается как вход, машина Тьюринга останавливается. Это подразумевает, что эпсилон принимается только тогда, когда в качестве входа используется B.

В положительном закрытии эпсилон отсутствует. Таким образом, машина Тьюринга никогда не останавливается в случае (0 + 1) + .

Таким образом, вариант (А) является правильным.

Пожалуйста, прокомментируйте ниже, если вы найдете что-то не так в вышеуказанном посте.

Рекомендуемые посты:

ВОРОТА | GATE-CS-2003 | Вопрос 53

0.00 (0%) 0 votes