Изменения
Нет описания правки
# Что можно сказать про $H(A | B)$ если $a_i$ и $b_j$ независимы для любых $i$ и $j$?
# Что можно сказать про $H(A | A)$?
# Зафиксируем любой язык программирования. Колмогоровской сложностью слова $x$ называется величина $K(x)$ - минимальная длина программы на зафиксированном языке программирвоанияпрограммирования, которая на пустом входе выводит $x$. Обозначим длину слова $x$ как $|x|$. Докажите, что $K(x) \le |x| + c$ для некоторой константы $c$.# Предложите семейство слов $x_1, x_2, \ldots, x_n, \ldots$, где $|x_i|=i$ строго возрастает и начиная с некоторого $n$ выполнено $K(x_i) < i= o(|x_i|)$.# Предложите семейство слов $x_1, x_2, \ldots, x_n, \ldots$, где $|x_i|=i$ строго возрастает и начиная с некоторого $n$ выполнено $K(x_i) < = o(\log_2 i|x_i|)$.# <strike>Колмогоровская сложность конкатенации. Докажите, что $K(xy) \le K(x) + K(y) + O(1)$.</strike>
# Колмогоровская сложность пары. Докажите, что $K(\langle x, y\rangle) \le K(x) + K(y) + O(\log |x|)$.
# Колмогоровская сложность и энтропия Шеннона. Для слова $x$, в котором $i$-й символ алфавита встречается $f_i$ раз обозначим как $H(x)$ величину, равную энтропии случайного источника с распределением $p_i = f_i/|x|$. Докажите, что $K(x) \le nH(x) + O(1\log n)$.
# Докажите, что для любого $c > 0$ найдется слово, для которого $K(x) < c n H(x)$
# Петя хочет пойти в кино с вероятностью ровно 1/13, а у него есть только честная монета. Может ли он осуществить свой замысел?
# Решите предудыщее задание для любой дроби $0 \le p/q \le 1$.
# Постройте схему получения вероятности 1/3 с помощью честной монеты, имеющую минимальное математическое ожидание числа бросков. Докажите оптимальность вашей схемы.
# Дана нечестная монета. Требуется определитьПридумайте метод определения, какое значение выпадает с большей вероятностью. Как это сделать? Вероятность того, что этот способ ошибся, должна быть не больше $0.01$. Оцените количество бросков, которое потребуется, в зависимости от того, насколько $p$ отличается от $1/2$.
# Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних двух бросков равны 11. Вася выигрывает, когда результаты последних двух бросков равны 00. С какой вероятностью Петя выиграет?
# Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних трех бросков равны 001. Вася выигрывает, когда результаты последних трех бросков равны 010. С какой вероятностью Петя выиграет?
# Можно ли сделать игру в предыдущем задании честной (чтобы вероятности выигрышей оказались равны $1/2$), используя нечестную монету?
# Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке $p$ ($p$ - целое) и каждую секунду переходит равновероятно на 1 влево или вправо. Точка поглощается в точках 0 и $n$ ($n$ целое, больше $p$). Найдите вероятность поглощения в точке 0.
# Для заданной рациональной дроби $p/q$ постройте марковскую цепь, все переходы которой имеют вероятность $1/2$, которая имеет поглощающее состояние с вероятностью поглощения $p/q$.
# Для заданной рациональной дроби $p/q$ постройте марковскую цепь, все переходы которой имеют вероятность $1/3$, которая имеет поглощающее состояние с вероятностью поглощения $p/q$.
# Для заданной рациональной дроби $p/q$ и целого $n$ постройте марковскую цепь, все переходы которой имеют вероятность $1/n$, которая имеет поглощающее состояние с вероятностью поглощения $p/q$.
# Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке 0 и каждую секунду переходит равновероятно на 1 влево или вправо. Чему равно математическое ожидание координаты точки после $n$ шагов?
# Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке 0 и каждую секунду переходит равновероятно на 1 влево или вправо. Докажите, что математическое ожидание максимума координаты точки за $n$ шагов есть $O(\sqrt{n})$. Поясните разницу с предыдущим заданием.
# Дана марковская цепь с двумя состояниями и вероятностью перехода из 1 в 2 равной $a$, вероятностью перехода из 2 в 1 равной $b$. Найдите в явном виде $n$-ю степень матрицы переходов.
# Предложите алгоритм решения задачи 54 для произвольных выигрышных строк Васи и Пети (работающий за полином от суммы длин этих строк).
# Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних двух бросков равны 001. Какую строку длины 3 оптмально выбрать Васе, чтобы его вероятность выигрыша была максимальна?
# Предложите решение предыдущей задачи для произвольной выигрышной строки Пети (за полином от длины этой строки).
# Пусть последовательно генерируется последовательность из 0 и 1 длины $n$. Каждый элемент последовательности определяется с помощью броска честной монеты. Определите, с какой вероятностью некоторый префикс этой последовательности представляет собой запись двоичного числа, которое делится на 3.
# Пусть последовательно генерируется последовательность из 0 и 1 длины $n$. Каждый элемент последовательности определяется с помощью броска честной монеты. Предложите алгоритм определния, с какой вероятностью некоторый префикс этой последовательности представляет собой запись двоичного числа, которое делится на $p$ для заданного целого $p$.
# Постройте регулярную Марковскую цепь с двумя состояниями и эргодическим распределением $[a, 1-a]$ для заданного $a$.
# Постройте регулярную Марковскую цепь с $n$ состояниями и заданным эргодическим распределением.
# Пусть $L$ - формальный язык. Докажите, что $(L^*)^* = L^*$
# Пусть $R$ и $S$ - языки. Докажите или опровергните, что $(R \cup S)^* = R^* \cup S^*$.
# Пусть $R$ и $S$ - языки. Докажите или опровергните, что $(R \cap S)^* = R^* \cap S^*$.
# Пусть $R$ и $S$ - языки. Докажите или опровергните, что $(R \cup S)^* = (R^*S^*)^*$.
# Пусть $R$ и $S$ - языки. Обозначим как $RS$ язык слов, представимых в виде конкатенации слова из $R$ и слова из $S$ (в этом порядке). Докажите или опровергните, что $(R\cup S)T=RT \cup ST$, $(R\cap S)T=RT \cap ST$.
# Пусть $L$ - язык. Обозначим как $Lc$ язык, который получается из $L$ дописыванием в конец каждому слову символа $c$. Обозначим как $Lc^{-1}$ язык, который получается из $L$ откидыванием всех слов, которые не заканчиваются на $c$, а затем у оставшихся слов откидыванием конечного символа $c$. Докажите или опровергните, что $(Lc)c^{-1}=L$, $(Lc^{-1})c=L$.
# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых четность числа 0 равна четности числа 1
# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3
# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей не кратно 3. Сделайте вывод из последних двух заданий.
# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых нет трех нулей подряд
# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых есть три нуля подряд
# Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой двоичную запись чисел, кратных 5
# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3 и которые представляют собой двоичную запись чисел кратных 5.
# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3 или которые представляют собой двоичную запись чисел кратных 5. Сделайте вывод из последних двух заданий.
# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число единиц кратно 3. Сделайте вывод.
# Постройте детерминированный конечный автомат для языка слов над бинарным алфавитом, в которых второй символ с конца равен последнему символу.
# Для заданного ДКА размера $n$ посчитать количество слов длины $d$, которые он допускает за $O(dn)$.
# То же самое, что в предыдущей, но за $O(\log{(d)} \cdot Poly(n))$.
# Посчитать количество слов длины не больше $d$, которые допускает автомат за $O(\log{(d)} \cdot Poly(n))$.
# Запишите регулярное выражения для слов над бинарным алфавитом, содержащих два нуля подряд.
# Запишите регулярное выражения для слов над бинарным алфавитом, содержащих не более одного места, где встречаются два нуля подряд.
# Запишите регулярное выражения для слов над бинарным алфавитом, не содержащих два нуля подряд.
# Запишите регулярное выражения для слов над алфавитом $\{a, b, c\}$, содержащих нечетное число букв $a$.
# Запишите регулярное выражения для слов над бинарным алфавитом, задающих целое число в двоичной системе, не меньшее 8.
# Запишите регулярное выражения для слов над бинарным алфавитом, задающих целое число в двоичной системе, не меньшее 51.
# Запишите регулярное выражения для слов над алфавитом $\{a, b, c\}$, содержащих хотя бы одну букву $a$ и хотя бы одну букву $b$.
# Запишите регулярное выражения для слов над алфавитом $\{a, b, c\}$, содержащих хотя бы две буквы $a$ и хотя бы одну букву $b$.
# Запишите регулярное выражения для слов над бинарным алфавитом, которые представляют собой двоичную запись числа, кратного трем.
# Постройте детерминированный конечный автомат для языка слов над бинарным алфавитом, в которых пятый символ с конца - единица.
# Докажите, что любой детерминированный автомат для языка слов над бинарным алфавитом, в которых $k$-й символ с конца равен 0, содержит $\Omega(2^k)$ состояний.
# Можно ли обобщить два предыдущих задания для любого размера алфавита $c$ следующим образом: построить семейство языков, для которых будут существовать НКА, содержащий $O(k)$ состояний, но любые ДКА будут содержать $\Omega(c^k)$ состояний?
# Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой развернутую двоичную запись чисел кратных 5 (сначала на вход подаются младшие разряды).
# Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой развернутую двоичную запись чисел кратных 6 (сначала на вход подаются младшие разряды).
# Рассмотрим язык $\{x_0 y_0 z_0 x_1 y_1 z_1 \dots x_{n-1} y_{n-1} z_{n-1} \mid x_i, y_i, z_i \in \{0, 1\}\}$, где $ X = x_{n-1}x_{n-2}\dots x_0$ и аналогично представляется $Y$ и $Z$, причем $ X + Y = Z $. Докажите, что этот язык регулярный.
# То же, что и предыдущее, только $\{x_{n-1} y_{n-1} z_{n-1} \dots x_1 y_1 z_1 x_0 y_0 z_0 \mid \dots \}$.
# Петя строит автомат для конкатенации языков $L_1$ и $L_2$ из автоматов для этих языков. Оказалось, что автомат для $L_1$ содержит только одно терминальное состояние и Петя просто объединил в одно это состояние и начальное состояние автомата для $L_2$. Всегда ли у Пети получится то, что нужно?
# Петя строит автомат для объединения языков $L_1$ и $L_2$ из автоматов для этих языков. Решив сэкономить, Петя просто объединил в одно начальные состояния автоматов для $L_1$ и $L_2$. Всегда ли у Пети получится то, что нужно?
# Петя строит автомат для замыкания Клини языка $L$. Решив сэкономить, Петя просто провёл $\varepsilon$-переход из каждого терминального состояния в начальное состояние, и сделал начальное состояние также терминальным. Всегда ли у Пети получится то, что нужно?
# Для символа $a$ обозначим как $La^{-1}$ множество слов $w$, таких что $wa \in L$. Докажите, что если $L$ регулярный, то $La^{-1}$ регулярный.
# Для символа $a$ обозначим как $a^{-1}L$ множество слов $w$, таких что $aw \in L$. Докажите, что если $L$ регулярный, то $a^{-1}L$ регулярный.
# <strike>Докажите или опровергните утверждения: (а) $Laa^{-1}=L$, (б) $La^{-1}a=L$, (в) $a^{-1}(aL)=L$, (г) $a(a^{-1}L)=L$.</strike>
# Пусть $R$ и $S$ - регулярные языки. Выразите $(RS)a^{-1}$ через $R$, $S$, $Ra^{-1}$ и $Sa^{-1}$. Указание: рассмотрите два случая: $\varepsilon \in S$ или $\varepsilon \not\in S$.
# Докажите нерегулярность языка, каждое слово которого содержит поровну 0 и 1.
# Докажите нерегулярность языка палиндромов.
# Докажите нерегулярность языка тандемных повторов.
# Докажите нерегулярность языка $0^n1^m$, $n \le m$
# Докажите нерегулярность языка $0^n1^m$, $n \ne m$
# Докажите нерегулярность языка $0^{n^2}$
# Докажите нерегулярность языка $0^p$, $p$ {{---}} простое
# Докажите нерегулярность языка двоичных записей простых чисел
# Докажите нерегулярность языка $0^n1^m$, $gcd(n, m) = 1$
# Докажите нерегулярность языка $0^a1^b2^c$, $a \ne b$ или $b \ne c$
# Приведите пример нерегулярного языка, для которого выполнена лемма о разрастании
# Из алгоритма построения множества различимых состояний следует, что $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n^2)$. Докажите, что если состояния $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n)$.
# Обозначим как $\min L$ множество слов $w \in L$, таких что никакой собственный префикс $w$ не является словом языка $L$. Докажите, что если $L$ регулярный, то и $\min L$ регулярный.
# Обозначим как $\max L$ множество слов $w \in L$, таких что $w$ не является собственным префиксом никакого словом языка $L$. Докажите, что если $L$ регулярный, то и $\max L$ регулярный.
# Обозначим как $\mbox{pref}\,L$ множество префиксов слов языка $L$. Докажите, что если $L$ регулярный, то и $\mbox{pref}\,L$ регулярный.
# Обозначим как $\mbox{suf}\,L$ множество суффиксов слов языка $L$. Докажите, что если $L$ регулярный, то и $\mbox{suf}\,L$ регулярный.
# Пусть $a$ и $b$ - слова равной длины $n$. Обозначим как $\mbox{alt}(a, b)$ слово $a_1b_2a_2b_2\ldots a_nb_n$. Для языков $R$ и $S$ обозначим как $\mbox{alt}(R, S)$ множество всех слов, которые получаются как $\mbox{alt}(a, b)$ где $a \in R$, $b \in S$. Докажите, что если $R$ и $S$ регулярные, то $\mbox{alt}(R, S)$ регулярный.
# Пусть $a$ и $b$ - слова. Обозначим как $\mbox{shuffle}(a, b)$ множество слов, которые можно составить, вставив в слово $a$ все буквы слова $b$ в том порядке, в котором они идут в $b$. Например, $\mbox{shuffle}(01, 23)=\{0123, 0213, 0231, 2013, 2031, 2301\}$. Для языков $R$ и $S$ обозначим как $\mbox{shuffle}(R, S)$ объединение всех множеств $\mbox{shuffle}(a, b)$ где $a \in R$, $b \in S$. Докажите, что если $R$ и $S$ регулярные, то $\mbox{shuffle}(R, S)$ регулярный.
# Обозначим как $\mbox{cycle}\,L$ множество циклических сдвигов слов языка $L$. Докажите, что если $L$ регулярный, то и $\mbox{cycle}\,L$ регулярный.
# Обозначим как $\mbox{half}\,L$ множество таких слов $a$, что существует слово $b$ такой же длины, как и $a$, что $ab \in L$. Докажите, что если $L$ регулярный, то и $\mbox{half}\,L$ регулярный.
# Предложите алгоритм проверки того, что регулярный язык бесконечен
# Предложите алгоритм подсчёта числа слов в регулярном языке (если язык бесконечен, алгоритм должен выдать информацию, что он бесконечен). Алгоритм должен работать за полином от числа состояний в автомате.
# Предложите алгоритм проверки того, что регулярный язык является беспрефиксным
# Предложите алгоритм проверки того, что один регулярный язык является подмножеством другого
# Предложите алгоритм проверки того, что регулярные языки не пересекаются
# Предложите алгоритм проверки того, что объединение двух заданных регулярных языков совпадет с некоторым третьим заданным.
# Приведите пример регулярного языка и двух неизоморфных недетерминированных автоматов для него, которые при этом имеют минимальное число состояний среди всех недетерминированных автоматов для этого языка.
# Рассмотрим язык $\{x_0 y_0 z_0 x_1 y_1 z_1 \dots x_{n-1} y_{n-1} z_{n-1} \mid x_i, y_i, z_i \in \{0, 1\}\}$, где $X = x_{n-1}x_{n-2}\dots x_0$ и аналогично представляется $Y$ и $Z$, причем $X \times Y = Z$. Докажите, что этот язык не является регулярным.
# Рассмотрим отношение на словах $L$: $x \equiv y$, если для любых $u$, $v$ выполнено $uxv \in L \Leftrightarrow uyv \in L$. Классы эквивалентности этого отношения называются синтаксическим моноидом языка $L$. Докажите, что $L$ регулярный тогда и только тогда, когда синтаксический моноид $L$ конечен.
# Придумайте семейство регулярных языков $L_i$, у которых ДКА для $L_i$ содержит $O(i)$ состояний, а синтаксический моноид $L_i$ имеет неполиномиальный размер.
# Постройте КС-грамматику для правильных скобочных последовательностей с двумя типами скобок.
# Постройте КС-грамматику для языка $0^n1^n$.
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей равно числу единиц. Докажите, что ваша грамматика является правильной.
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей равно удвоенному числу единиц. Докажите, что ваша грамматика является правильной.
# Постройте КС-грамматику для языка $0^k1^n2^{k+n}$.
# Постройте КС-грамматику для языка $0^k1^n2^{k+n}\cup 1^k0^n2^{k+n}$.
# Постройте КС-грамматику для языка $0^k1^n2^{k+n}1^i0^j2^{i+j}$.
# Постройте КС-грамматику для языка $0^i1^j2^k$, $i \ne j$ или $j \ne k$.
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются палиндромами.
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются правильными скобочными последовательностями.
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей не равно числу единиц.
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются тандемными повторами.
# Верно ли, что любую КС-грамматику можно привести к форме, когда любое правило имеет вид $A\to BCD$ или $A\to a$?
# Верно ли, что любой КС-язык над односимвольным алфавитом является регулярным?
# Докажите, что язык не является КС: $0^i1^j2^k$, $i<j<k$.
# Докажите, что язык не является КС: $0^n1^n2^k$, $k<n$.
# Докажите, что язык не является КС: $0^p$, $p$ простое.
# Докажите, что язык двоичных записей простых чисел не является КС.
# Докажите, что язык не является КС: $0^i1^j$, $j=i^2$.
# Докажите, что язык не является КС: $0^n1^n2^k$, $n<k<2n$.
# Докажите, что язык не является КС: $ww^Rw$, $w$ - строка из 0 и 1, $w^R$ - развернутая строка $w$.
# Докажите, что язык $\{0^n1^m2^n3^m\}$ не является КС.
# Докажите, что язык $\{0^n1^m2^n| n \ne m\}$ не является КС.
# Приведите пример не КС-языка, для которого выполнена лемма о разрастании.
# Приведите пример КС-языка, не являющегося регулярным, дополнение к которому также является КС.
# Приведите пример двух КС-языка, не являющихся регулярными, пересечение которых также является КС, но не регулярным, причем отлично от обоих пересекаемых языков.
# Пусть $f : \Sigma \to \Sigma^*$ - функция, сопоставляющая каждому символу некоторую строку. Распространим $f$ на слова следующим образом: $f(c_1c_2\ldots c_k) = f(c_1)f(c_2)\ldots f(c_k)$. Обозначим как $f(L)$ множество слов $f(x)$ для всех $x \in L$. Докажите или опровергните, что если $L$ - КС, то $f(L)$ также КС.
# Пусть $f : \Sigma \to \Sigma^*$ - функция, сопоставляющая каждому символу некоторую строку. Распространим $f$ на слова следующим образом: $f(c_1c_2\ldots c_k) = f(c_1)f(c_2)\ldots f(c_k)$. Обозначим как $f^{-1}(L)$ множество таких слов $x$, для которых $f(x) \in L$. Докажите или опровергните, что если $L$ - КС, то $f^{-1}(L)$ также КС.
# Докажите или опровергните, что язык является контекстно-свободным: $0^a1^b2^a$, $a=2b$
# Докажите или опровергните, что язык является контекстно-свободным: $0^a1^b2^a$, $2a=b$
# Докажите или опровергните, что язык является контекстно-свободным: $0^a1^b2^a$, $a\ne 2b$
# Докажите или опровергните, что язык является контекстно-свободным: $0^a1^b2^a$, $2a\ne b$
# Рассмотрим список слов $A = \{\alpha_1, \alpha_2, \ldots, \alpha_n\}$ над алфавитом $\Sigma$. Введем $n$ новых различных символов $d_1, d_2, \ldots, d_n$. Рассмотрим алфавит $\Sigma' = \Sigma \cup \{d_1, d_2, \ldots, d_n\}$. Рассмотрим язык списка $A$, обозначаемый как $L_A$, в который входят все слова вида $\alpha_{i_1}\alpha_{i_2}\ldots\alpha_{i_k}d_{i_k}d_{i_{k-1}}\ldots d_{i_1}$. Докажите, что для любого списка $A$ язык $L_A$ является контекстно-свободным.
# Докажите, что дополнение к языку списка $L_A$ является контекстно-свободным для любого списка $A$.
# Можно неправильно определить язык списка $A = \{\alpha_1, \alpha_2, \ldots, \alpha_n\}$ из предыдущего задания, составив его из слов вида $\alpha_{i_1}\alpha_{i_2}\ldots\alpha_{i_k}d_{i_1}d_{i_2}\ldots d_{i_k}$. Докажите или опровергните, что при таком неправильном определении язык списка все еще будет конткстно-свободным для любого списка $A$.
# Постройте МП-автомат для языка $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\}$, которые содержат равное число двоек и равное число единиц, или равное число двоек и равное число нулей.
# Предложите алгоритм проверки, что МП-автомат допускает заданное слово.
# Назовем состояние МП-автомата бесполезным если автомат не может перейти в него ни при каком входном слове. Предложите алгоритм проверки состояния МП-автомата на бесполезность.
# Предложите алгоритм проверки, что МП-автомат допускает хотя бы одно слово, содержащее заданное в качестве подстроки.
# Предложите алгоритм проверки, что МП-автомат допускает бесконечное число слов.
