Рубрики

ВОРОТА | Gate IT 2008 | Вопрос 33

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

L 1 = {0 m 1 n | 0 ≤ m ≤ n ≤ 10000}
L 2 = {w | w читает одно и то же вперед и назад}
L 3 = {w ∊ {0, 1} * | w содержит четное число 0 и четное число 1}
(A) только L 2 и L 3
(B) только L 1 и L 2
(C) только L 3
(D) L 2 только

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

1. L 1 является обычным языком, так как он может быть получен с помощью тривиального DFA с 10000 состояниями для каждого алфавита в грамматике, чтобы ограничить количество от 0 до 1 100 с.
2. L 2 — это набор всех палиндромных строк, который не является обычным языком, потому что конечный автомат не может вспомнить, какие алфавиты встречались.
3. L 3 является стандартным регулярным языком, так как существует DFA, который может получить этот язык. Вы можете прочитать больше в ссылках об этом.

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

ВОРОТА | Gate IT 2008 | Вопрос 33

0.00 (0%) 0 votes