Рубрики

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

Что из следующего неразрешимо?


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

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

  • Во-первых, пустота для CFG; пуста ли CFG или нет, эта проблема разрешима.
  • Во-вторых, все для CFG; будет ли CFG генерировать все возможные строки (полнота CFG), эта проблема неразрешима.
  • В-третьих, регулярность для REC; является ли язык, сгенерированный ТМ, регулярным, неразрешимым.
  • В-четвертых, эквивалентность для регулярного; является ли язык, сгенерированный DFA и NFA, тем же самым, решаемо.

Второе и третье будут неразрешимы. Следовательно, вариант (D) является правильным.
Тест на этот вопрос

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

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

0.00 (0%) 0 votes