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

Материал из DISCOPAL
Перейти к: навигация, поиск

Вопрос: 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.

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

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

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