Рубрики

ВОРОТА | GATE-CS-2007 | Вопрос 6

Какая из следующих проблем неразрешима? [2007]

(A) Проблема членства для CFG
(B) Проблема неоднозначности для CFG.
(C) Проблема конечности для FSA.
(D) Проблема эквивалентности для FSA.

Ответ: (Б)
Объяснение:

Множество закрыто под операцией, значит, когда мы оперируем элементом этого множества с этим оператором, мы получаем элемент из этого множества.

Здесь CFG генерирует CFL, и набор всех CFL является набором. Но двусмысленность не является операцией, и, следовательно, мы никогда не можем сказать, что CFG закрыт при такой операции.

Только проблема неоднозначности для CFG неразрешима.

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

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

Тест на этот вопрос

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

ВОРОТА | GATE-CS-2007 | Вопрос 6

0.00 (0%) 0 votes