Рубрики

ВОРОТА | GATE-CS-2007 | Вопрос 78

GATE

Рассмотрим CFG с {S, A, B) в качестве нетерминального алфавита, {a, b) в качестве конечного алфавита, S в качестве начального символа и следующего набора производственных правил

S --> aB        S --> bA
B --> b         A --> a
B --> bS        A --> aS
B --> aBB       A --> bAA

Какая из следующих строк генерируется грамматикой?
(A) aaaabb
(Б) аабббб
(C) Aabbab
(D) abbbba

Ответ: (с)
Пояснение: Приведенные ниже правила производства.

S --> aB        S --> bA
B --> b         A --> a
B --> bS        A --> aS
B --> aBB       A --> bAA

Мы можем получить aabbab используя следующую последовательность

S  -> aB      [Using S --> aB] 
   -> aaBB    [Using B --> aBB]
   -> aabB    [Using B --> b]
   -> aabbS   [Using B --> bS]
   -> aabbaB  [Using S --> aB]
   -> aabbab  [Using B --> b]

Тест на этот вопрос

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

ВОРОТА | GATE-CS-2007 | Вопрос 78

0.00 (0%) 0 votes