Рубрики

ВОРОТА | GATE-CS-2007 | Вопрос 31

Какой из следующих языков является регулярным?

(А) А
(Б) Б
(С) С
(D) D

Ответ: (с)
Объяснение:
(C) Строки, которые являются частью этого языка, являются 0w0 или 1w1, где w — любая строка в {0, 1} *.
Таким образом, язык, указанный в варианте (C), является регулярным.

Все остальные языки принимают строки, в качестве подстроки которых используется палиндром.

(A) Строки пересекаются с 0 * 110 *.

(B) Строки пересекаются с 0 * 110 * 1.

(D) Строки пересекаются с 10 * 110 *.

В соответствии с леммой прокачки, языки, заданные опциями (A), (B) и (D), являются нерегулярными.

Таким образом, вариант (C) является ответом.

Пожалуйста, прокомментируйте ниже, если вы найдете что-то не так в вышеуказанном посте.

Тест на этот вопрос

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

ВОРОТА | GATE-CS-2007 | Вопрос 31

0.00 (0%) 0 votes