Список заданий по ДМ 2021 весна - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:22:14Z

rollbackEdits.php mass rollback

194.26.192.187 в 05:22, 1 сентября 2022

2022-09-01T05:22:52Z

95.161.221.171 в 20:17, 26 мая 2021

2021-05-26T20:17:53Z

77.234.215.133 в 16:45, 19 мая 2021

2021-05-19T16:45:07Z

95.161.222.118 в 13:19, 13 мая 2021

2021-05-13T13:19:33Z

188.170.214.41 в 15:00, 7 мая 2021

2021-05-07T15:00:22Z

77.234.215.133 в 14:53, 22 апреля 2021

2021-04-22T14:53:06Z

77.234.215.133 в 15:40, 14 апреля 2021

2021-04-14T15:40:39Z

77.234.215.133 в 17:03, 31 марта 2021

2021-03-31T17:03:12Z

77.234.215.133 в 18:09, 26 марта 2021

2021-03-26T18:09:54Z

← Предыдущая		Версия 16:22, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	# Чему равна вероятность, что две случайно вытянутые кости домино можно приложить друг к другу по правилам домино?		# Чему равна вероятность, что две случайно вытянутые кости домино можно приложить друг к другу по правилам домино?
	# Чему равна вероятность, что на двух брошенных честных игральных костях выпадут числа, одно из которых делит другое?		# Чему равна вероятность, что на двух брошенных честных игральных костях выпадут числа, одно из которых делит другое?

← Предыдущая		Версия 05:22, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	# Чему равна вероятность, что две случайно вытянутые кости домино можно приложить друг к другу по правилам домино?		# Чему равна вероятность, что две случайно вытянутые кости домино можно приложить друг к другу по правилам домино?
	# Чему равна вероятность, что на двух брошенных честных игральных костях выпадут числа, одно из которых делит другое?		# Чему равна вероятность, что на двух брошенных честных игральных костях выпадут числа, одно из которых делит другое?

← Предыдущая		Версия 20:17, 26 мая 2021
Строка 213:		Строка 213:
	# Алиса разработала свою нормальную форму грамматики, в которой каждое правило имеет вид $A \to BC$, $A \to B$ или $A \to c$. Как обобщить алгоритм КЯК на грамматики в такой форме? Сравните получившийся алгоритм с оригинальным.		# Алиса разработала свою нормальную форму грамматики, в которой каждое правило имеет вид $A \to BC$, $A \to B$ или $A \to c$. Как обобщить алгоритм КЯК на грамматики в такой форме? Сравните получившийся алгоритм с оригинальным.
	# Рассмотрим дерево разбора некоторого слова в грамматике в НФХ. Как соотносятся количество нетерминалов и терминалов в дереве?		# Рассмотрим дерево разбора некоторого слова в грамматике в НФХ. Как соотносятся количество нетерминалов и терминалов в дереве?
		+	# Докажите, что язык не является КС: $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\}$ не является КС.
		+	# Верно ли, что любой КС-язык над односимвольным алфавитом является регулярным?
		+	# Приведите пример КС-языка, не являющегося регулярным, дополнение к которому также является КС.
		+	# Приведите пример двух КС-языков, не являющихся регулярными, пересечение которых также является КС, но не регулярным, причем отлично от обоих пересекаемых языков.
		+	# Рассмотрим несколько неправильных модификаций леммы о разрастании для КС-языков. Для каждой модификации придумайте КС-язык, который не удовлетворяет этой лемме. Для КС-языка $L$ существует число $n$, что любое слово $w \in L$, $\|w\| \ge n$ можно разбить на четыре части $w = uvyz$, где $\|vy\| \le n$, $vy \neq \varepsilon$ что для любого $k \ge 0$, $uv^ky^kz \in L$.
		+	# Для КС-языка $L$ существует число $n$, что любое слово $w \in L$, $\|w\| \ge n$ можно разбить на четыре части $w = vxyz$, где $\|vxy\| \le n$, $vy \neq \varepsilon$, что для любого $k \ge 0$, $v^kxy^kz \in L$.
		+	# Докажите, что следующая модификация леммы о разрастании верна: Для КС-языка $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$.
		+	# Пусть $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)$ также КС.

