2004-gre-cs-practice-book.pdf/Q66

Ссылки сюда (2) →

Вопрос: Q66-4c9f66

Рассмотрим языки L and L1 над алфавитом из символов {a,b}, где

• L1 = {w | w содержит какое-то слово «x» из L}

Что верно?

1. L — регулярный → L1 — регулярный.
2. L — контекстно-свободный → L1 — контекстно-свободный
3. L — рекурсивный → L1 — рекурсивный

Ответы

• Только 1
• Только 3
• 1 и 3
• 2 и 3
• Правильный ответ: 1, 2 и 3

Объяснение

Исходники — вопрос 66 на 43 странице книги «2004-gre-cs-practice-book.pdf»

1. Если L регулярный, то распознается конечным автоматом, и распознавание подстроки можно конечным автоматом сделать — можно сделать КА для L1.
2. Если L - KC, то тоже самое, только автомат с магазином, тоже можно сделать автомат с магазином для L1
3. Если L - рекурсивный (т.е. разрешимый) — то есть разрешающая МТ(L), это еще лучше, чем все автоматы, и еще легче будет сделать разрешающую МТ для L1.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.