Рубрики

ВОРОТА | GATE-CS-2014- (Set-1) | Вопрос 45

Пусть L — язык, а L — его дополнение. Что из перечисленного НЕ является жизнеспособной возможностью?

(A) Ни L, ни L 'не являются рекурсивно перечислимыми (re).
(B) Один из L и L 'является ре, но не рекурсивным; другой не ре

(C) L и L 'являются ре, но не рекурсивными.
(D) L и L 'являются рекурсивными

Ответ: (с)
Пояснение: A) Это возможно, если само L НЕ является RE. Тогда L 'также не будет RE.
Б) Предположим, что существует такой язык, что машина Тьюринга останавливается на входе. Данный язык является RE, но не рекурсивным, и его дополнение НЕ RE.
C) Это невозможно, потому что если мы можем написать процедуру перечисления для обоих языков и ее дополнения, то язык становится рекурсивным.
D) Это возможно, потому что L замкнуто относительно дополнения, если оно рекурсивно.

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

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

ВОРОТА | GATE-CS-2014- (Set-1) | Вопрос 45

0.00 (0%) 0 votes