Рубрики

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

Рассмотрим CFG со следующими постановками.

S → AA | В
A → 0A | A0 | 1
B → 0B00 | 1

S — начальный символ, A и B — нетерминалы, а 0 и 1 — терминалы. Язык, генерируемый этой грамматикой
(A) {0 n 10 2n | n ≥ 1}
(B) {0 i 10 j 10 k | i, j, k ≥ 0} ∪ {0 n 10 2n | n ≥ l}
(C) {0 i 10 j | i, j ≥ 0} ∪ {0 n 10 2n | n ≥ l}
(D) Множество всех строк в {0, 1}, содержащих как минимум два 0
(E) Ничего из вышеперечисленного

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

A−> 0A | A0 | 1 Это производственное правило индивидуально создает КЛЛ вида {0 i 10 j | i, j ≥ 0}
B−> 0B00 | 1 Это производственное правило индивидуально создает CFL вида {0 n 10 2n | n ≥ 0}
S−> AA | B Это производственное правило объединяет CFL A с самим собой и объединяет его с CFL B.
Следовательно, CFL, принятый данным CFG, будет {0 n 10 2n | n ≥ 0} ∪ {0 i 10 j 10 k | i, j, k ≥ 0}
Согласно нашему выводу, поскольку ни один из указанных КЛЛ не соответствует нашему производному КЛЛ, правильный вариант

должно быть (E) Ничего из вышеперечисленного.

Это решение предоставлено Винет Пурсвани .
Тест на этот вопрос

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

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

0.00 (0%) 0 votes