Рубрики

ВОРОТА | GATE-CS-2000 | Вопрос 5

Пусть L обозначает язык, порожденный грамматикой S -> 0S0 / 00. Какие из следующих утверждений верно?
(А) L = 0+
(B) L регулярно, но не 0+
(C) L не зависит от контекста, но не является регулярным
(D) L не является контекстно-свободным

Ответ: (Б)
Объяснение: Опция A : L не равно 0+ , потому что 0+ будет содержать любую произвольную строку над алфавитом 0 с любым номером 0 (кроме пустой строки), например: {0, 00, 000,00000}, но L будет только иметь строки как {00, 0000, 000000,…}, т.е. только четные нули (исключая пустую строку}).

Вариант D : L является контекстно-свободным языком , потому что грамматика G, которая генерирует язык L, является контекстно-свободной грамматикой. Грамматика G является CFG, если все ее произведения имеют форму A-> α, где A — один нетерминал, а α принадлежит (V∪ T) *, то есть α может быть цепочкой терминалов и / или Non. -terminals. (V представляет собой нетерминал и T представляет собой терминал)

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

ВОРОТА | GATE-CS-2000 | Вопрос 5

0.00 (0%) 0 votes