ВОРОТА | 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 ′ должен быть регулярным
потому что обычная грамматика закрыта под пересечением и комплиментом
Тест на этот вопрос

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

• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 52
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 65
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 64
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 53
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 54
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 55
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 56
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 57
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 58
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 59
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 60
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 61
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 62
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 63
• ВОРОТА | Sudo GATE 2020 Mock II (10 января 2019 года) | Вопрос 65