2004-gre-cs-practice-book.pdf/Q26 — различия между версиями

Текущая версия на 15:32, 15 декабря 2024

Вопрос: Q26-4c9f66

Пусть A и B — два набора слов (строк) из ∑* для некоторого алфавита символов ∑

Предположим, что B является подмножеством A

Какое из следующих утверждений всегда должно быть верным для A и B?

1. Если A конечно, то и B конечно.
2. Если A регулярный язык, то и B такой же.
3. Если A не зависит от контекста, то и B такой же.

Ответы

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

Объяснение

• Конечность конечно передастся подмножеству.
• Но «context-free» или распознавание регулярками конечно нет.

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