2004-gre-cs-practice-book.pdf/Q66
Материал из DISCOPAL
Вопрос: Q66-4c9f66
Рассмотрим языки L and L1 над алфавитом из символов {a,b}, где
- L1 = {w | w содержит какое-то слово «x» из L}
Что верно?
- L — регулярный → L1 — регулярный.
- L — контекстно-свободный → L1 — контекстно-свободный
- L — рекурсивный → L1 — рекурсивный
Ответы
- Только 1
- Только 3
- 1 и 3
- 2 и 3
- Правильный ответ: 1, 2 и 3
Объяснение
Исходники — вопрос 66 на 43 странице книги «2004-gre-cs-practice-book.pdf»
- Если L регулярный, то распознается конечным автоматом, и распознавание подстроки можно конечным автоматом сделать — можно сделать КА для L1.
- Если L - KC, то тоже самое, только автомат с магазином, тоже можно сделать автомат с магазином для L1
- Если L - рекурсивный (т.е. разрешимый) — то есть разрешающая МТ(L), это еще лучше, чем все автоматы, и еще легче будет сделать разрешающую МТ для L1.
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.