ВОРОТА | GATE-CS-2009 | Вопрос 60

Пусть L = L1∩L2, где L1 и L2 — языки, как определено ниже:

L1 = { | m, n >= 0 }
L2 = { | i, j, k >= 0 }

Тогда L
(А) не рекурсивный
(B) Обычный
(C) Контекстно-свободный, но не регулярный
(D) Рекурсивно перечислимый, но не контекстно-свободный.

Ответ: (с)
Объяснение: Язык L1 принимает строки {c, abc, abcab, aabbcab, aabbcaabb,…} и L2 принимает строки {a, b, c, ab, abc, aabc, aabbc,…}. Пересечение этих двух языков который является контекстно-свободным, но не регулярным.
Тест на этот вопрос

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

• ВОРОТА | 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