Изменения
Нет описания правки
# Улучшить неравенство Чебышева в общем случае нельзя. Докажите, что для любого $c > 0$ найдется такая случайная величина $\xi$, что $P(|\xi - E\xi| \ge c) = D\xi/c^2$.
# Оцените вероятность, что значение на игральной кости отличается от матожидания больше чем на 2 с помощью неравенства Чебышева. Насколько точна эта оценка?
# Докажите, что вероятность того, что значения на двух одинаково распределенных нечестных игральных костях совпадает, не меньше $1/6$.
# Найдите дисперсию следующей случайной величины: число бросков честной монеты до $k$-го выпадения 1.
# Перемножим счетное число вероятностных пространств, соответствующих честным монетам. Что получится? Как бы вы ввели на результате вероятностную меру?
# У вас Сколько байт в колоде бите?# Докажите, что для монеты энтропия максимальна в игре случае честной монеты# Докажите, что для $n$ исходов энтропия максимальна если они все равновероятны# Пусть заданы полные системы событий $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|)$.# <bstrike>HearthstoneКолмогоровская сложность конкатенации. Докажите, что $K(xy) \le K(x) + K(y) + O(1)$.</bstrike># Колмогоровская сложность пары. Докажите, что $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(\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 оптмально выбрать Васе, чтобы его вероятность вытащить виспа 100%выигрыша была максимальна?# Предложите решение предыдущей задачи для произвольной выигрышной строки Пети (за полином от длины этой строки).# Пусть последовательно генерируется последовательность из 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$ регулярный.# <bstrike>HearthsotneДокажите или опровергните утверждения: (а) $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\}$, которые содержат равное число двоек и равное число единиц, или равное число двоек и равное число нулей.# Предложите алгоритм проверки, что МП-автомат допускает заданное слово.# Назовем состояние МП-автомата бесполезным если автомат не может перейти в него ни при каком входном слове. Предложите алгоритм проверки состояния МП-автомата на бесполезность.# Предложите алгоритм проверки, что МП-автомат допускает хотя бы одно слово, содержащее заданное в качестве подстроки.# Предложите алгоритм проверки, что МП-автомат допускает бесконечное число слов.
