Рубрики

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

Здесь w r является обратной строкой w. Какие из этих языков являются детерминированными контекстно-свободными языками?
(A) Ни один из языков
(B) Только L1
(С) только L1 и L2
(D) Все три языка

Ответ: (с)
Пояснение: Для L1 и L2 мы можем спроектировать детерминированные автоматы Push-down, так что оба являются DCFL.

Но для L3 невозможно спроектировать детерминированный PDA, потому что DPDA не может точно определить, где заканчивается «w», и поэтому может начать извлекать символы (для w r ) из стека.

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

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

0.00 (0%) 0 votes