Рубрики

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 53

Рассмотрим следующие языки:
L1 = {a n b m c n : m, n> = 1}
L2 = {a n b n c 2n : n> = 1}
Что из следующего является ИСТИННЫМ?
(A) L1 и L2 не зависят от контекста.
(B) L1 не зависит от контекста, в то время как L2 не зависит от контекста.
(C) L2 не зависит от контекста, в то время как L1 не зависит от контекста.
(D) Ни L1, ни L2 не являются контекстно-свободными.

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

L1 = {a n b m c n | m, n ≥ 1} является контекстно-свободным языком, потому что он получен с помощью следующего CFG:
S−> aSc | aBc;
B−> bB | b

L2 = {a n b n c 2n | n ≥ 1} не является контекстно-свободным языком, это можно доказать с помощью леммы прокачки. Интуитивно понятно, что прижимной автомат не может запомнить количество символов для третьего набора символов, т. Е. Этот язык очень похож на {a n b n c n | n ≥ 1}, который, как известно, не является CFL.

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

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 53

0.00 (0%) 0 votes