Рубрики

ВОРОТА | GATE-CS-2014- (Set-2) | Вопрос 65

GATE

Let L1 = {w ∈ {0,1}∗ | w has at least as many occurrences
                                  of (110)’s as (011)’s}. 

Let L2 = { ∈ {0,1}∗ | w has at least as many occurrences
                                 of (000)’s as (111)’s}.

Что из следующего является ИСТИННЫМ?
(A) L1 регулярный, но не L2
(B) L2 регулярный, но не L!
(C) L2 и L1 являются регулярными
(D) Ни L1, ни L2 не являются регулярными

Ответ: (А)
Пояснение: L1 регулярно
давайте рассмотрим строку 011011011011
В этой строке число вхождений 011 равно 4, но когда мы видим здесь, 110 также произошло, а число вхождений 110 равно 3.

Обратите внимание, что если я добавлю 0 в конце строки, мы можем иметь одинаковое количество вхождений 011 и 110, поэтому эта строка будет принята. Мы можем сказать, что если строка заканчивается 011, добавив 0, мы также можем сделать 110.

Теперь string2: 110110110110 в этом числе вхождений 110 равно 4, а 011 равно 3, что уже удовлетворяет условию

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

ВОРОТА | GATE-CS-2014- (Set-2) | Вопрос 65

0.00 (0%) 0 votes