Список заданий по ДМ 2016 весна

<wikitex>

1. Чему равна вероятность, что две случайно вытянутые кости домино можно приложить друг к другу по правилам домино?
2. Чему равна вероятность, что на двух брошенных честных игральных костях выпадут числа, одно из которых делит другое?
3. Чему равна вероятность, что если вытянуть из колоды две случайные карты, одной из них можно побить другую (одна из мастей назначена козырем, картой можно побить другую, если они одинаковой масти или если одна из них козырь)?
4. Чему равна вероятность, что на двадцати брошенных честных монетах выпадет поровну нулей и единиц?
5. Петя и Вася три раза бросают по одной честной игровой кости. Вася два раза выкинул строго больше, чем Петя, а один раз строго меньше. При этом Петя в сумме выкинул строго больше, чем Вася. С какой вероятностью такое могло произойти?
6. Петя собирается смотреть серию матчей финала Флатландской хоккейной лиги. В финале две команды играют до 5 побед, ничьих не бывает, таким образом максимум в финале будет не более 9 матчей. Вася рассказал Пете, что всего в финале было 7 матчей. Петя считает матч интересным, если перед его просмотром он не знает, кто выиграет финал. Какова вероятность, что будет хотя бы 5 интересных матчей?
7. Петя собирается смотреть серию матчей финала Флатландской хоккейной лиги. В финале две команды играют до 5 побед, ничьих не бывает, таким образом максимум в финале будет не более 9 матчей. Вася рассказал Пете, что всего в финале было 7 матчей. Петя считает матч зрелищным, если перед его просмотром он не знает, кто его выиграет. Какова вероятность, что будет хотя бы 5 зрелищных матчей?
8. Приведите пример событий, независимых попарно, но зависимых в совокупности
9. Приведите пример трех событий, для которых $P(A \cap B \cap C) = P(A)P(B)P(C)$, но которые не являются независимыми, причем вероятности всех трех событий больше 0
10. Доказать или опровергнуть, что для независимых событий $A$ и $B$ и события $C$, где $P(C) > 0$ выполнено $P(A \cap B|C) = P(A|C)P(B|C)$
11. Доказать или опровергнуть, что для независимых событий $A$ и $B$ и события $C$, где $P(A) > 0$, $P(B) > 0$ выполнено $P(C|A \cap B) = P(C|A)P(C|B)$
12. Рассмотрим множество костей домино (неупорядоченные пары $(i, j)$, где $i$ и $j$ от 0 до 6, всего костей 28). Можно ли вероятностное пространство костей домино естественным образом представить как прямое произведение вероятностных пространств?
13. Доказать или опровергнуть: если $P(A|B) = P(B|A)$, то $P(A) = P(B)$
14. Доказать или опровергнуть: если $P(A|B) = P(B|A)$, то $A$ и $B$ независимы
15. Доказать или опровергнуть: если $P(A|C) = P(B|C)$, то $P(C|A) = P(C|B)$
16. Доказать или опровергнуть: если $A$ и $B$ независимы, то $\Omega \setminus A$ и $\Omega \setminus B$ независимы
17. Перемножим счетное число вероятностных пространств, соответствующих честным монетам. Что получится? Как бы вы ввели на результате вероятностную меру?
18. Найдите математическое ожидание и дисперсию значения на нечестной монете
19. Найдите распределение и математическое ожидание следующей случайной величины: число бросков нечестной монеты до первого выпадения 1.
20. Найдите распределение и математическое ожидание следующей случайной величины: число бросков честной монеты до второго выпадения 1.
21. Докажите, что если $f$ и $g$ независимы, то для любых $a$ и $b$ события $[f = a]$ и $[g = b]$ независимы
22. Случайные величины f, g и h называются независимыми в совокупности, если для любых a, b и c события [f <= a], [g <= b] и [h <= c] независимы. Приведите пример независимых попарно, но не независимых в совокупности случайных величин
23. Случайные величины f, g и h называются независимыми в совокупности, если для любых a, b и c события [f <= a], [g <= b] и [h <= c] независимы. Приведите пример независимых попарно, но не независимых в совокупности случайных величин, запрещается использовать величины, пропорциональные индикаторным случайным величинам событий
24. Найдите математическое ожидание числа инверсий в перестановке чисел от 1 до $n$
25. Найдите математическое ожидание числа подъемов в перестановке чисел от 1 до $n$
26. Найдите математическое ожидание числа троек $i$, $j$, $k$, где $i < j < k$ и $a[i] < a[j] < a[k]$ в перестановке чисел от 1 до $n$
27. Предложите метод генерации случайной перестановки порядка $n$ с равновероятным распределением всех перестановок, если мы умеем генерировать равномерно распределенное целое число от 1 до $k$ для любых небольших $k$ ($k = O(n)$).
28. Дает ли следующий метод равномерную генерацию всех перестановок? "p = [1, 2, ..., n]; for i from 1 to n: swap(p[i], p[random(1..n)] )"
29. Дает ли следующий метод равномерную генерацию всех перестановок? "p = [1, 2, ..., n]; for i from 1 to n: swap(p[random(1..n)], p[random(1..n)] )"
30. Предложите метод генерации случайного сочетания из $n$ по $k$ с равновероятным распределением всех сочетаний, если мы умеем генерировать равномерно распределенное целое число от 1 до $t$ для любых небольших $t$ ($t = O(n)$)
31. Предложите метод генерации случайного сочетания из $n$ по $k$ с равновероятным распределением всех сочетаний, если мы умеем генерировать равномерно распределенное целое число от 1 до $t$ для любых небольших $t$ ($t = O(n)$), использующий $O(k)$ времени и памяти.
32. Найдите математическое ожидание и дисперсию значения на честной игральной кости
33. Верно ли, что если $\xi$ и $\eta$ - независимые случайные величины, то таким будут и $f(\xi)$ и $g(\eta)$ для любых функций $f$ и $g$?
34. Постройте случайную величину, имеющую конечное математическое ожидание и бесконечную дисперсию.
35. Оцените вероятность, что значение на игральной кости отличается от матожидания больше чем на 2 с помощью неравенства Чебышева. Какова погрешность оценки?
36. Докажите, что вероятность того, что значения на двух нечестных игральных костях совпадает, не меньше $1/6$.
37. Найдите дисперсию следующей случайной величины: число бросков честной монеты до первого выпадения 1.
38. Найдите дисперсию следующей случайной величины: число бросков честной монеты до $k$-го выпадения 1.
39. Докажите, что корреляция случайных величин лежит в диапазоне от -1 до 1
40. Докажите или опровергните, что корреляция случайных величин равна 0 тогда и только тогда, когда они независимы
41. Докажите, что корреляция случайных величин равна 1 тогда и только тогда, когда они линейно зависимы $(f = cg)$ и $c > 0$ (если $c < 0$, то корелляция равна -1)
42. Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних двух бросков равны 11. Вася выигрывает, когда результаты последних двух бросков равны 00. С какой вероятностью Петя выиграет?
43. Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних двух бросков равны 01. Вася выигрывает, когда результаты последних двух бросков равны 00. С какой вероятностью Петя выиграет?
44. Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних двух бросков равны 01. Вася выигрывает, когда результаты последних двух бросков равны 00. С какой вероятностью Петя выиграет?
45. Можно ли сделать игру в предыдущем задании честной (чтобы вероятности выигрышей оказались равны $1/2$), используя нечестную монету?
46. По аналогии с доказательством на лекции, докажите оценку на отклонение суммы $n$ честных монет от $n/2$ вниз: $P(\xi \le (1-\delta)n/2) \le \exp(-\delta^2/(4n))$.
47. Используйте метод границы Чернова, чтобы следующее. Пусть нечестную монету с вероятностью выпадения 1 равной p бросили $n$ раз. Обозначим случайную величину "число выпавших единиц" как $\xi$. Тогда $P(\xi \le n/2) \le exp(-\frac{1}{2p}n\left(p-\frac{1}{2}\right)^2)$.
48. Сколько байт в бите?
49. Докажите, что для монеты энтропия максимальна в случае честной монеты
50. Докажите, что для n исходов энтропия максимальна если они все равновероятны
51. Зафиксируйте ваш любимый язык программирования. Колмогоровской сложностью $K(x)$ для слова $x$ называется длина минимальной программы, которая выводит слово $x$. Докажите, что колмогоровская сложность не превышает $n H(x) + O(\log n)$, где $n$ - длина строки $x$, $H(x)$ - энтропия случайного источника с распределением соответствующим частотам встречания символов в $x$, константа в $O$, не зависит от слова $x$ (но может зависеть от выбранного языка программирования)
52. Докажите, что для любого $c > 0$ найдется слово, для которого $K(x) < c n H(x)$
53. Пусть заданы полные системы событий $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)$
54. Что можно сказать про $H(A | B)$ если $a_i$ и $b_j$ независимы для любых $i$ и $j$?
55. Что можно сказать про $H(A | A)$?
56. Петя хочет пойти в кино с вероятностью ровно 1/3, а у него есть только честная монета. Может ли он осуществить свой замысел?
57. Решите предудыщее задание для любой дроби $0 \le p/q \le 1$.
58. Постройте схему получения вероятности 1/3 с помощью честной монеты, имеющую минимальное математическое ожидание числа бросков. Докажите оптимальность вашей схемы.
59. Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке $p$ ($p$ - целое) и каждую секунду переходит равновероятно на 1 влево или вправо. Точка поглощается в точках 0 и $n$ ($n$ целое, больше $p$). Найдите вероятность поглощения в точке 0.
60. Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке 0 и каждую секунду переходит равновероятно на 1 влево или вправо. Докажите, что математическое ожидание максимума координаты точки за $n$ шагов есть $O(\sqrt{n})$.
61. Дана марковская цепь с двумя состояниями и вероятностью перехода из 1 в 2 равной $a$, вероятностью перехода из 2 в 1 равной $b$. Найдите в явном виде $n$-ю степень матрицы переходов.
62. Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних двух бросков равны 0101. Вася выигрывает, когда результаты последних двух бросков равны 000. С какой вероятностью Петя выиграет?
63. Предложите решение предыдущей задачи для произвольных выигрышных строк Васи и Пети (за полином от суммы длин этих строк).
64. Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних двух бросков равны 001. Какую строку длины 3 оптмально выбрать Васе, чтобы его вероятность выигрыша была максимальна?
65. Предложите решение предыдущей задачи для произвольной выигрышной строки Пети (за полином от длины этой строки).
66. Пусть последовательно генерируется последовательность из 0 и 1 длины $n$. Каждый элемент последовательности определяется с помощью броска честной монеты. Определите, с какой вероятностью некоторый префикс этой последовательности представляет собой запись двоичного числа, которое делится на 3.
67. Пусть последовательно генерируется последовательность из 0 и 1 длины $n$. Каждый элемент последовательности определяется с помощью броска честной монеты. Предложите алгоритм определния, с какой вероятностью некоторый префикс этой последовательности представляет собой запись двоичного числа, которое делится на $p$ для заданного целого $p$.
68. Для симуляции распределения двумя исходами с вероятностями $p/q$ и $1-p/q$, где $p$ и $q$ целые, с помощью честной монеты можно использовать метод с делением отрезка [0-1], изложенный на лекции, а можно использовать поглощающую марковскую цепь "пьяницы на прямой" с $q+1$ вершиной. Проведите сравнительный анализ этих двух методов.
69. Докажите, что математическое ожидание числа экспериментов при симуляции одного распределения другим асимптотически пропорционально отношению энтропий распределений (считайте, что энтропия симулируемого распределения больше).
70. Постройте регулярную Марковскую цепь с двумя состояниями и эргодическим распределением $[a, 1-a]$ для заданного $a$.
71. Постройте регулярную Марковскую цепь с $n$ состояниями и заданным распределением.
72. В случае, если НОД длин циклов единственного эргодического класса не равен 1, соотвтствующая Марковская цепь будет периодической и эргодического распреления не будет. Тем не менее, что можно сказать про распределения в моменты с заданным остатком по модулю НОД длин циклов?
73. Завершите доказательство леммы из эргодической теоремы для регулярных цепей. Докажите, что если $P$ - матрица переходов, не содержащая нулей, то для любого вектора $u$ с максимальным элементом $M$ и минимальным элементом $m$ максимальный и минимальный элементы $Pu$ $M'$ и $m'$, соответственно, удовлетворяют условиям $m \le m'$, $M \ge M'$, $M'-m' \le (M - m)(1 - 2\varepsilon)$, где $\varepsilon$ - минимальный элемент $P$.
74. В этом и последующих заданиях необходимо подробно изложить алгоритм вычисления числа комбинаторных объектов с таким префиксом, чтобы можно было получить объект по номеру и номер по объекту. Получение объекта по номеру и номера по объекту для перестановок.
75. Получение объекта по номеру и номера по объекту для сочетаний.
76. Получение объекта по номеру и номера по объекту для размещений.
77. Получение объекта по номеру и номера по объекту для разбиений на слагаемые.
78. Получение объекта по номеру и номера по объекту для скобочных последовательностей с одним типом скобок.
79. Получение объекта по номеру и номера по объекту для скобочных последовательностей с двумя типами скобок.
80. Факториальная система счисления. Рассмотрим систему счисления, где бесконечно много цифр, в $i$-м разряде (нумерация разрядов с 1 от младшего к старшему) разрешается использовать цифры от 0 до $i$, вес $i$-го разряда $i!$. Докажите, что у каждого положительного числа ровно одно представление в факториальной системе счисления (с точностью до ведущих нулей). Предложите алгоритм перевода числа в факториальную систему счисления.
81. Как связана факториальная система счисления и нумерация перестановок?
82. Фибоначчиева система счисления. Рассмотрим систему счисления, где есть две цифры, 0 и 1. Пусть нумерация разрядов ведется с 0 от младшего к старшему, вес $i$-го разряда $F_i$, где $F_i$ - $i$-е число Фибоначчи ($F_0 = 1$, $F_1 = 1$). При этом запрещается исползовать две единицы в соседних разрядах, а также запрещается использовать 1 в разряде 1. Сколько представлений в Фибоначчиевой системе счисления у положительного числа $x$? Предложите алгоритм перевода числа в фибоначчиеву систему счисления.
83. Свяжите фибоначчиеву систему счисления с нумерацией каких-либо комбинаторных объектов.
84. Предложите алгоритм получения следующего по номеру в лексикографическом порядке разбиения множества $\{1, \ldots, n\}$ на множества. Множества в каждом разбиении упорядочиваются лексикографически по представлениям в виде возрастающего списка элеметов. Разбиения далее упорядочиваются лексикографически как списки множеств.
85. Предложите алгоритм получения следующего по номеру в лексикографическом порядке разбиения множества $\{1, \ldots, n\}$ на множества. Множества в каждом разбиении упорядочиваются лексикографически как битовые вектора. Разбиения далее упорядочиваются лексикографически как списки множеств.
86. Постройте конечный автомат для языка слов над бинарным алфавитом, в которых четность числа 0 равна четности числа 1
87. Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3
88. Постройте конечный автомат для языка слов над бинарным алфавитом, в которых нет трех нулей подряд
89. Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой двоичную запись чисел, кратных 5
90. Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей не кратно 3
91. Постройте конечный автомат для языка слов над бинарным алфавитом, в которых есть три нуля подряд. Сделайте вывод из последних двух заданий.
92. Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3 и которые представляют собой двоичную запись чисел кратных 5.
93. Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3 или которые представляют собой двоичную запись чисел кратных 5. Сделайте вывод из последних двух заданий.
94. Постройте конечный автомат для языка слов над бинарным алфавитом, в пятый символ с конца - 0. Можно построить недетерминированный автомат.
95. Постройте детерминированный автомат для предыдущего задания или докажите, что в нем слишком много состояний, чтобы его рисовать ;).
96. Постройте регулярное выражение для языка слов над бинарным алфавитом, в которых нет двух нулей подряд.
97. Постройте регулярное выражение для языка слов над бинарным алфавитом, в которых число 0 кратно 3.
98. Постройте конечный автомат для языка слов над бинарным алфавитом, в которых нет трех одинаковых символов подряд.
99. Постройте конечный автомат для языка слов над бинарным алфавитом, которые заканчиваются на 01001.
100. Постройте конечный автомат для языка слов над бинарным алфавитом, которые содержат подстроку 01001.
101. Постройте конечный автомат для языка слов, которые содержат заданную подстроку $s$.
102. Постройте недетерминированный автомат для языка слов над бинарным алфавитом, в которых $k$-й символ с конца равен 0, содержащий $O(k)$ состояний.
103. Докажите, что любой детерминированный автомат для языка слов над бинарным алфавитом, в которых $k$-й символ с конца равен 0, содержит $\Omega(2^k)$ состояний.
104. Можно ли обобщить два предыдущих задания для любого размера алфавита $c$ следующим образом: построить семейство языков, для которых будут существовать НКА, содержащий $O(k)$ состояний, но любые ДКА будут содержать $\Omega(c^k)$ состояний?
105. Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой развернутую двоичную запись чисел кратных 5 (сначала на вход подаются младшие разряды).
106. Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой развернутую двоичную запись чисел кратных 6 (сначала на вход подаются младшие разряды).
107. Рассмотрим язык $\{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 $. Докажите, что этот язык регулярный.
108. То же, что и предыдущее, только $\{x_{n-1} y_{n-1} z_{n-1} \dots x_1 y_1 z_1 x_0 y_0 z_0 \mid \dots \}$.
109. Петя строит автомат для конкатенации языков $L_1$ и $L_2$ из автоматов для этих языков. Оказалось, что автомат для $L_1$ содержит только одно терминальное состояние и Петя просто объединил в одно это состояние и начальное состояние автомата для $L_2$. Всегда ли у Пети получится то, что нужно?
110. Петя строит автомат для объединения языков $L_1$ и $L_2$ из автоматов для этих языков. Решив сэкономить, Петя просто объединил в одно начальные состояния автоматов для $L_1$ и $L_2$. Всегда ли у Пети получится то, что нужно?
111. Петя строит автомат для замыкания Клини языка $L$. Решив сэкономить, Петя просто провёл $\varepsilon$-переход из каждого терминального состояния в начальное состояние, и сделал начальное состояние также терминальным. Всегда ли у Пети получится то, что нужно?
112. Для символа $a$ обозначим как $La^{-1}$ множество слов $w$, таких что $wa \in L$. Докажите, что если $L$ регулярный, то $La^{-1}$ регулярный.
113. Для символа $a$ обозначим как $a^{-1}L$ множество слов $w$, таких что $aw \in L$. Докажите, что если $L$ регулярный, то $a^{-1}L$ регулярный.
114. Докажите или опровергните утверждения: (а) $Laa^{-1}=L$, (б) $La^{-1}a=L$, (в) $a^{-1}aL=L$, (г) $a^{-1}aL=L$.
115. Пусть $R$ и $S$ - регулярные языки. Выразите $(RS)a^{-1}$ через $R$, $S$, $Ra^{-1}$ и $Sa^{-1}$. Указание: рассмотрите два случая: $\varepsilon \in S$ или $\varepsilon \not\in S$.
116. Обозначим как $\min L$ множество слов $w \in L$, таких что никакой собственный префикс $w$ не является словом языка $L$. Докажите, что если $L$ регулярный, то и $\min L$ регулярный.
117. Обозначим как $\max L$ множество слов $w \in L$, таких что $w$ не является собственным префиксом никакого словом языка $L$. Докажите, что если $L$ регулярный, то и $\max L$ регулярный.
118. Обозначим как $\mbox{pref}\,L$ множество префиксов слов языка $L$. Докажите, что если $L$ регулярный, то и $\mbox{pref}\,L$ регулярный.
119. Обозначим как $\mbox{suf}\,L$ множество суффиксов слов языка $L$. Докажите, что если $L$ регулярный, то и $\mbox{suf}\,L$ регулярный.
120. Пусть $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)$ регулярный.
121. Пусть $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)$ регулярный.
122. Обозначим как $\mbox{cycle}\,L$ множество циклических сдвигов слов языка $L$. Докажите, что если $L$ регулярный, то и $\mbox{cycle}\,L$ регулярный.
123. Обозначим как $\mbox{half}\,L$ множество таких слов $a$, что существует слово $b$ такой же длины, как и $a$, что $ab \in L$. Докажите, что если $L$ регулярный, то и $\mbox{half}\,L$ регулярный.
124. Докажите нерегулярность языка, каждое слово которого содержит поровну 0 и 1.
125. Докажите нерегулярность языка палиндромов.
126. Докажите нерегулярность языка тандемных повторов.
127. Докажите нерегулярность языка $0^n1^m$, $n \le m$
128. Докажите нерегулярность языка $0^n1^m$, $n \ne m$
129. Докажите нерегулярность языка $0^{n^2}$
130. Докажите нерегулярность языка $0^p$, $p$ — простое
131. Докажите нерегулярность языка двоичных записей простых чисел
132. Докажите нерегулярность языка $0^n1^m$, $gcd(n, m) = 1$
133. Докажите нерегулярность языка $0^a1^b2^c$, $a \ne b$ и $b \ne c$
134. Приведите пример нерегулярного языка, для которого выполнена лемма о разрастании
135. Докажите, что если состояния $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n^2)$.
136. Докажите, что если состояния $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n)$.
137. Предложите алгоритм проверки того, что регулярный язык бесконечен
138. Предложите алгоритм подсчёта числа слов в регулярном языке (если язык бесконечен, алгоритм должен выдать информацию, что он бесконечен). Алгоритм должен работать за полином от числа состояний в автомате.
139. Предложите алгоритм проверки того, что регулярный язык является беспрефиксным
140. Предложите алгоритм проверки того, что один регулярный язык является подмножеством другого
141. Предложите алгоритм проверки того, что регулярные языки не пересекаются
142. Предложите алгоритм проверки того, что объединение двух заданных регулярных языков совпадет с некоторым третьим заданным.
143. Приведите пример регулярного языка и двух неизоморфных недетерминированных автоматов для него, которые при этом имеют минимальное число состояний среди всех недетерминированных автоматов для этого языка.
144. Рассмотрим язык $\{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$. Докажите, что этот язык не является регулярным.
145. Рассмотрим отношение на словах $L$: $x \equiv y$, если для любых $u$, $v$ выполнено $uxv \in L \Leftrightarrow uyv \in L$. Классы эквивалентности этого отношения называются синтаксическим моноидом языка $L$. Докажите, что $L$ регулярный тогда и только тогда, когда синтаксический моноид $L$ конечен.
146. Придумайте семейство регулярных языков $L_i$, у которых ДКА для $L_i$ содержит $O(i)$ состояний, а синтаксический моноид $L_i$ имеет неполиномиальный размер.
147. Постройте КС-грамматику для правильных скобочных последовательностей с двумя типами скобок.
148. Постройте КС-грамматику для языка $0^n1^n$.
149. Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей равно числу единиц. Докажите, что ваша грамматика является правильной.
150. Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей равно удвоенному числу единиц. Докажите, что ваша грамматика является правильной.
151. Постройте КС-грамматику для языка $0^k1^n2^{k+n}$.
152. Постройте КС-грамматику для языка $0^k1^n2^{k+n}\cup 1^k0^n2^{k+n}$. Сделайте вывод о свойствах КС-языков.
153. Постройте КС-грамматику для языка $0^k1^n2^{k+n}1^i0^j2^{i+j}$. Сделайте вывод о свойствах КС-языков.
154. Постройте КС-грамматику для языка $0^i1^j2^k$, $i \ne j$ или $j \ne k$.
155. Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются палиндромами.
156. Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются правильными скобочными последовательностями.
157. Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей не равно числу единиц.
158. Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются тандемными повторами.
159. Верно ли, что любую КС-грамматику можно привести к форме, когда любое правило имеет вид $A\to BCD$ или $A\to a$?
160. Верно ли, что любой КС-язык над односимвольным алфавитом является регулярным?
161. Докажите, что язык не является КС: $0^i1^j2^k$, $i<j<k$.
162. Докажите, что язык не является КС: $0^n1^n2^k$, $k<n$.
163. Докажите, что язык не является КС: $0^p$, $p$ простое.
164. Докажите, что язык двоичных записей простых чисел не является КС.
165. Докажите, что язык не является КС: $0^i1^j$, $j=i^2$.
166. Докажите, что язык не является КС: $0^n1^n2^k$, $n<k<2n$.
167. Докажите, что язык не является КС: $ww^Rw$, $w$ - строка из 0 и 1, $w^R$ - развернутая строка $w$.
168. Докажите, что язык $\{0^n1^m2^n3^m\}$ не является КС.
169. Докажите, что язык $\{0^n1^m2^n| n \ne m\}$ не является КС.
170. Приведите пример не КС-языка, для которого выполнена лемма о разрастании.
171. Постройте МП-автомат для языка $0^n1^n$.
172. Постройте МП-автомат для языка слов, где число нулей равно числу единиц.
173. Постройте МП-автомат для языка $0^n1^{2n}$.
174. Постройте МП-автомат для языка $0^n1^m2^{n+m}$.
175. Постройте МП-автомат для языка $0^{2n}1^n$.
176. Постройте МП-автомат для языка $0^n1^n\cup0^n1^{2n}$.
177. Постройте МП-автомат для языка слов $0^n1^m$, где $n \le m \le 2n$.
178. Докажите, что для любых $p$ и $q$ существует МП-автомат для языка слов $0^n1^m$, где $n/m=p/q$
179. Постройте автомат с магазинной памятью для языка слов над алфавитом $\{0, 1, 2\}$, которые содержат равное число двоек и равное число единиц, или равное число двоек и равное число нулей.

</wikitex>