Рубрики

ВОРОТА | GATE-CS-2006 | Вопрос 85

Для S ∈ (0 + 1) * пусть d (s) обозначает десятичное значение s (например, d (101) = 5). Пусть L = {s ∈ (0 + 1) * d (s) mod5 = 2 и d (s) mod7! = 4}.
Какое из следующих утверждений верно?

(A) L рекурсивно перечислимо, но не рекурсивно
(B) L является рекурсивным, но не контекстно-свободным
(C) L не зависит от контекста, но не является регулярным
(D) L регулярно

Ответ: (D)
Пояснение: это регулярно
L1 = d (s) mod 5 = 2 регулярно с 5 состояниями
L2 = d (s) mod 7 = 4 регулярно с 7 состояниями
поэтому L1 ^ L2 ′ должен быть регулярным
потому что обычная грамматика закрыта под пересечением и комплиментом
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2006 | Вопрос 85

0.00 (0%) 0 votes