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

Пусть L⊆{0,1}∗ — произвольный регулярный язык, допускаемый минимальным ДКА с k состояниями. Какой из следующих языков обязательно должен быть принят минимальным DFA с k состояниями?
(А) Л – {01}
(Б) Л∪{01}
(С) {0,1}*–L
(Г) л⋅л

Ответ: (С)
Объяснение: Вариант (C) является правильным вариантом.

{0,1}*−L = дополнение языка L.

Поскольку у нас есть минимальный DFA с k состояниями для данного языка L.

Мы можем просто поменять местами конечное и не конечное состояния, чтобы получить DFA, который принимает дополнение L без изменения количества состояний.
Викторина этого вопроса