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

1. Чему равна вероятность, что две случайно вытянутые кости домино можно приложить друг к другу по правилам домино?
2. Чему равна вероятность, что на двух брошенных честных игральных костях выпадут числа, одно из которых делит другое?
3. Чему равна вероятность, что если вытянуть из 52-карточной колоды две случайные карты, одной из них можно побить другую (одна из мастей назначена козырем, картой можно побить другую, если они одинаковой масти или если одна из них козырь)?
4. Чему равна вероятность, что на двадцати брошенных честных монетах выпадет поровну нулей и единиц?
5. Используя формулу Стирлинга $n!\approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$ оцените, чему равна вероятность, что на $2n$ брошенных честных монетах выпадет поровну нулей и единиц. Найдите асимптотическое поведение при $n \to \infty$
6. Петя и Вася три раза бросают по одной честной игровой кости. Вася два раза выкинул строго больше, чем Петя, а один раз строго меньше. При этом Петя в сумме выкинул строго больше, чем Вася. С какой вероятностью такое могло произойти?
7. Приведите пример трех событий, для которых $P(A \cap B \cap C) = P(A)P(B)P(C)$, но которые не являются независимыми, причем вероятности всех трех событий больше 0
8. Доказать или опровергнуть, что для независимых событий $A$ и $B$ и события $C$, где $P(C) > 0$ выполнено $P(A \cap B|C) = P(A|C)P(B|C)$
9. Доказать или опровергнуть, что для независимых событий $A$ и $B$ и события $C$, где $P(A) > 0$, $P(B) > 0$ выполнено $P(C|A \cap B) = P(C|A)P(C|B)$
10. Доказать или опровергнуть: если $P(A|B) = P(B|A)$, то $P(A) = P(B)$
11. Доказать или опровергнуть: если $P(A|B) = P(B|A)$, то $A$ и $B$ независимы
12. Доказать или опровергнуть: если $P(A|C) = P(B|C)$, то $P(C|A) = P(C|B)$
13. Выразите $P(A|B \cap C)$ через $P(A|B)$, $P(A|C)$, $P(B)$ и $P(C)$, либо обоснуйте, что это невозможно сделать.
14. Доказать или опровергнуть: если $A$ и $B$ независимы, то $\Omega \setminus A$ и $\Omega \setminus B$ независимы
15. Петя собирается смотреть серию матчей финала Флатландской хоккейной лиги. В финале две команды играют до 5 побед, ничьих не бывает, таким образом максимум в финале будет не более 9 матчей. Вася рассказал Пете, что всего в финале было 7 матчей. Петя считает матч интересным, если перед его просмотром он не знает, кто выиграет финал. Пусть все возможные последовательности исходов матчей, удовлетворяющих описанным условиями, равновероятны. Какова вероятность, что будет хотя бы 4 интересных матча?
16. Петя собирается смотреть серию матчей финала Флатландской хоккейной лиги. В финале две команды играют до 5 побед, ничьих не бывает, таким образом максимум в финале будет не более 9 матчей. Вася рассказал Пете, что всего в финале было 7 матчей. Петя считает матч зрелищным, если перед его просмотром он не знает, кто его выиграет. Пусть все возможные последовательности исходов матчей, удовлетворяющих описанным условиями, равновероятны. Какова вероятность, что будет хотя бы 5 зрелищных матчей?
17. Найдите распределение и математическое ожидание следующей случайной величины: число бросков нечестной монеты до первого выпадения 1.
18. Найдите распределение и математическое ожидание следующей случайной величины: число бросков честной монеты до второго выпадения 1.
19. Найдите математическое ожидание числа инверсий в перестановке чисел от 1 до $n$
20. Найдите математическое ожидание числа подъемов в перестановке чисел от 1 до $n$
21. Найдите математическое ожидание числа троек $i$, $j$, $k$, где $i < j < k$ и $a[i] < a[j] < a[k]$ в перестановке чисел от 1 до $n$
22. Предложите метод генерации случайной перестановки порядка $n$ с равновероятным распределением всех перестановок, если мы умеем генерировать равномерно распределенное целое число от 1 до $k$ для любых небольших $k$ ($k = O(n)$).
23. Дает ли следующий метод равномерную генерацию всех перестановок? "p = [1, 2, ..., n]; for i from 1 to n: swap(p[i], p[random(1..n)] )"
24. Дает ли следующий метод равномерную генерацию всех перестановок? "p = [1, 2, ..., n]; for i from 1 to n: swap(p[random(1..n)], p[random(1..n)] )"
25. Предложите метод генерации случайного сочетания из $n$ по $k$ с равновероятным распределением всех сочетаний, если мы умеем генерировать равномерно распределенное целое число от 1 до $t$ для любых небольших $t$ ($t = O(n)$)
26. Предложите метод генерации случайного сочетания из $n$ по $k$ с равновероятным распределением всех сочетаний, если мы умеем генерировать равномерно распределенное целое число от 1 до $t$ для любых небольших $t$ ($t = O(n)$), использующий $O(k)$ времени и памяти.
27. Верно ли, что если $\xi$ и $\eta$ - независимые случайные величины, то таким будут и $f(\xi)$ и $g(\eta)$ для любых функций $f$ и $g$? Достаточно доказать для конечных вероятностных пространств.
28. Постройте случайную величину, имеющую конечное математическое ожидание и бесконечную дисперсию.
29. Постройте случайную величину, имеющую бесконечное математическое ожидание и конечную дисперсию.
30. Рассмотрим игру. Колода из 52 карт, 26 красных и 26 черных, тасуется, так что все порядки следования карт оказываются равновероятными. Затем карты извлекаются по одной и колоды в открытую до того момента, пока не игрок не скажет "стоп". После этого открывается еще одна карта, если она красная, то игрок выигрывает. Какая стратегия максимизирует вероятность выигрыша игрока?
31. 10 шаров раскладываются по 5 корзинам. Для каждого шара равновероятно выбирается, в какую корзину он помещается. Какое математическое ожидание числа пустых корзин?
32. 10 шаров раскладываются по 5 корзинам. Для каждого шара равновероятно выбирается, в какую корзину он помещается. Какое математическое ожидание числа корзин, содержащих ровно один шар?
33. Докажите, что минимум $E(X-\alpha)^2$ достигается при $\alpha = EX$.
34. Улучшить неравенство Маркова в общем случае нельзя. Докажите, что для любого $c > 1$ найдется такая неотрицательная случайная величина $\xi$, что $P(\xi \ge cE\xi) = 1/c$.
35. Можно ли подобрать такую неотрицательную случайную величину $\xi$, чтобы для двух различных $c_1 > 1$ и $c_2 > 1$ выполнялось $P(\xi \ge c_iE\xi) = 1/c_i$ ($i \in \{1, 2\}$)?
36. Для какого максимального $\alpha$ можно подобрать такую неотрицательную случайную величину $\xi$, чтобы для двух различных $c_1 > 1$ и $c_2 > 1$ выполнялось $P(\xi \ge c_iE\xi) = \alpha/c_i$ ($i \in \{1, 2\}$)?
37. Улучшить неравенство Чебышева в общем случае нельзя. Докажите, что для любого $c > 0$ найдется такая случайная величина $\xi$, что $P(|\xi - E\xi| \ge c) = D\xi/c^2$.
38. Улучшить неравенство Чебышева нельзя даже для суммы. Докажите, что для любого $c > 0$ найдется такое семейство одинаково распределенных случайных величин $\xi_1, \xi_2, \ldots, \xi_n$, что $P(|\sum\xi_i - \sum E\xi_i| \ge c) = nD\xi/c^2$.
39. Оцените вероятность, что значение на игральной кости отличается от матожидания больше чем на 2 с помощью неравенства Чебышева. Насколько точна эта оценка?
40. Докажите, что вероятность того, что значения на двух одинаково распределенных нечестных игральных костях совпадает, не меньше $1/6$.
41. Найдите дисперсию следующей случайной величины: число бросков честной монеты до $k$-го выпадения 1.
42. Петя хочет пойти в кино с вероятностью ровно 1/3, а у него есть только честная монета. Может ли он осуществить свой замысел?
43. Петя хочет пойти в кино с вероятностью ровно 1/13, а у него есть только честная монета. Может ли он осуществить свой замысел?
44. Решите предудыщее задание для любой дроби $0 \le p/q \le 1$.
45. Постройте схему получения вероятности 1/3 с помощью честной монеты, имеющую минимальное математическое ожидание числа бросков. Докажите оптимальность вашей схемы.
46. Дана нечестная монета. Придумайте метод определения, какое значение выпадает с большей вероятностью. Вероятность того, что этот способ ошибся, должна быть не больше $0.01$. Оцените количество бросков, которое потребуется, в зависимости от того, насколько $p$ отличается от $1/2$.
47. Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних двух бросков равны 11. Вася выигрывает, когда результаты последних двух бросков равны 00. С какой вероятностью Петя выиграет?
48. Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних трех бросков равны 001. Вася выигрывает, когда результаты последних трех бросков равны 010. С какой вероятностью Петя выиграет?
49. Можно ли сделать игру в предыдущем задании честной (чтобы вероятности выигрышей оказались равны $1/2$), используя нечестную монету?
50. Сколько байт в бите? Можно ли ответить на этот вопрос с точки зрения теории информации? Какое определение нужно дать для байта в этом случае?
51. Сравните количество информации в одном броске честной монеты и одном броске честной игральной кости.
52. Докажите, что для монеты энтропия максимальна в случае честной монеты
53. Докажите, что для $n$ исходов энтропия максимальна если они все равновероятны
54. Найдите энтропию для геометрического распределения с $p = 1/2$ (счетное число исходов, $i$-й исход происходит с вероятностью $1/2^i$).
55. Найдите энтропию для геометрического распределения с произвольным $p$ (счетное число исходов, $i$-й исход происходит с вероятностью $(1-p)p^i$).
56. Пусть заданы полные системы событий $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)$
57. Что можно сказать про $H(A | B)$ если $a_i$ и $b_j$ независимы для любых $i$ и $j$?
58. Что можно сказать про $H(A | A)$?
59. Зафиксируем любой язык программирования. Колмогоровской сложностью слова $x$ называется величина $K(x)$ - минимальная длина программы на зафиксированном языке программирования, которая на пустом входе выводит $x$. Обозначим длину слова $x$ как $|x|$. Докажите, что $K(x) \le |x| + c$ для некоторой константы $c$.
60. Предложите семейство слов $x_1, x_2, \ldots, x_n, \ldots$, где $|x_i|$ строго возрастает и выполнено $K(x_i) = o(|x_i|)$.
61. Предложите семейство слов $x_1, x_2, \ldots, x_n, \ldots$, где $|x_i|$ строго возрастает и выполнено $K(x_i) = o(\log_2 |x_i|)$.
62. Колмогоровская сложность и энтропия Шеннона. Для слова $x$, в котором $i$-й символ алфавита встречается $f_i$ раз обозначим как $H(x)$ величину, равную энтропии случайного источника с распределением $p_i = f_i/|x|$. Докажите, что $K(x) \le nH(x) + O(\log n)$.
63. Докажите, что для любого $c > 0$ найдется слово, для которого $K(x) < c n H(x)$
64. Симуляция дискретного распределения непрерывным. Рассмотрим источник, который возвращает равномерно распределенное вещественное число от 0 до 1 (для решения этой задачи достаточно формального определения, что для любого отрезка вероятность попадания значения в этот отрезок пропорциональна его длине). Мы хотим просимулировать дискретное равновероятное распределение с $n$ исходами. Как это сделать за $O(1)$? Будем считать, что тип данных double имеет достаточно точности и что операции со значениями типа double выполняются за $O(1)$.
65. Пусть теперь мы хотим просимулировать с помощью непрерывного равномерного распределения дискретное распределение с распределением вероятностей $[p_1, \ldots, p_n]$. Как это сделать за $O(\log n)$? Разрешается провести предподготовку за $O(n)$.
66. Схема Уолкера. Требуется просимулировать с помощью непрерывного равномерного распределения дискретное распределение с распределением вероятностей $[p_1, \ldots, p_n]$. Как это сделать за $O(1)$? Разрешается провести предподготовку за $O(n)$.
67. Будем генерировать бесконечную последовательность из 0 и 1 с помощью бросков честной монеты. Найдите матожидание числа бросков до выпадения трех нулей подряд.
68. Будем генерировать бесконечную последовательность из 0 и 1 с помощью бросков честной монеты. Найдите матожидание числа бросков до первого вхождения 011.
69. Будем генерировать бесконечную последовательность из 0 и 1 с помощью бросков честной монеты. Найдите матожидание числа бросков до первого вхождения 010.
70. Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке $p$ ($p$ - целое) и каждую секунду переходит равновероятно на 1 влево или вправо. Точка поглощается в точках 0 и $n$ ($n$ целое, больше $p$). Найдите вероятность поглощения в точке 0.
71. Дана марковская цепь с двумя состояниями и вероятностью перехода из 1 в 2 равной $a$, вероятностью перехода из 2 в 1 равной $b$. Найдите в явном виде $n$-ю степень матрицы переходов.
72. Для заданной рациональной дроби $p/q$ постройте марковскую цепь, все переходы которой имеют вероятность $1/2$, которая имеет поглощающее состояние с вероятностью поглощения $p/q$.
73. Для заданной рациональной дроби $p/q$ постройте марковскую цепь, все переходы которой имеют вероятность $1/3$, которая имеет поглощающее состояние с вероятностью поглощения $p/q$.
74. Для заданной рациональной дроби $p/q$ и целого $n$ постройте марковскую цепь, все переходы которой имеют вероятность $1/n$, которая имеет поглощающее состояние с вероятностью поглощения $p/q$.
75. Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке 0 и каждую секунду переходит равновероятно на 1 влево или вправо. Чему равно математическое ожидание координаты точки после $n$ шагов?
76. Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке 0 и каждую секунду переходит равновероятно на 1 влево или вправо. Докажите, что математическое ожидание модуля координаты точки за $n$ шагов есть $O(\sqrt{n})$.
77. Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке 0 и каждую секунду переходит равновероятно на 1 влево или вправо. Докажите, что математическое ожидание максимума координаты точки за $n$ шагов есть $O(\sqrt{n})$.
78. Предложите алгоритм решения задачи 48 для произвольных выигрышных строк Васи и Пети (работающий за полином от суммы длин этих строк).
79. Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних трех бросков равны 001. Какую строку длины 3 оптимально выбрать Васе, чтобы его вероятность выигрыша была максимальна?
80. Предложите решение предыдущей задачи для произвольной выигрышной строки Пети (за полином от длины этой строки).
81. Будем генерировать последовательность из 0 и 1 длины $n$ с помощью бросков честной монеты. Определите, с какой вероятностью некоторый префикс этой последовательности представляет собой запись двоичного числа, которое делится на 3.
82. Будем генерировать последовательность из 0 и 1 длины $n$ с помощью бросков честной монеты. Предложите алгоритм определения, с какой вероятностью некоторый префикс этой последовательности представляет собой запись двоичного числа, которое делится на $p$ для заданного целого $p$.
83. В Киндер-сюрпризах бывает $n$ различных игрушек. Вы покупаете по одному Киндер-сюрпризу со случайной игрушкой (может содержать игрушку, уже попадавшуюся ранее), пока не получите каждую из $n$ игрушек. Опишите процесс с помощью цепи Маркова. Посчитайте и оцените асимптотически матожидание количества купленных Киндер-сюрпризов.
84. Посчитайте и оцените дисперсию для предыдущего задания.
85. Пусть $L$ - формальный язык. Докажите, что $(L^*)^* = L^*$
86. Пусть $R$ и $S$ - языки. Докажите или опровергните, что $(R \cup S)^* = R^* \cup S^*$.
87. Пусть $R$ и $S$ - языки. Докажите или опровергните, что $(R \cap S)^* = R^* \cap S^*$.
88. Пусть $R$ и $S$ - языки. Докажите или опровергните, что $(R \cup S)^* = (R^*S^*)^*$.
89. Пусть $R$ и $S$ - языки. Обозначим как $RS$ язык слов, представимых в виде конкатенации слова из $R$ и слова из $S$ (в этом порядке). Докажите или опровергните, что $(R\cup S)T=RT \cup ST$, $(R\cap S)T=RT \cap ST$.
90. Пусть $L$ - язык. Обозначим как $Lc$ язык, который получается из $L$ дописыванием в конец каждому слову символа $c$. Обозначим как $Lc^{-1}$ язык, который получается из $L$ откидыванием всех слов, которые не заканчиваются на $c$, а затем у оставшихся слов откидыванием конечного символа $c$. Докажите или опровергните, что $(Lc)c^{-1}=L$, $(Lc^{-1})c=L$.
91. Постройте конечный автомат для языка слов над бинарным алфавитом, в которых четность числа 0 равна четности числа 1
92. Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3
93. Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей не кратно 3. Сделайте вывод из последних двух заданий.
94. Постройте конечный автомат для языка слов над бинарным алфавитом, в которых нет трех нулей подряд
95. Постройте конечный автомат для языка слов над бинарным алфавитом, в которых есть три нуля подряд
96. Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой двоичную запись чисел, кратных 5
97. Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3 и которые представляют собой двоичную запись чисел кратных 5.
98. Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3 или которые представляют собой двоичную запись чисел кратных 5. Сделайте вывод из последних двух заданий.
99. Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число единиц кратно 3. Сделайте вывод.
100. Постройте детерминированный конечный автомат для языка слов над бинарным алфавитом, в которых второй символ с конца равен последнему символу.
101. Запишите регулярное выражения для слов над бинарным алфавитом, содержащих два нуля подряд.
102. Запишите регулярное выражения для слов над бинарным алфавитом, содержащих не более одного места, где встречаются два нуля подряд.
103. Запишите регулярное выражения для слов над бинарным алфавитом, не содержащих два нуля подряд.
104. Запишите регулярное выражения для слов над алфавитом $\{a, b, c\}$, содержащих нечетное число букв $a$.
105. Запишите регулярное выражения для слов над бинарным алфавитом, задающих целое число в двоичной системе, не меньшее 8.
106. Запишите регулярное выражения для слов над бинарным алфавитом, задающих целое число в двоичной системе, не меньшее 51.
107. Запишите регулярное выражения для слов над алфавитом $\{a, b, c\}$, содержащих хотя бы одну букву $a$ и хотя бы одну букву $b$.
108. Запишите регулярное выражения для слов над алфавитом $\{a, b, c\}$, содержащих хотя бы две буквы $a$ и хотя бы одну букву $b$.
109. Запишите регулярное выражения для слов над бинарным алфавитом, которые представляют собой двоичную запись числа, кратного трем.
110. Постройте детерминированный конечный автомат для языка слов над бинарным алфавитом, в которых пятый символ с конца - единица.
111. Докажите, что любой детерминированный автомат для языка слов над бинарным алфавитом, в которых $k$-й символ с конца равен 0, содержит $\Omega(2^k)$ состояний.
112. Можно ли обобщить два предыдущих задания для любого размера алфавита $c$ следующим образом: построить семейство языков, для которых будут существовать НКА, содержащий $O(k)$ состояний, но любые ДКА будут содержать $\Omega(c^k)$ состояний?
113. Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой развернутую двоичную запись чисел кратных 5 (сначала на вход подаются младшие разряды).
114. Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой развернутую двоичную запись чисел кратных 6 (сначала на вход подаются младшие разряды).
115. Предложите для заданного ДКА размера $n$ алгоритм подсчета количества слов длины $d$ которые он допускает, за $O(dn)$.
116. Предложите для заданного ДКА размера $n$ алгоритм подсчета количества слов длины $d$ которые он допускает, за $O(\log{(d)} \cdot poly(n))$ для некоторого полинома $poly$.
117. Предложите для заданного ДКА размера $n$ алгоритм подсчета количества слов длины не больше $d$ которые он допускает, за $O(\log{(d)} \cdot poly(n))$ для некоторого полинома $poly$.
118. Петя строит автомат для конкатенации языков $L_1$ и $L_2$ из автоматов для этих языков. Оказалось, что автомат для $L_1$ содержит только одно терминальное состояние и Петя просто объединил в одно это состояние и начальное состояние автомата для $L_2$. Всегда ли у Пети получится то, что нужно?
119. Петя строит автомат для объединения языков $L_1$ и $L_2$ из автоматов для этих языков. Решив сэкономить, Петя просто объединил в одно начальные состояния автоматов для $L_1$ и $L_2$. Всегда ли у Пети получится то, что нужно?
120. Петя строит автомат для замыкания Клини языка $L$. Решив сэкономить, Петя просто провёл $\varepsilon$-переход из каждого терминального состояния в начальное состояние, и сделал начальное состояние также терминальным. Всегда ли у Пети получится то, что нужно?
121. Докажите нерегулярность языка палиндромов, если алфавит содержит хотя бы два символа. Что если алфавит унарный?
122. Докажите нерегулярность языка тандемных повторов $L = \{ ww | w \in \Sigma^* \}$, если алфавит содержит хотя бы два символа. Что если алфавит унарный?
123. Докажите нерегулярность языка $0^n1^m$, $n \le m$
124. Докажите нерегулярность языка $0^n1^m$, $n \ne m$
125. Докажите нерегулярность языка $0^{n^2}$
126. Докажите нерегулярность языка $0^p$, $p$ — простое
127. Докажите нерегулярность языка двоичных записей простых чисел
128. Докажите нерегулярность языка $0^n1^m$, $gcd(n, m) = 1$
129. Приведите пример нерегулярного языка, для которого выполнена лемма о разрастании
130. Обозначим как $\min L$ множество слов $w \in L$, таких что никакой собственный префикс $w$ не является словом языка $L$. Докажите, что если $L$ регулярный, то и $\min L$ регулярный.
131. Обозначим как $\max L$ множество слов $w \in L$, таких что $w$ не является собственным префиксом никакого словом языка $L$. Докажите, что если $L$ регулярный, то и $\max L$ регулярный.
132. Обозначим как $\mbox{pref}\,L$ множество префиксов слов языка $L$. Докажите, что если $L$ регулярный, то и $\mbox{pref}\,L$ регулярный.
133. Обозначим как $\mbox{suf}\,L$ множество суффиксов слов языка $L$. Докажите, что если $L$ регулярный, то и $\mbox{suf}\,L$ регулярный.
134. Пусть $a$ и $b$ - слова равной длины $n$. Обозначим как $\mbox{alt}(a, b)$ слово $a_1b_1a_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)$ регулярный.
135. Пусть $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)$ регулярный.
136. Обозначим как $\mbox{cycle}\,L$ множество циклических сдвигов слов языка $L$. Докажите, что если $L$ регулярный, то и $\mbox{cycle}\,L$ регулярный.
137. Обозначим как $\mbox{half}\,L$ множество таких слов $a$, что существует слово $b$ такой же длины, как и $a$, что $ab \in L$. Докажите, что если $L$ регулярный, то и $\mbox{half}\,L$ регулярный.
138. Рассмотрим язык $\{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 $. Докажите, что этот язык регулярный.
139. То же, что и предыдущее, только $\{x_{n-1} y_{n-1} z_{n-1} \dots x_1 y_1 z_1 x_0 y_0 z_0 \mid \dots \}$.
140. Рассмотрим язык $\{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$. Докажите, что этот язык не является регулярным.
141. Из алгоритма построения множества различимых состояний следует, что $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n^2)$. Докажите, что если состояния $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n)$.
142. Постройте КС-грамматику для правильных скобочных последовательностей с двумя типами скобок. В этом и следующих заданиях, после разработки КС грамматики необходимо выбрать в качестве примера слово и продемонстрировать его левосторонний вывод и дерево разбора.
143. Постройте КС-грамматику для языка $0^n1^n$.
144. Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей равно числу единиц. Докажите, что ваша грамматика является правильной.
145. Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей равно удвоенному числу единиц. Докажите, что ваша грамматика является правильной.
146. Постройте КС-грамматику для языка $0^k1^n2^{k+n}$.
147. Постройте КС-грамматику для языка $0^k1^n2^{k+n}\cup 1^k0^n2^{k+n}$. Сделайте вывод про КС языки.
148. Постройте КС-грамматику для языка $0^k1^n2^{k+n}1^i0^j2^{i+j}$. Сделайте вывод про КС языки.
149. Пусть задана КС-грамматика для языка $L$. Укажите, как построить КС-грамматику для языка $L^*$.
150. Пусть задана КС-грамматика для языка $L$. Обозначим как $L^R$ язык, составленный из слов, которые, если их прочитать от конца к началу, принадлежат языку $L$. Укажите, как построить КС-грамматику для языка $L^R$.
151. Постройте КС-грамматику для языка $0^i1^j2^k$, $i \ne j$ или $j \ne k$.
152. Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются палиндромами.
153. Постройте КС-грамматику для языка слов над алфавитом $\{(, )\}$, которые не являются правильными скобочными последовательностями.
154. Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей не равно числу единиц.
155. Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются тандемными повторами (не имеют вид $xx$ для некоторого слова $x$).
156. Постройте КС-грамматику, описывающие академические регулярные выражения над алфавитом $\{0, 1\}$.
157. КС грамматика называется линейной, если в правых частях правил встречается максимум один нетерминал. Праволинейные грамматики, в которых этот нетерминал находится на последнем месте, порождают регулярные языки. Приведите пример линейной грамматики, которая порождает нерегулярный язык.
158. КС грамматика называется леволинейной, если в правых частях правил встречается максимум один нетерминал, причем если он есть, то находится на первом месте. Докажите, что язык можно породить леволинейной грамматикой тогда и только тогда, когда он регулярный.
159. КС грамматика называется смешанной линейной, если в правых частях правил встречается максимум один нетерминал, причем если он есть, то находится либо на первом, либо на последнем месте. Докажите, что существует КС язык, не являющийся регулярным, который можно породить смешанной линейной грамматикой.
160. Постройте КС-грамматику для описаний КС грамматик.
161. Верно ли, что любую КС-грамматику можно привести к форме, когда любое правило имеет вид $A\to BCD$ или $A\to a$?
162. Приведите пример КС-языка, не являющегося регулярным, дополнение к которому также является КС.
163. Приведите пример двух КС-языков, не являющихся регулярными, пересечение которых также является КС, но не регулярным, причем отлично от обоих пересекаемых языков.
164. Предложите алгоритм проверки, что в грамматике выводится хотя бы одно слово.
165. Предложите алгоритм нахождения слова минимальной длины, выводящегося в заданной грамматике.
166. Грамматика называется леворекурсивной, если найдется такой нетерминал A, что за один или более шаг из A можно вывести строку, которая начинается с A ($A \Rightarrow^+ A\alpha$). Предложите алгоритм, который проверяет, является ли грамматика леворекурсивной.
167. Предложите алгоритм проверки, что в заданная КС грамматика в НФХ порождает конечное число слов.
168. Предложите алгоритм, который получает на вход КС грамматику в НФХ, про которую с помощью алгоритма из предыдущего задания выяснили, что она порождает конечное число слов. На выход необходимо выдать самое длинное слово, которое порождается этой КСГ.
169. Билл поменял местами шаги алгоритма приведения КСГ к НФХ: он сначала удаляет цепные правила, а затем eps-правила. Будет ли корректно работать алгоритм?
170. Билл поменял местами шаги алгоритма приведения КСГ к НФХ: он сначала удаляет eps-правила, а затем длинные правые части. Можно ли поправить алгоритм удаления eps-правил, чтобы он работал с длинными правыми частями? Чем эта версия алгоритма хуже оригинальной?
171. Алиса разработала свою нормальную форму грамматики, в которой каждое правило имеет вид $A \to BCD$, $A \to BC$ или $A \to c$. Как обобщить алгоритм КЯК на грамматики в такой форме? Сравните получившийся алгоритм с оригинальным.
172. Алиса разработала свою нормальную форму грамматики, в которой каждое правило имеет вид $A \to BC$, $A \to B$ или $A \to c$. Как обобщить алгоритм КЯК на грамматики в такой форме? Сравните получившийся алгоритм с оригинальным.
173. Рассмотрим дерево разбора некоторого слова в грамматике в НФХ. Как соотносятся количество нетерминалов и терминалов в дереве?
174. Докажите, что язык не является КС: $0^i1^j2^k$, $i<j<k$.
175. Докажите, что язык не является КС: $0^n1^n2^k$, $k<n$.
176. Докажите, что язык не является КС: $0^p$, $p$ простое.
177. Докажите, что язык двоичных записей простых чисел не является КС.
178. Докажите, что язык не является КС: $0^i1^j$, $j=i^2$.
179. Докажите, что язык не является КС: $0^n1^n2^k$, $n<k<2n$.
180. Докажите, что язык не является КС: $ww^Rw$, $w$ - строка из 0 и 1, $w^R$ - развернутая строка $w$.
181. Докажите, что язык $\{0^n1^m2^n3^m\}$ не является КС.
182. Докажите, что язык $\{0^n1^m2^n| n \ne m\}$ не является КС.
183. Верно ли, что любой КС-язык над односимвольным алфавитом является регулярным?
184. Рассмотрим несколько неправильных модификаций леммы о разрастании для КС-языков. Для каждой модификации придумайте КС-язык, который не удовлетворяет этой лемме. Для КС-языка $L$ существует число $n$, что любое слово $w \in L$, $|w| \ge n$ можно разбить на четыре части $w = uvyz$, где $|vy| \le n$, $vy \neq \varepsilon$ что для любого $k \ge 0$, $uv^ky^kz \in L$.
185. Для КС-языка $L$ существует число $n$, что любое слово $w \in L$, $|w| \ge n$ можно разбить на четыре части $w = vxyz$, где $|vxy| \le n$, $vy \neq \varepsilon$, что для любого $k \ge 0$, $v^kxy^kz \in L$.
186. Докажите, что следующая модификация леммы о разрастании верна: Для КС-языка $L$ существует число $n$, что любое слово $w \in L$, $|w| \ge n$ можно разбить на пять частей $w = uvxyz$, где $|vxy| \le n$, $v \neq \varepsilon$, $y \neq \varepsilon$ что для любого $k \ge 0$, $uv^kxy^kz \in L$.
187. Постройте МП-автомат для языка слов, где число нулей равно числу единиц.
188. Постройте МП-автомат для языка $0^n1^{2n}$.
189. Постройте МП-автомат для языка $0^n1^m2^{n+m}$.
190. Постройте МП-автомат для языка $0^{2n}1^n$.
191. Постройте МП-автомат для языка $0^n1^n\cup0^n1^{2n}$.
192. Постройте МП-автомат для языка слов $0^n1^m$, где $n \le m \le 2n$.
193. Докажите, что для любых $p$ и $q$ существует МП-автомат для языка слов $0^n1^m$, где $n/m=p/q$
194. Постройте автомат с магазинной памятью для языка слов над алфавитом $\{0, 1, 2\}$, которые содержат равное число двоек и равное число единиц, или равное число двоек и равное число нулей.
195. Рассмотрим список слов $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$ является контекстно-свободным.
196. Докажите, что дополнение к языку списка $L_A$ является контекстно-свободным для любого списка $A$.
197. Можно неправильно определить язык списка $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$.
198. Предложите алгоритм проверки, что МП-автомат допускает заданное слово.
199. Назовем состояние МП-автомата бесполезным, если автомат не может перейти в него ни при каком входном слове. Предложите алгоритм проверки состояния МП-автомата на бесполезность.
200. Предложите алгоритм проверки, что МП-автомат допускает хотя бы одно слово, содержащее заданное в качестве подстроки.
201. Предложите алгоритм проверки, что МП-автомат допускает бесконечное число слов.
202. Пусть $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)$ также КС.
203. Пусть $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)$ также КС.