← Предыдущая		Версия 16:45, 19 мая 2021
Строка 195:		Строка 195:
	# КС грамматика называется леволинейной, если в правых частях правил встречается максимум один нетерминал, причем если он есть, то находится на первом месте. Докажите, что язык можно породить леволинейной грамматикой тогда и только тогда, когда он регулярный.		# КС грамматика называется леволинейной, если в правых частях правил встречается максимум один нетерминал, причем если он есть, то находится на первом месте. Докажите, что язык можно породить леволинейной грамматикой тогда и только тогда, когда он регулярный.
	# КС грамматика называется смешанной линейной, если в правых частях правил встречается максимум один нетерминал, причем если он есть, то находится либо на первом, либо на последнем месте. Докажите, что существует КС язык, не являющийся регулярным, который можно породить смешанной линейной грамматикой.		# КС грамматика называется смешанной линейной, если в правых частях правил встречается максимум один нетерминал, причем если он есть, то находится либо на первом, либо на последнем месте. Докажите, что существует КС язык, не являющийся регулярным, который можно породить смешанной линейной грамматикой.
		+	# Постройте МП-автомат для языка слов, где число нулей равно числу единиц.
		+	# Постройте МП-автомат для языка $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$.
		+	# Постройте автомат с магазинной памятью для языка слов над алфавитом $\{0, 1, 2\}$, которые содержат равное число двоек и равное число единиц, или равное число двоек и равное число нулей.
		+	# Верно ли, что любую КС-грамматику можно привести к форме, когда любое правило имеет вид $A\to BCD$ или $A\to a$?
		+	# Предложите алгоритм проверки, что в грамматике выводится хотя бы одно слово.
		+	# Предложите алгоритм нахождения слова минимальной длины, выводящегося в заданной грамматике.
		+	# Грамматика называется леворекурсивной, если найдется такой нетерминал A, что за один или более шаг из A можно вывести строку, которая начинается с A ($A \Rightarrow^+ A\alpha$). Предложите алгоритм, который проверяет, является ли грамматика леворекурсивной.
		+	# Предложите алгоритм проверки, что в заданная КС грамматика в НФХ порождает конечное число слов.
		+	# Предложите алгоритм, который, получает на вход КС грамматику в НФХ, про которую с помощью алгоритма из предыдущего задания выяснили, что она порождает конечное число слов. На выход необходимо выдать самое длинное слово, которое порождается этой КСГ.
		+	# Билл поменял местами шаги алгоритма приведения КСГ к НФХ: он сначала удаляет цепные правила, а затем eps-правила. Будет ли корректно работать алгоритм?
		+	# Билл поменял местами шаги алгоритма приведения КСГ к НФХ: он сначала удаляет eps-правила, а затем длинные правые части. Можно ли поправить алгоритм удаления eps-правил, чтобы он работал с длинными правыми частями? Чем эта версия алгоритма хуже оригинальной?
		+	# Алиса разработала свою нормальную форму грамматики, в которой каждое правило имеет вид $A \to BCD$, $A \to BC$ или $A \to c$. Как обобщить алгоритм КЯК на грамматики в такой форме? Сравните получившийся алгоритм с оригинальным.
		+	# Алиса разработала свою нормальную форму грамматики, в которой каждое правило имеет вид $A \to BC$, $A \to B$ или $A \to c$. Как обобщить алгоритм КЯК на грамматики в такой форме? Сравните получившийся алгоритм с оригинальным.
		+	# Рассмотрим дерево разбора некоторого слова в грамматике в НФХ. Как соотносятся количество нетерминалов и терминалов в дереве?

