Рубрики

ВОРОТА | GATE CS 2010 | Вопрос 40

Рассмотрим языки
L1 = {0 i 1 j | я! = j}
L2 = {0 i 1 j | я = j}
L3 = {0 i 1 j | я = 2j + 1}.
L4 = {0 i 1 j | я! = 2j}.
(A) Только L2 не зависит от контекста
(B) Только L2 и L3 являются контекстно-свободными
(C) Только L1 и L2 являются контекстно-свободными
(D) Все являются контекстно-свободными

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

Все эти языки имеют действительные CFG, которые могут их выводить. Следовательно, все они являются КЛЛ. Наглядно,
(A) и (B) являются хорошо известными КЛЛ, и КФГ для (С) и (D) могут быть сделаны с небольшими изменениями в
CFGs A & B.

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

ВОРОТА | GATE CS 2010 | Вопрос 40

0.00 (0%) 0 votes