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

​​​​​Рассмотрите следующие два утверждения о регулярных языках:

• S1: Каждый бесконечный регулярный язык содержит неразрешимый язык как подмножество.
• S2: Каждый конечный язык регулярен.

Какой из следующих вариантов правильный?
(A) Верно только S1
(B) Верно только S2
(C) И S1, и S2 верны
(D) Ни S1, ни S2 не верны

Ответ: (С)
Объяснение:

• С1: Верно. Мы можем построить подмножество N множества A, нерегулярность которого будет доказана с помощью леммы о накачке.
• С2: Верно. Каждый конечный язык является регулярным. Потому что мы можем нарисовать для него DFA.

Викторина этого вопроса