← Предыдущая		Версия 13:19, 13 мая 2021
Строка 178:		Строка 178:
	# Придумайте семейство регулярных языков $L_i$, у которых ДКА для $L_i$ содержит $O(i)$ состояний, а синтаксический моноид $L_i$ имеет неполиномиальный размер.		# Придумайте семейство регулярных языков $L_i$, у которых ДКА для $L_i$ содержит $O(i)$ состояний, а синтаксический моноид $L_i$ имеет неполиномиальный размер.
	# Вспомните/узнайте определение моноида. Почему конструкция из задания 177 названа моноидом, опишите группоидную операцию для нее.		# Вспомните/узнайте определение моноида. Почему конструкция из задания 177 названа моноидом, опишите группоидную операцию для нее.
		+	# Постройте КС-грамматику для правильных скобочных последовательностей с двумя типами скобок. В этом и следующих заданиях, после разработки КС грамматики необходимо выбрать в качестве примера слово и продемонстрировать его левосторонний вывод и дерево разбора.
		+	# Постройте КС-грамматику для языка слов над алфавитом $\{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}$. Сделайте вывод про КС языки.
		+	# Пусть задана КС-грамматика для языка $L$. Укажите, как построить КС-грамматику для языка $L^*$.
		+	# Пусть задана КС-грамматика для языка $L$. Обозначим как $L^R$ язык, составленный из слов, которые, если их прочитать от конца к началу, принадлежат языку $L$. Укажите, как построить КС-грамматику для языка $L^R$.
		+	# Постройте КС-грамматику для языка $0^i1^j2^k$, $i \ne j$ или $j \ne k$.
		+	# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются палиндромами.
		+	# Постройте КС-грамматику для языка слов над алфавитом $\{(, )\}$, которые не являются правильными скобочными последовательностями.
		+	# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей не равно числу единиц.
		+	# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются тандемными повторами (не имеют вид $xx$ для некоторого слова $x$).
		+	# Постройте КС-грамматику, описывающие академические регулярные выражения над алфавитом $\{0, 1\}$.
		+	# КС грамматика называется линейной, если в правых частях правил встречается максимум один нетерминал. Праволинейные грамматики, в которых этот нетерминал находится на последнем месте, порождают регулярные языки. Приведите пример линейной грамматики, которая порождает нерегулярный язык.
		+	# КС грамматика называется леволинейной, если в правых частях правил встречается максимум один нетерминал, причем если он есть, то находится на первом месте. Докажите, что язык можно породить леволинейной грамматикой тогда и только тогда, когда он регулярный.
		+	# КС грамматика называется смешанной линейной, если в правых частях правил встречается максимум один нетерминал, причем если он есть, то находится либо на первом, либо на последнем месте. Докажите, что существует КС язык, не являющийся регулярным, который можно породить смешанной линейной грамматикой.

← Предыдущая		Версия 15:00, 7 мая 2021
Строка 163:		Строка 163:
	# Рассмотрим язык $\{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$. Докажите, что этот язык не является регулярным.		# Рассмотрим язык $\{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$. Докажите, что этот язык не является регулярным.
	# Из алгоритма построения множества различимых состояний следует, что если состояния $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n^2)$. Докажите, что если состояния $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n)$.		# Из алгоритма построения множества различимых состояний следует, что если состояния $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n^2)$. Докажите, что если состояния $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n)$.
		+	# Решите уравнение в регулярных выражениях $L=L\alpha+\beta$
		+	# Петя хочет решить уравнение в регулярных выражениях $L=\alpha L\xi+\beta$, где $\alpha$, $\beta$ и $\xi$ — регулярные выражения, а $L$ — неизвестный язык. Всегда ли решение будет регулярным языком?
		+	# В этом и последующих заданиях регулярный язык подается на вход вашему алгоритму как ДКА, распознающий этот язык. Предложите алгоритм проверки того, что регулярный язык бесконечен.
		+	# Предложите алгоритм подсчёта числа слов в регулярном языке (если язык бесконечен, алгоритм должен выдать информацию, что он бесконечен). Алгоритм должен работать за полином от числа состояний в автомате.
		+	# Предложите алгоритм проверки того, что регулярный язык является беспрефиксным.
		+	# Предложите алгоритм проверки того, что один регулярный язык является подмножеством другого.
		+	# Предложите алгоритм проверки того, что регулярные языки не пересекаются.
		+	# Предложите алгоритм проверки того, что объединение двух заданных регулярных языков совпадет с некоторым третьим заданным.
		+	# Приведите пример регулярного языка и двух неизоморфных недетерминированных автоматов для него, которые при этом имеют минимальное число состояний среди всех недетерминированных автоматов для этого языка.
		+	# Правые контексты. Правым контекстом слова $x$ в языке $A$ называется множество $R_A(x)$ таких слов $y$, что $xy \in A$. Докажите, что если $A$ регулярный, то количество различных правых контекстов равно числу состояний минимального ДКА для этого языка.
		+	# Левые контексты. Левым контекстом слова $x$ в языке $A$ называется множество $L_A(x)$ таких слов $y$, что $yx \in A$. Докажите, что язык $A$ регулярный тогда и только тогда, когда его множество левых контектов конечно.
		+	# Пусть язык $A$ регулярен и распознается ДКА с $n$ состояниями. Оцените сверху число различных левых контекстов в языке $A$.
		+	# Рассмотрим отношение на словах $L$: $x \equiv y$, если для любых $u$, $v$ выполнено $uxv \in L \Leftrightarrow uyv \in L$. Классы эквивалентности этого отношения называются синтаксическим моноидом языка $L$. Докажите, что если $L$ регулярный и его ДКА содержит $n$ состояний, то синтаксический моноид $L$ конечен и содержит не более $n^n$ классов эквивалентности.
		+	# Придумайте семейство регулярных языков $L_i$, у которых ДКА для $L_i$ содержит $O(i)$ состояний, а синтаксический моноид $L_i$ имеет неполиномиальный размер.
		+	# Вспомните/узнайте определение моноида. Почему конструкция из задания 177 названа моноидом, опишите группоидную операцию для нее.

