ВОРОТА | ВОРОТА КС 2021 | Набор 2 | Вопрос 51

Опубликовано: 7 Октября, 2022

Для строки w мы определяем w R как обратную строку w. Например, если w = 01101, то w R = 10110.

Какой из следующих языков является/являются контекстно-свободными?
(A) {wxw R x R ∣ w,x∈{0,1}*}
(B) {ww R xx R ∣ w,x∈{0,1}*}
(С) {wxw R ∣ w,x∈{0,1}*}
(D) {wxx R w R ∣ w,x∈{0,1}*}

Ответ: (Б) (В) (Г)
Объяснение: Вариант A: L={wxw^R x^R | ш, х € {0,1}*}
Это не CFL, так как если мы нажимаем «w», а затем «x», то мы не можем сопоставить w ^ R с «w», так как вершина стека содержит x.

Вариант Б: L={ww^R xx^R | ш, х € {0,1}*}
Это КФЛ. Мы недетерминировано угадываем середину строки. Итак, мы нажимаем «w», затем сопоставляем с w^R и снова нажимаем x и сопоставляем с x^R

Вариант C: L={wxx^R w^R | ш, х € {0,1}*}
Это тоже КФЛ. Мы недетерминировано угадываем середину строки. Итак, мы нажимаем «w», затем нажимаем x, затем сопоставляем с x^R и снова сопоставляем с w^R

Вариант D: L={wxw^R | ш, х € {0,1}*}
Это обычный язык (отсюда CFL). В этом языке каждая строка начинается и заканчивается одним и тем же символом (поскольку x может расширяться).
Викторина этого вопроса

РЕКОМЕНДУЕМЫЕ СТАТЬИ