Рубрики

ВОРОТА | GATE-CS-2006 | Вопрос 32

Рассмотрим следующие утверждения о контекстно-свободной грамматике

G = {S → SS, S → ab, S → ba, S → Ε}
I. G is ambiguous
II. G produces all strings with equal number of a’s and b’s
III. G can be accepted by a deterministic PDA.

Какая комбинация ниже выражает все истинные утверждения о G?
(А) Я только
(B) только I и III
(C) только II и III
(D) I, II и III

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

Утверждение I: G неоднозначно, потому что, как показано на рисунке ниже, может быть два дерева решений для строки S = ababab [TRUE]

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

ВОРОТА | GATE-CS-2006 | Вопрос 32

0.00 (0%) 0 votes