← Предыдущая		Версия 14:53, 22 апреля 2021
Строка 142:		Строка 142:
	# Петя строит автомат для объединения языков $L_1$ и $L_2$ из автоматов для этих языков. Решив сэкономить, Петя просто объединил в одно начальные состояния автоматов для $L_1$ и $L_2$. Всегда ли у Пети получится то, что нужно?		# Петя строит автомат для объединения языков $L_1$ и $L_2$ из автоматов для этих языков. Решив сэкономить, Петя просто объединил в одно начальные состояния автоматов для $L_1$ и $L_2$. Всегда ли у Пети получится то, что нужно?
	# Петя строит автомат для замыкания Клини языка $L$. Решив сэкономить, Петя просто провёл $\varepsilon$-переход из каждого терминального состояния в начальное состояние, и сделал начальное состояние также терминальным. Всегда ли у Пети получится то, что нужно?		# Петя строит автомат для замыкания Клини языка $L$. Решив сэкономить, Петя просто провёл $\varepsilon$-переход из каждого терминального состояния в начальное состояние, и сделал начальное состояние также терминальным. Всегда ли у Пети получится то, что нужно?
		+	# Докажите нерегулярность языка палиндромов, если алфавит содержит хотя бы два символа. Что если алфавит унарный?
		+	# Докажите нерегулярность языка тандемных повторов $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$
		+	# Приведите пример нерегулярного языка, для которого выполнена лемма о разрастании
		+	# Обозначим как $\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_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)$ регулярный.
		+	# Пусть $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$. Докажите, что этот язык не является регулярным.
		+	# Из алгоритма построения множества различимых состояний следует, что если состояния $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n^2)$. Докажите, что если состояния $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n)$.

