Рубрики

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

Рассмотрим следующие языки.

L 1 = {a i b j c k | i = j, k ≥ 1}

L 1 = {a i b j | j = 2i, i ≥ 0}

Какие из следующих утверждений верно?
(A) L 1 не является КЛЛ, но L 2 является
(B) L 1 ∩ L 2 = ∅ и L 1 нерегулярно
(C) L 1 ∪ L 2 не является КЛЛ, но L 2 является
(D) Существует PDA с 4 состояниями, который принимает L 1 , но нет DPDA, который принимает L 2

Ответ: (Б)
Пояснение: A: оба L 1 и L 2 являются CFL

B: L 1 ∩ L 2 = ∅ верно

L 1 не является регулярным => верно

=> B верно

С: L 1 , L 2 , ∪ не КЛЛ гайка L 2 КЛЛ замкнут относительно Союза

=> Ложь

D: L 1 и L 2 приняты DPDA
Тест на этот вопрос

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

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

0.00 (0%) 0 votes