Изменения
Нет описания правки
# Петя собирается смотреть серию матчей финала Флатландской хоккейной лиги. В финале две команды играют до 5 побед, ничьих не бывает, таким образом максимум в финале будет не более 9 матчей. Вася рассказал Пете, что всего в финале было 7 матчей. Петя считает матч интересным, если перед его просмотром он не знает, кто выиграет финал. Пусть все возможные последовательности исходов матчей, удовлетворяющих описанным условиями, равновероятны. Какова вероятность, что будет хотя бы 4 интересных матча?
# Петя собирается смотреть серию матчей финала Флатландской хоккейной лиги. В финале две команды играют до 5 побед, ничьих не бывает, таким образом максимум в финале будет не более 9 матчей. Вася рассказал Пете, что всего в финале было 7 матчей. Петя считает матч зрелищным, если перед его просмотром он не знает, кто его выиграет. Пусть все возможные последовательности исходов матчей, удовлетворяющих описанным условиями, равновероятны. Какова вероятность, что будет хотя бы 5 зрелищных матчей?
# Найдите распределение и математическое ожидание следующей случайной величины: число бросков нечестной монеты до первого выпадения 1.
# Найдите распределение и математическое ожидание следующей случайной величины: число бросков честной монеты до второго выпадения 1.
# Используя формулу Стирлинга $n!\approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$ оцените, чему равна вероятность, что на $2n$ брошенных честных монетах выпадет поровну нулей и единиц.
# Найдите математическое ожидание числа инверсий в перестановке чисел от 1 до $n$
# Найдите математическое ожидание числа подъемов в перестановке чисел от 1 до $n$
# Найдите математическое ожидание числа троек $i$, $j$, $k$, где $i < j < k$ и $a[i] < a[j] < a[k]$ в перестановке чисел от 1 до $n$
# Предложите метод генерации случайной перестановки порядка $n$ с равновероятным распределением всех перестановок, если мы умеем генерировать равномерно распределенное целое число от 1 до $k$ для любых небольших $k$ ($k = O(n)$).
# Дает ли следующий метод равномерную генерацию всех перестановок? "p = [1, 2, ..., n]; for i from 1 to n: swap(p[i], p[random(1..n)] )"
# Дает ли следующий метод равномерную генерацию всех перестановок? "p = [1, 2, ..., n]; for i from 1 to n: swap(p[random(1..n)], p[random(1..n)] )"
# Предложите метод генерации случайного сочетания из $n$ по $k$ с равновероятным распределением всех сочетаний, если мы умеем генерировать равномерно распределенное целое число от 1 до $t$ для любых небольших $t$ ($t = O(n)$)
# Предложите метод генерации случайного сочетания из $n$ по $k$ с равновероятным распределением всех сочетаний, если мы умеем генерировать равномерно распределенное целое число от 1 до $t$ для любых небольших $t$ ($t = O(n)$), использующий $O(k)$ времени и памяти.
# Верно ли, что если $\xi$ и $\eta$ - независимые случайные величины, то таким будут и $f(\xi)$ и $g(\eta)$ для любых функций $f$ и $g$? Достаточно доказать для конечных вероятностных пространств.
# Постройте случайную величину, имеющую конечное математическое ожидание и бесконечную дисперсию.
# Постройте случайную величину, имеющую бесконечное математическое ожидание и конечную дисперсию.
# Улучшить неравенство Маркова в общем случае нельзя. Докажите, что для любого $c > 1$ найдется такая неотрицательная случайная величина $\xi$, что $P(\xi \ge cE\xi) = 1/c$.
# Можно ли подобрать такую неотрицательную случайную величину $\xi$, чтобы для двух различных $c_1 > 1$ и $c_2 > 1$ выполнялось $P(\xi \ge c_iE\xi) = 1/c_i$ ($i \in \{1, 2\}$)?
# Для какого максимального $\alpha$ можно подобрать такую неотрицательную случайную величину $\xi$, чтобы для двух различных $c_1 > 1$ и $c_2 > 1$ выполнялось $P(\xi \ge c_iE\xi) = \alpha/c_i$ ($i \in \{1, 2\}$)?
# Улучшить неравенство Чебышева в общем случае нельзя. Докажите, что для любого $c > 0$ найдется такая случайная величина $\xi$, что $P(|\xi - E\xi| \ge c) = D\xi/c^2$.
# Улучшить неравенство Чебышева нельзя даже для суммы. Докажите, что для любого $c > 0$ найдется такое семейство одинаково распределенных случайных величин $\xi_1, \xi_2, \ldots, \xi_n$, что $P(|\sum\xi_i - \sum E\xi_i| \ge c) = nD\xi/c^2$.
# Оцените вероятность, что значение на игральной кости отличается от матожидания больше чем на 2 с помощью неравенства Чебышева. Насколько точна эта оценка?
# Докажите, что вероятность того, что значения на двух одинаково распределенных нечестных игральных костях совпадает, не меньше $1/6$.
# Найдите дисперсию следующей случайной величины: число бросков честной монеты до $k$-го выпадения 1.
# Петя хочет пойти в кино с вероятностью ровно 1/13, а у него есть только честная монета. Может ли он осуществить свой замысел?
# Решите предудыщее задание для любой дроби $0 \le p/q \le 1$.
# Постройте схему получения вероятности 1/3 с помощью честной монеты, имеющую минимальное математическое ожидание числа бросков. Докажите оптимальность вашей схемы.
# Дана нечестная монета. Придумайте метод определения, какое значение выпадает с большей вероятностью. Вероятность того, что этот способ ошибся, должна быть не больше $0.01$. Оцените количество бросков, которое потребуется, в зависимости от того, насколько $p$ отличается от $1/2$.
# Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних двух бросков равны 11. Вася выигрывает, когда результаты последних двух бросков равны 00. С какой вероятностью Петя выиграет?
# Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних трех бросков равны 001. Вася выигрывает, когда результаты последних трех бросков равны 010. С какой вероятностью Петя выиграет?
# Можно ли сделать игру в предыдущем задании честной (чтобы вероятности выигрышей оказались равны $1/2$), используя нечестную монету?
# Сколько байт в бите?
# Докажите, что для монеты энтропия максимальна в случае честной монеты
# Докажите, что для $n$ исходов энтропия максимальна если они все равновероятны
# Найдите энтропию для геометрического распределения с $p = 1/2$ (счетное число исходов, $i$-й исход происходит с вероятностью $1/2^i$).
# Найдите энтропию для геометрического распределения с произвольным $p$ (счетное число исходов, $i$-й исход происходит с вероятностью $(1-p)p^i$).
# Пусть заданы полные системы событий $A = \{a_1, ..., a_n\}$ и $B = \{b_1, ..., b_m\}$. Определим условную энтропию $H(A | B)$ как $-\sum\limits_{i = 1}^m P(b_i) \sum\limits_{j = 1}^n P(a_j | b_i) \log P(a_j | b_i))$. Докажите, что $H(A | B) + H(B) = H(B | A) + H(A)$
# Что можно сказать про $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|$ строго возрастает и выполнено $K(x_i) = o(|x_i|)$.
# Предложите семейство слов $x_1, x_2, \ldots, x_n, \ldots$, где $|x_i|$ строго возрастает и выполнено $K(x_i) = o(\log_2 |x_i|)$.
# Колмогоровская сложность и энтропия Шеннона. Для слова $x$, в котором $i$-й символ алфавита встречается $f_i$ раз обозначим как $H(x)$ величину, равную энтропии случайного источника с распределением $p_i = f_i/|x|$. Докажите, что $K(x) \le nH(x) + O(\log n)$.
# Докажите, что для любого $c > 0$ найдется слово, для которого $K(x) < c n H(x)$
# Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке $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$-ю степень матрицы переходов.
# Предложите алгоритм решения задачи 41 для произвольных выигрышных строк Васи и Пети (работающий за полином от суммы длин этих строк).
# Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних трех бросков равны 001. Какую строку длины 3 оптмально выбрать Васе, чтобы его вероятность выигрыша была максимальна?
# Предложите решение предыдущей задачи для произвольной выигрышной строки Пети (за полином от длины этой строки).
# Пусть последовательно генерируется последовательность из 0 и 1 длины $n$. Каждый элемент последовательности определяется с помощью броска честной монеты. Определите, с какой вероятностью некоторый префикс этой последовательности представляет собой запись двоичного числа, которое делится на 3.
# Пусть последовательно генерируется последовательность из 0 и 1 длины $n$. Каждый элемент последовательности определяется с помощью броска честной монеты. Предложите алгоритм определния, с какой вероятностью некоторый префикс этой последовательности представляет собой запись двоичного числа, которое делится на $p$ для заданного целого $p$.
# Пусть $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 (сначала на вход подаются младшие разряды).
# Докажите нерегулярность языка, каждое слово которого содержит поровну 0 и 1.
# Докажите нерегулярность языка палиндромов.
# Докажите нерегулярность языка тандемных повторов $L = \{ ww | w \in \Sigma^* \}$.
# Докажите нерегулярность языка $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)$.
# Предложите алгоритм проверки того, что регулярный язык бесконечен
# Предложите алгоритм подсчёта числа слов в регулярном языке (если язык бесконечен, алгоритм должен выдать информацию, что он бесконечен). Алгоритм должен работать за полином от числа состояний в автомате.
# Предложите алгоритм проверки того, что регулярный язык является беспрефиксным
# Предложите алгоритм проверки того, что один регулярный язык является подмножеством другого
# Предложите алгоритм проверки того, что регулярные языки не пересекаются
# Предложите алгоритм проверки того, что объединение двух заданных регулярных языков совпадет с некоторым третьим заданным.
# Приведите пример регулярного языка и двух неизоморфных недетерминированных автоматов для него, которые при этом имеют минимальное число состояний среди всех недетерминированных автоматов для этого языка.
# Петя строит автомат для конкатенации языков $L_1$ и $L_2$ из автоматов для этих языков. Оказалось, что автомат для $L_1$ содержит только одно терминальное состояние и Петя просто объединил в одно это состояние и начальное состояние автомата для $L_2$. Всегда ли у Пети получится то, что нужно?
# Петя строит автомат для объединения языков $L_1$ и $L_2$ из автоматов для этих языков. Решив сэкономить, Петя просто объединил в одно начальные состояния автоматов для $L_1$ и $L_2$. Всегда ли у Пети получится то, что нужно?
# Петя строит автомат для замыкания Клини языка $L$. Решив сэкономить, Петя просто провёл $\varepsilon$-переход из каждого терминального состояния в начальное состояние, и сделал начальное состояние также терминальным. Всегда ли у Пети получится то, что нужно?
# Обозначим как $\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 + 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 \}$.
# Рассмотрим язык $\{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\}$, которые содержат равное число двоек и равное число единиц, или равное число двоек и равное число нулей.
# Предложите алгоритм проверки, что МП-автомат допускает заданное слово.
# Назовем состояние МП-автомата бесполезным если автомат не может перейти в него ни при каком входном слове. Предложите алгоритм проверки состояния МП-автомата на бесполезность.
# Предложите алгоритм проверки, что МП-автомат допускает хотя бы одно слово, содержащее заданное в качестве подстроки.
# Предложите алгоритм проверки, что МП-автомат допускает бесконечное число слов.