← Предыдущая		Версия 15:40, 14 апреля 2021
Строка 123:		Строка 123:
	# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3 или которые представляют собой двоичную запись чисел кратных 5. Сделайте вывод из последних двух заданий.		# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3 или которые представляют собой двоичную запись чисел кратных 5. Сделайте вывод из последних двух заданий.
	# Постройте детерминированный конечный автомат для языка слов над бинарным алфавитом, в которых третий символ с конца равен последнему символу.		# Постройте детерминированный конечный автомат для языка слов над бинарным алфавитом, в которых третий символ с конца равен последнему символу.
		+	# Запишите регулярное выражение для слов над бинарным алфавитом, содержащих два нуля подряд.
		+	# Запишите регулярное выражение для слов над бинарным алфавитом, содержащих не более одного места, где встречаются два нуля подряд.
		+	# Запишите регулярное выражение для слов над бинарным алфавитом, не содержащих два нуля подряд.
		+	# Запишите регулярное выражение для слов над алфавитом $\{a, b, c\}$, содержащих нечетное число букв $a$.
		+	# Запишите регулярное выражение для слов над бинарным алфавитом, задающих целое число в двоичной системе, не меньшее 51.
		+	# Запишите регулярное выражение для слов над алфавитом $\{a, b, c\}$, содержащих хотя бы одну букву $a$ и хотя бы одну букву $b$.
		+	# Запишите регулярное выражение для слов над алфавитом $\{a, b, c\}$, содержащих хотя бы две буквы $a$ и хотя бы одну букву $b$.
		+	# Запишите регулярное выражение для слов над бинарным алфавитом, которые представляют собой двоичную запись числа, кратного трем.
		+	# Постройте детерминированный конечный автомат для языка слов над бинарным алфавитом, в которых пятый символ с конца - единица.
		+	# Докажите, что любой детерминированный автомат для языка слов над бинарным алфавитом, в которых $k$-й символ с конца равен 0, содержит $\Omega(2^k)$ состояний.
		+	# Можно ли обобщить два предыдущих задания для любого размера алфавита $c$ следующим образом: построить семейство языков, для которых будут существовать НКА, содержащий $k$ состояний, но любые ДКА будут содержать $\Omega(c^k)$ состояний?
		+	# Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой развернутую двоичную запись чисел кратных 5 (сначала на вход подаются младшие разряды).
		+	# Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой развернутую двоичную запись чисел кратных 6 (сначала на вход подаются младшие разряды).
		+	# Предложите для заданного ДКА размера $n$ алгоритм подсчета количества слов длины $d$ которые он допускает, за $O(dn)$.
		+	# Предложите для заданного ДКА размера $n$ алгоритм подсчета количества слов длины $d$ которые он допускает, за $O(\log{(d)} \cdot poly(n))$ для некоторого полинома $poly$.
		+	# Предложите для заданного ДКА размера $n$ алгоритм подсчета количества слов длины не больше $d$ которые он допускает, за $O(\log{(d)} \cdot poly(n))$ для некоторого полинома $poly$.
		+	# Петя строит автомат для конкатенации языков $L_1$ и $L_2$ из автоматов для этих языков. Оказалось, что автомат для $L_1$ содержит только одно терминальное состояние и Петя просто объединил в одно это состояние и начальное состояние автомата для $L_2$. Всегда ли у Пети получится то, что нужно?
		+	# Петя строит автомат для объединения языков $L_1$ и $L_2$ из автоматов для этих языков. Решив сэкономить, Петя просто объединил в одно начальные состояния автоматов для $L_1$ и $L_2$. Всегда ли у Пети получится то, что нужно?
		+	# Петя строит автомат для замыкания Клини языка $L$. Решив сэкономить, Петя просто провёл $\varepsilon$-переход из каждого терминального состояния в начальное состояние, и сделал начальное состояние также терминальным. Всегда ли у Пети получится то, что нужно?

← Предыдущая		Версия 17:03, 31 марта 2021
Строка 107:		Строка 107:
	# Парадокс двух конвертов. Есть два неразличимых конверта с деньгами. В одном находится сумма в два раза большая, чем во втором. Величина этой суммы неизвестна. Конверты дают двум игрокам. Каждый из них может открыть свой конверт и пересчитать в нём деньги. После этого игроки должны решить: стоит ли обменять свой конверт на чужой? Оба игрока рассуждают следующим образом. Я вижу в своём конверте сумму $X$. В чужом конверте равновероятно может находиться $2X$ или $\frac{X}{2}$. Поэтому если я поменяю конверт, то у меня в среднем будет $\left(2X+\frac{X}{2}\right)/2 = \frac54X$, то есть больше, чем сейчас. Значит, обмен выгоден. Однако обмен не может быть выгоден обоим игрокам. Где в их рассуждениях кроется ошибка?		# Парадокс двух конвертов. Есть два неразличимых конверта с деньгами. В одном находится сумма в два раза большая, чем во втором. Величина этой суммы неизвестна. Конверты дают двум игрокам. Каждый из них может открыть свой конверт и пересчитать в нём деньги. После этого игроки должны решить: стоит ли обменять свой конверт на чужой? Оба игрока рассуждают следующим образом. Я вижу в своём конверте сумму $X$. В чужом конверте равновероятно может находиться $2X$ или $\frac{X}{2}$. Поэтому если я поменяю конверт, то у меня в среднем будет $\left(2X+\frac{X}{2}\right)/2 = \frac54X$, то есть больше, чем сейчас. Значит, обмен выгоден. Однако обмен не может быть выгоден обоим игрокам. Где в их рассуждениях кроется ошибка?
	# Пусть в парадоксе двух конвертов в качестве распределения используется следующее: с вероятностью $\frac{2^n}{3^{n+1}}$ в конверты помещаются суммы $2^n$ и $2^{n+1}$. Покажите, что в этом случае при обмене обмена вероятность получить $2X$ равна $1$, если игрок видит сумму $X=1$ и $\frac{11}{10}X$ в случае $X > 1$. Таким образом обмен выгоден в любом случае. Как такое возможно?		# Пусть в парадоксе двух конвертов в качестве распределения используется следующее: с вероятностью $\frac{2^n}{3^{n+1}}$ в конверты помещаются суммы $2^n$ и $2^{n+1}$. Покажите, что в этом случае при обмене обмена вероятность получить $2X$ равна $1$, если игрок видит сумму $X=1$ и $\frac{11}{10}X$ в случае $X > 1$. Таким образом обмен выгоден в любом случае. Как такое возможно?
		+	# Пусть $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.
		+	# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых встречается подпоследовательность 001.
		+	# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых нет трех нулей подряд
		+	# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых есть три нуля подряд. Сделайте вывод из двух последних заданий.
		+	# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых есть три единицы подряд. Сделайте вывод из двух последних заданий.
		+	# Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой двоичную запись чисел, кратных 5
		+	# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3 и которые представляют собой двоичную запись чисел кратных 5.
		+	# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3 или которые представляют собой двоичную запись чисел кратных 5. Сделайте вывод из последних двух заданий.
		+	# Постройте детерминированный конечный автомат для языка слов над бинарным алфавитом, в которых третий символ с конца равен последнему символу.

