Изменения
Нет описания правки
# Докажите, что для разбиений на произвольное число подмножеств, каждое из которых содержит четное число элементов, экспоненциальная производящая функция равна $e^{\mathrm{ch}\,z-1}$. Почему здесь в показателе степени есть $-1$, а в предыдущем задании нет?
# Обобщите четыре предыдущих задания. Как выглядят экспоненциальные производящие функции для разбиений на (не)четное число подмножеств, каждое из которых содержит (не)четное число элементов? (Необходимо дать четыре ответа для всех комбинаций)
# Докажите, что объединение перечислимых языков перичислимоперeчислимо.# Докажите, что пересечение перечислимых языков перичислимоперeчислимо.# Докажите, что конкатенация перечислимых языков перичислимаперeчислима.# Докажите, что замыкание Клини перечислимого языка перичислимоперeчислимо.# Докажите, что декартово произведение перечислимых языков перичислимоперeчислимо.
# Докажите, что проекция перечислимого языка пар на каждую из осей перечислима.
# Пусть $A \subset \Sigma^*$. Функция $f:A \to \Sigma^*$ называется вычислимой, если существует программа, которая по входу $x \in A$ выдает $f(x)$, а на входах не из $A$ зависает. Приведите пример невычислимой функции.
