Изменения
Нет описания правки
# Постройте детерминированный автомат для предыдущего задания или докажите, что в нем слишком много состояний, чтобы его рисовать ;).
# Постройте регулярное выражение для языка слов над бинарным алфавитом, в которых нет двух нулей подряд.
# Построить конечный автомат для языка слов над бинарным алфавитом, в которых которые представляют собой двоичное число 0 кратно , кратное 3.
# ХМУ 4.2.2, стр 163
# ХМУ 4.2.3, стр 163
# Докажите, что язык $\{0^n1^m2^n| n \ne m\}$ не является КС.
# Приведите пример не КС-языка, для которого выполнена лемма о разрастании.
# Постройте МП-автомат для языка $0^n1^n$.
# Постройте МП-автомат для языка слов, где число нулей равно числу единиц.
# Постройте МП-автомат для языка $0^n1^{2n}$.
# Постройте МП-автомат для языка $0^n1^m2^{n+m}$.
# Постройте МП-автомат для языка $0^{2n}1^n$.
# Постройте МП-автомат для языка $0^n1^n\cup0^n1^{2n}$.
# Постройте МП-автомат для языка слов $0^n1^m$, где $n \le m \le 2n$.
# Докажите, что для любых $p$ и $q$ существует МП-автомат для языка слов $0^n1^m$, где $n/m=p/q$
# Постройте автомат с магазинной памятью для языка слов над алфавитом $\{0, 1, 2\}$, которые содержат равное число двоек и равное число единиц, или равное число двоек и равное число нулей.
# Существует ли для языка из предыдущего задания детерминированный автомат?
# Постройте автомат с магазинной памятью для языка палиндромов.
# Докажите, что для любого автомата с магазинной памятью существует эквивалентный, который на каждом переходе кладет в стек не более 2 символов. Ваша конструкция должна сохранять детерминированность автомата, если ранее он был детерминированным.
# Докажите, что для любого детерминированного автомата с магазинной памятью существует эквивалентный, который при $\varepsilon$-переходе только снимает или заменяет верхний символ стека (то есть размер стека не увеличивается на $\varepsilon$-переходах).
# Рассмотрим детерминированный автомат с магазинной памятью, для которого выполнены свойства из двух предыдущих заданий. Докажите, что для любого состояния $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$, перечислимо. Можно ли привести тот же аргумент, что и в предыдущем задании, для доказательства его (не)разрешимости?
# Докажите, что любое бесконечное перечислимое множество содержит бесконечное разрешимое подмножество.
# Пусть $f$ - вычислимая функция. Докажите, что существует вычислимая функция $g$ с областью определения, совпадающей с областью значений $f$, такая что $f(g(f(x))) = f(x)$ для любого $x$, на котором $f$ определена.
# Вещественное число $\alpha$ называется вычислимым, если существует вычислимая функция $a$, которая по любому рациональному $\varepsilon > 0$ даёт рациональное приближение к $\alpha$ с ошибкой не более $\varepsilon$, то есть $|\alpha-a(\varepsilon)| \le \varepsilon$ для любого рационального $\varepsilon > 0$. Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда множество рациональных чисел, меньших $\alpha$, разрешимо
# Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда последовательность знаков представляющей его десятичной (или двоичной) дроби вычислима.
# Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к $\alpha$ (то есть является вычислимой функция, которая по $\varepsilon$ возвращает $n_0$, такое что $|a_n - \alpha| \le \varepsilon$ для $n > n_0$)
# Покажите, что сумма, произведение, разность и частное вычислимых действительных чисел вычислимы. Покажите, что корень многочлена с вычислимыми коэффициентами вычислим.
# Сформулируйте и докажите утверждение о том, что предел вычислимо сходящейся последовательности вычислимых действительных чисел вычислим.
# Вещественное число $\alpha$ называют перечислимым снизу, если множество всех рациональных чисел, меньших $\alpha$, перечислимо. Перечислимость сверху определяется аналогично. Докажите, что число $\alpha$ перечислимо снизу тогда и только тогда, когда оно является пределом некоторой вычислимой возрастающей последовательности рациональных чисел.
# Докажите, что вещественное число вычислимо тогда и только тогда, когда оно перечислимо снизу и сверху.
# Покажите, что следующие три свойства множества $X$ равносильны: (1) $X$ можно представить в виде $A \setminus B$, где $A$ — перечислимое множество, а $B$ — его перечислимое подмножество; (2) $X$ можно представить в виде $A \setminus B$, где $A$ и $B$ — перечислимые множества; (3) $X$ можно представить в виде симметрической разности двух перечислимых множеств.
# Покажите, что множество $X$ можно представить в виде $A\setminus (B\setminus C)$, где $A \supset B \supset C$ — перечислимые множества, если и только если его можно представить в виде симметрической разности (суммы по модулю 2) трёх перечислимых множеств.
# Пусть $A(x,y)$ - вычислимая функция от двух аргументов. Докажите, что для любого $x$ функция $A_x(y)=A(x, y)$ как функция одного аргумента - вычислима.
# Пусть $A(x,y)$ - функция от двух аргументов и для любого $x$ функция $A_x(y)=A(x, y)$ как функция одного аргумента - вычислима. Значит ли это. что функция $A$ вычислима как функция двух аргументов?
# Функция $f$ называется продолжением функции $g$, если для любого $n$, такого что $g$ определена, $f$ также определена и $f(n) = g(n)$. Докажите, что существует вычислимая функция $d(n)$, такая что никакая всюду определенная вычислимая функция $f(n)$ не является ее продолжением.
# Пусть множество пар $A=\{(x, y)\}$ перечислимо. Можно ли утверждать, что множество $B$ минимальных парных для каждого $x$ ($B = \{(x, y)| (x, y) \in A \wedge (x, z)\in A \Rightarrow z \ge y\}$ перечислимо?
# Пусть множество пар $A=\{(x, y)\}$ разрешимо. Можно ли утверждать, что множество $B$ минимальных парных для каждого $x$ ($B = \{(x, y)| (x, y) \in A \wedge (x, z)\in A \Rightarrow z \ge y\}$ перечислимо? Разрешимо?
# Пусть $A$ - произвольный список слов $(a_1, a_2, \ldots, a_n)$ над алфавитом $\Sigma$, содержащем хотя бы 2 символа. Рассмотрим алфавит $\Pi = \Sigma \cup \{1, 2, \ldots, n\}$. Обозначим как $L_A$ язык, содержащий множество слов, порождаемых грамматикой $S\to\varepsilon$, $S\to a_1S1$, ..., $S\to a_n S n$. Докажите, что для любого списка язык $\overline{L_A}$ дополнение до $L_A$ является контекстно-свободным.
# В этой и последующих задачах для задания КС-языка используется некоторая произвольная его КС-грамматика, а для задания регулярного языка - на ваш выбор конечный автомат или регулярное выражение. Докажите, что задача проверки пустоты пересечения контекстно-свободных языков алгоритмически неразрешима.
# Докажите, что задача равенства двух контекстно-свободных языков алгоритмически неразрешима.
# Докажите, что задача проверка равенства заданных контекстно-свободного языка и регулярного языка алгоритмически неразрешима.
# Докажите, что задача проверки равенства КС-языка языку $\Sigma^*$ алгоритмически неразрешима
# Докажите, что задача проверки, что один контекстно-свободный язык является подмножеством другого алгоритмически неразрешима.
# Докажите, что задача проверки, что заданный регулярный язык является подмножеством заданного контекстно-свободного алгоритмически неразрешима.
# Докажите, что множество КС-грамматик, порождающих язык, содержащий хотя бы один палиндром, неразрешимо
# Докажите, что язык $\overline{L_A}\cup\overline{L_B}$ является регулярным тогда и только тогда, когда он совпадает с $\Sigma^*$, то есть соответствующий экземпляр ПСП неразрешим. Сделайте вывод относительно возможности проверки КС-языка на регулярность.
# Докажите, что задача проверки, что дополнение КС-языка является КС-языком, алгоритмически неразрешима
