Рубрики

ВОРОТА | GATE CS 2013 | Вопрос 17

Какое из следующих утверждений ЛОЖНО?

1. For every non-deterministic Turing machine, 
   there exists an equivalent deterministic Turing machine.
2. Turing recognizable languages are closed under union 
   and complementation.
3. Turing decidable languages are closed under intersection 
   and complementation.
4. Turing recognizable languages are closed under union 
   and intersection. 

(А) 1 и 4 только
(B) 1 и 3 только
(C) 2 только
(D) 3 только

Ответ: (с)
Объяснение: Распознаватель языка — это машина, которая распознает этот язык.
Выбор языка — это машина, которая решает этот язык.

Оба типа машин останавливаются в состоянии «Принять» для строк на языке
Decider также останавливается, если строка не на языке
Recogizer МОЖЕТ или МОЖЕТ НЕ останавливаться на строках, которые не на языке

На всех входах:
Решение должно быть остановлено (в состоянии Принять или Отклонить)
Recogizer МОЖЕТ или МОЖЕТ НЕ останавливаться на некоторых строках (Q: Какие?)

Язык является разрешимым по Тьюрингу (или разрешимым), если какой-либо механизм Тьюринга решит его. Ака рекурсивный язык.

Язык распознается по Тьюрингу, если его распознает какая-то машина Тьюринга. Ака рекурсивно перечислимый язык.

Источник: http://www.radford.edu/~nokie/classes/420/Chap3-Langs.html

Рекурсивные (тьюринговы) языки закрыты под следующими
Звезда Клини, конкатенация, объединение, пересечение, дополнение и разность множеств.

Рекурсивно перечислимый язык замкнут под клиной звездой, конкатенацией, объединением, пересечением. Они НЕ закрыты под дополнением или заданной разницей.
Тест на этот вопрос

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

ВОРОТА | GATE CS 2013 | Вопрос 17

0.00 (0%) 0 votes