Рубрики

ВОРОТА | GATE CS 2008 | Вопрос 9

Какие из следующих разрешимы?

I. Whether the intersection of two regular languages is infinite
II. Whether a given context-free language is regular
III. Whether two push-down automata accept the same language
IV. Whether a given grammar is context-free

(А) I и II
(Б) Я и IV
(С) II и III
(D) II и IV

Ответ: (Б)
Объяснение: (A) Пересечение двух регулярных языков является регулярным, и проверка, является ли регулярный язык бесконечным, разрешима.

(B) Решение регулярности языка без контекста неразрешимо.
Мы проверяем, содержит ли L (CFG) строку длиной от n до 2n − 1, где n — константа леммы накачки. Если это так, L (CFG) бесконечен, в противном случае он конечен.

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

ВОРОТА | GATE CS 2008 | Вопрос 9

0.00 (0%) 0 votes