Рубрики

ВОРОТА | GATE-CS-2000 | Вопрос 32

Рассмотрим следующие проблемы решения:

(P1) Does a given finite state machine accept a given string
(P2) Does a given context free grammar generate an infinite 
     number of stings

Какие из следующих утверждений верно?
(A) Оба (P1) и (P2) разрешимы
(B) Ни (P1), ни (P2) не разрешимы

(C) Только (P1) разрешимо
(D) Только (P2) разрешимо

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

  • Конечный автомат всегда останавливается в конечном или не конечном состоянии. Поэтому проблема P1 разрешима.
  • Мы проверяем, генерирует ли контекстно-свободный язык какую-либо строку длины между n и (2n — 1). Если это так, контекстно-свободный язык бесконечен, иначе он конечен. Поэтому проблема P2 разрешима.

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

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

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

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

ВОРОТА | GATE-CS-2000 | Вопрос 32

0.00 (0%) 0 votes