← Предыдущая		Версия 18:09, 26 марта 2021
Строка 95:		Строка 95:
	# Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних трех бросков равны 001. Какую строку длины 3 оптимально выбрать Васе, чтобы его вероятность выигрыша была максимальна?		# Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних трех бросков равны 001. Какую строку длины 3 оптимально выбрать Васе, чтобы его вероятность выигрыша была максимальна?
	# Предложите решение предыдущей задачи для произвольной выигрышной строки Пети (за полином от длины этой строки).		# Предложите решение предыдущей задачи для произвольной выигрышной строки Пети (за полином от длины этой строки).
		+	# Серия «парадоксы теории вероятности». Мы предлагаем попытаться решать задачи этой серии самостоятельно, а не с помощью интернета, потому что они, конечно, там подробно разобраны. Парадокс Монти Холла. Представьте, что вы стали участником игры, в которой вам нужно выбрать одну из трёх дверей. За одной из дверей находится автомобиль, за двумя другими дверями — козы. Вы выбираете одну из дверей, например, номер 1, после этого ведущий, который знает, где находится автомобиль, а где — козы, открывает одну из оставшихся дверей, например, номер 3, за которой находится коза. После этого он спрашивает вас — не желаете ли вы изменить свой выбор и выбрать дверь номер 2? Увеличатся ли ваши шансы выиграть автомобиль, если вы примете предложение ведущего и измените свой выбор?
		+	# Парадокс трёх заключённых. Трое заключённых, A, B и С, заключены в одиночные камеры и приговорены к смертной казни. Губернатор случайным образом выбирает одного из них и милует его. Стражник, охраняющий заключённых, знает, кто помилован, но не имеет права сказать этого. Заключённый A просит стражника сказать ему имя того (другого) заключённого, кто точно будет казнён: «Если B помилован, скажи мне, что казнён будет C. Если помилован C, скажи мне, что казнён будет B. Если они оба будут казнены, а помилован я, подбрось монету, и скажи имя B или C». Стражник говорит заключённому A, что заключённый B будет казнён. Заключённый A рад это слышать, поскольку он считает, что теперь вероятность его выживания стала 1/2, а не 1/3, как была до этого. Заключённый A тайно говорит заключённому С, что B будет казнён. Заключённый С также рад это слышать, поскольку он всё ещё полагает, что вероятность выживания заключённого А — 1/3, а его вероятность выживания возросла до 2/3. Как такое может быть?
		+	# Нетранзитивные кости. Набор игральных костей нетранзитивен, если он состоит из трёх игральных костей A, B и C, для которых результат бросания кости A с вероятностью свыше 50% больше результата бросания кости B, результат бросания кости B с вероятностью свыше 50% больше результата бросания кости C, однако утверждение о том, что результат бросания кости A с вероятностью свыше 50% больше результата бросания кости C, является ошибочным. Постройте набор нетранзитивных костей.
		+	# Усиленные нетранзитивные кости. Постройте набор из $n$ костей, в котором для любой кости есть другая, для которой с вероятностью свыше 50% будет получено большее число.
		+	# Парадокс Берксона. Два независимых события могут становиться зависимыми, если произошло некоторое событие. Придумайте три события $A$, $B$ и $C$, такие что $A$ и $B$ независимы, но $A \cap C$ и $B \cap C$ зависимы после замены вероятностного пространства на $C$ и новой дискретной плотности вероятности $p_C(x) = p(x) / P(C)$.
		+	# Парадокс дружбы — феномен, состоящий в том, что, как правило, у большинства людей друзей меньше, чем в среднем у их друзей. Прокомментируйте парадокс дружбы.
		+	# Парадокс коробок Бертрана. Есть три коробки: первая содержит две золотых монеты, вторая содержит две серебряные монеты, третья содержит одну золотую и одну серебряную монету. После выбора случайной коробки и случайной монеты из нее, выбранная монета оказалась золотой. Какова вероятность того, что вторая монета в выбранной коробке также золотая?
		+	# Парадокс Симпсона. Придумайте 4 дроби: $m_1/n_1$, $m_2/n_2$, $m_3/n_3$, $m_4/n_4$, чтобы выполнялось $m_1/n_1 < m_2/n_2$, $m_3/n_3 < m_4/n_4$ но $(m_1+m_3)/(n_1+n_3)>(m_2+m_4)/(n_2+n_4)$.
		+	# Санкт-Петербургский парадокс. Рассматривается следующая задача. Вступая в игру, игрок платит некоторую сумму $s$, а затем подбрасывает честную монету, пока не выпадет 1. При выпадении 1 игра заканчивается, а игрок получает выигрыш, рассчитанный по следующим правилам. Если 1 выпала на $i$-м броске, игрок получает $2^i$. Для какой максимальной суммы $c$ есть смысл играть в эту игру?
		+	# Парадокс галустков. Двое мужчин дарят друг другу на Рождество галстуки, купленные их жёнами. За напитками они начинают спорить, у кого галстук дешевле. Они приходят к тому, чтобы заключить пари — они будут консультироваться со своими жёнами и выяснят, какой галстук дороже. Условия пари в том, что человек с более дорогим галстуком должен отдать его проигравшему как утешительный приз. Первый человек рассуждает следующим образом: «Победа и поражения одинаково вероятны. Если я выиграю, я потеряю стоимость моего галстука. Но если я выиграю, то я выиграю больше, чем стоимость моего галстука. Поэтому шансы в мою пользу». Второй человек считает условия пари точно такими же, и, как ни парадоксально, кажется, оба мужчины имеют преимущество в этом пари.
		+	# Парадокс двух конвертов. Есть два неразличимых конверта с деньгами. В одном находится сумма в два раза большая, чем во втором. Величина этой суммы неизвестна. Конверты дают двум игрокам. Каждый из них может открыть свой конверт и пересчитать в нём деньги. После этого игроки должны решить: стоит ли обменять свой конверт на чужой? Оба игрока рассуждают следующим образом. Я вижу в своём конверте сумму $X$. В чужом конверте равновероятно может находиться $2X$ или $\frac{X}{2}$. Поэтому если я поменяю конверт, то у меня в среднем будет $\left(2X+\frac{X}{2}\right)/2 = \frac54X$, то есть больше, чем сейчас. Значит, обмен выгоден. Однако обмен не может быть выгоден обоим игрокам. Где в их рассуждениях кроется ошибка?
		+	# Пусть в парадоксе двух конвертов в качестве распределения используется следующее: с вероятностью $\frac{2^n}{3^{n+1}}$ в конверты помещаются суммы $2^n$ и $2^{n+1}$. Покажите, что в этом случае при обмене обмена вероятность получить $2X$ равна $1$, если игрок видит сумму $X=1$ и $\frac{11}{10}X$ в случае $X > 1$. Таким образом обмен выгоден в любом случае. Как такое возможно?