Изменения
Нет описания правки
# Рассмотрим детерминированный автомат с магазинной памятью, для которого выполнены свойства из двух предыдущих заданий. Докажите, что для любого состояния $p$ автомата и строки $\gamma$ в стеке существует строка $s$, для которой выполняется следующее свойство. Начав в состоянии $p$ и со стеком $\gamma$, считав строку $s$ автомат переходит некоторое состояние $q$ и имеет в стеке $\beta$, причем какую бы строку далее автомат не получил на вход, на вершине стека никогда не окажется второй символ $\beta$.
# На основании трех предыдущих заданий докажите, что не существует детерминированного автомата с магазинной памятью для языка палиндромов.
# Докажите, что объединение и пересечение разрешимых языков разрешимо.
# Докажите, что объединение и пересечение перечислимых языков перечислимо.
# Докажите, что конкатенация и замыкание Клини разрешимых языков разрешимы.
# Докажите, что конкатенация и замыкание Клини перечислимых языков перечислимы.
# Докажите, что если множества $A$ и $B$ разрешимы (перечислимы), то их декартово произведение перечислимо.
# Докажите, что образ перечислимого множества под действием вычислимой (не обязательно всюду определенной) функции перечислим.
# Докажите, что прообраз перечислимого множества под действием вычислимой (не обязательно всюду определенной) функции перечислим.
# Теорема об униформизации. Пусть задано перечислимое множество пар $F$. Докажите, что найдется вычислимая функция $f$, такая что для любого $x$, для которого существует $y$, такой что $(x,y)\in F$ выполнено, что $(x, f(x)) \in F$.
# Пусть даны два перечислимых множества $X$ и $Y$. Докажите, что существуют непересекающиеся перечислимые множества $X' \subset X$ и $Y' \subset Y$, такие что $X' \cup Y' = X \cup Y$.
# Докажите, что множество чисел $i$, таких, что в десятичной записи числа $\pi$ встречается последовательность из $i$ семерок подряд, перечислимо. Является ли оно разрешимым? Почему?
# Докажите, что множество чисел $i$, таких, что в десятичной записи числа $\pi$ как подстрока десятичная запись $i$, перечислимо. Можно ли привести тот же аргумент, что и в предыдущем задании, для доказательства его (не)разрешимости?
