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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:30:01Z

rollbackEdits.php mass rollback

80.82.78.13 в 04:39, 1 сентября 2022

2022-09-01T04:39:01Z

89.221.207.142 в 11:53, 25 мая 2019

2019-05-25T11:53:13Z

Linn в 11:46, 14 мая 2019

2019-05-14T11:46:08Z

194.150.65.188 в 09:56, 5 мая 2019

2019-05-05T09:56:56Z

91.135.68.130: sta

2019-04-29T19:57:14Z

sta

89.221.207.142 в 15:07, 27 апреля 2019

2019-04-27T15:07:57Z

77.234.212.37 в 10:55, 22 апреля 2019

2019-04-22T10:55:19Z

94.25.170.185 в 10:06, 21 апреля 2019

2019-04-21T10:06:47Z

89.221.207.142 в 15:23, 13 апреля 2019

2019-04-13T15:23:48Z

← Предыдущая		Версия 16:30, 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 Майкл Наки].
−	\|}
−
	# Чему равна вероятность, что две случайно вытянутые кости домино можно приложить друг к другу по правилам домино?		# Чему равна вероятность, что две случайно вытянутые кости домино можно приложить друг к другу по правилам домино?
	# Чему равна вероятность, что на двух брошенных честных игральных костях выпадут числа, одно из которых делит другое?		# Чему равна вероятность, что на двух брошенных честных игральных костях выпадут числа, одно из которых делит другое?

← Предыдущая		Версия 04:39, 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 Майкл Наки].
		+	\|}
		+
	# Чему равна вероятность, что две случайно вытянутые кости домино можно приложить друг к другу по правилам домино?		# Чему равна вероятность, что две случайно вытянутые кости домино можно приложить друг к другу по правилам домино?
	# Чему равна вероятность, что на двух брошенных честных игральных костях выпадут числа, одно из которых делит другое?		# Чему равна вероятность, что на двух брошенных честных игральных костях выпадут числа, одно из которых делит другое?

← Предыдущая		Версия 11:53, 25 мая 2019
Строка 167:		Строка 167:
	# Докажите или опровергните, что язык является контекстно-свободным: $0^a1^b2^a$, $a\ne 2b$		# Докажите или опровергните, что язык является контекстно-свободным: $0^a1^b2^a$, $a\ne 2b$
	# Докажите или опровергните, что язык является контекстно-свободным: $0^a1^b2^a$, $2a\ne b$		# Докажите или опровергните, что язык является контекстно-свободным: $0^a1^b2^a$, $2a\ne b$
		+	# Рассмотрим список слов $A = \{\alpha_1, \alpha_2, \ldots, \alpha_n\}$ над алфавитом $\Sigma$. Введем $n$ новых различных символов $d_1, d_2, \ldots, d_n$. Рассмотрим алфавит $\Sigma' = \Sigma \cup \{d_1, d_2, \ldots, d_n\}$. Рассмотрим язык списка $A$, обозначаемый как $L_A$, в который входят все слова вида $\alpha_{i_1}\alpha_{i_2}\ldots\alpha_{i_k}d_{i_k}d_{i_{k-1}}\ldots d_{i_1}$. Докажите, что для любого списка $A$ язык $L_A$ является контекстно-свободным.
		+	# Докажите, что дополнение к языку списка $L_A$ является контекстно-свободным для любого списка $A$.
		+	# Можно неправильно определить язык списка $A = \{\alpha_1, \alpha_2, \ldots, \alpha_n\}$ из предыдущего задания, составив его из слов вида $\alpha_{i_1}\alpha_{i_2}\ldots\alpha_{i_k}d_{i_1}d_{i_2}\ldots d_{i_k}$. Докажите или опровергните, что при таком неправильном определении язык списка все еще будет конткстно-свободным для любого списка $A$.
		+	# Постройте МП-автомат для языка $0^n1^n$.
		+	# Постройте МП-автомат для языка слов, где число нулей равно числу единиц.
		+	# Постройте МП-автомат для языка $0^n1^{2n}$.
		+	# Постройте МП-автомат для языка $0^n1^m2^{n+m}$.
		+	# Постройте МП-автомат для языка $0^{2n}1^n$.
		+	# Постройте МП-автомат для языка $0^n1^n\cup0^n1^{2n}$.
		+	# Постройте МП-автомат для языка слов $0^n1^m$, где $n \le m \le 2n$.
		+	# Докажите, что для любых $p$ и $q$ существует МП-автомат для языка слов $0^n1^m$, где $n/m=p/q$
		+	# Постройте автомат с магазинной памятью для языка слов над алфавитом $\{0, 1, 2\}$, которые содержат равное число двоек и равное число единиц, или равное число двоек и равное число нулей.
		+	# Предложите алгоритм проверки, что МП-автомат допускает заданное слово.
		+	# Назовем состояние МП-автомата бесполезным если автомат не может перейти в него ни при каком входном слове. Предложите алгоритм проверки состояния МП-автомата на бесполезность.
		+	# Предложите алгоритм проверки, что МП-автомат допускает хотя бы одно слово, содержащее заданное в качестве подстроки.
		+	# Предложите алгоритм проверки, что МП-автомат допускает бесконечное число слов.

@@ Строка 160: / Строка 160: @@
 # Приведите пример не КС-языка, для которого выполнена лемма о разрастании.
 # Приведите пример КС-языка, не являющегося регулярным, дополнение к которому также является КС.
-# Приведите пример двух КС-языка, не являющихся регулярными, пересечение которых также является КС, но не регулярным, причем отлично от обоих пересекаемых языков.
+# Приведите пример двух КС-языков, не являющихся регулярными, пересечение которых также является КС, но не регулярным, причем отлично от обоих пересекаемых языков.
 # Пусть $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)$ также КС.

← Предыдущая		Версия 09:56, 5 мая 2019
Строка 135:		Строка 135:
	# Рассмотрим отношение на словах $L$: $x \equiv y$, если для любых $u$, $v$ выполнено $uxv \in L \Leftrightarrow uyv \in L$. Классы эквивалентности этого отношения называются синтаксическим моноидом языка $L$. Докажите, что $L$ регулярный тогда и только тогда, когда синтаксический моноид $L$ конечен.		# Рассмотрим отношение на словах $L$: $x \equiv y$, если для любых $u$, $v$ выполнено $uxv \in L \Leftrightarrow uyv \in L$. Классы эквивалентности этого отношения называются синтаксическим моноидом языка $L$. Докажите, что $L$ регулярный тогда и только тогда, когда синтаксический моноид $L$ конечен.
	# Придумайте семейство регулярных языков $L_i$, у которых ДКА для $L_i$ содержит $O(i)$ состояний, а синтаксический моноид $L_i$ имеет неполиномиальный размер.		# Придумайте семейство регулярных языков $L_i$, у которых ДКА для $L_i$ содержит $O(i)$ состояний, а синтаксический моноид $L_i$ имеет неполиномиальный размер.
		+	# Постройте КС-грамматику для правильных скобочных последовательностей с двумя типами скобок.
		+	# Постройте КС-грамматику для языка $0^n1^n$.
		+	# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей равно числу единиц. Докажите, что ваша грамматика является правильной.
		+	# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей равно удвоенному числу единиц. Докажите, что ваша грамматика является правильной.
		+	# Постройте КС-грамматику для языка $0^k1^n2^{k+n}$.
		+	# Постройте КС-грамматику для языка $0^k1^n2^{k+n}\cup 1^k0^n2^{k+n}$.
		+	# Постройте КС-грамматику для языка $0^k1^n2^{k+n}1^i0^j2^{i+j}$.
		+	# Постройте КС-грамматику для языка $0^i1^j2^k$, $i \ne j$ или $j \ne k$.
		+	# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются палиндромами.
		+	# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются правильными скобочными последовательностями.
		+	# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей не равно числу единиц.
		+	# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются тандемными повторами.
		+	# Верно ли, что любую КС-грамматику можно привести к форме, когда любое правило имеет вид $A\to BCD$ или $A\to a$?
		+	# Верно ли, что любой КС-язык над односимвольным алфавитом является регулярным?
		+	# Докажите, что язык не является КС: $0^i1^j2^k$, $i<j<k$.
		+	# Докажите, что язык не является КС: $0^n1^n2^k$, $k<n$.
		+	# Докажите, что язык не является КС: $0^p$, $p$ простое.
		+	# Докажите, что язык двоичных записей простых чисел не является КС.
		+	# Докажите, что язык не является КС: $0^i1^j$, $j=i^2$.
		+	# Докажите, что язык не является КС: $0^n1^n2^k$, $n<k<2n$.
		+	# Докажите, что язык не является КС: $ww^Rw$, $w$ - строка из 0 и 1, $w^R$ - развернутая строка $w$.
		+	# Докажите, что язык $\{0^n1^m2^n3^m\}$ не является КС.
		+	# Докажите, что язык $\{0^n1^m2^n\| n \ne m\}$ не является КС.
		+	# Приведите пример не КС-языка, для которого выполнена лемма о разрастании.
		+	# Приведите пример КС-языка, не являющегося регулярным, дополнение к которому также является КС.
		+	# Приведите пример двух КС-языка, не являющихся регулярными, пересечение которых также является КС, но не регулярным, причем отлично от обоих пересекаемых языков.
		+	# Пусть $f : \Sigma \to \Sigma^*$ - функция, сопоставляющая каждому символу некоторую строку. Распространим $f$ на слова следующим образом: $f(c_1c_2\ldots c_k) = f(c_1)f(c_2)\ldots f(c_k)$. Обозначим как $f(L)$ множество слов $f(x)$ для всех $x \in L$. Докажите или опровергните, что если $L$ - КС, то $f(L)$ также КС.
		+	# Пусть $f : \Sigma \to \Sigma^*$ - функция, сопоставляющая каждому символу некоторую строку. Распространим $f$ на слова следующим образом: $f(c_1c_2\ldots c_k) = f(c_1)f(c_2)\ldots f(c_k)$. Обозначим как $f^{-1}(L)$ множество таких слов $x$, для которых $f(x) \in L$. Докажите или опровергните, что если $L$ - КС, то $f^{-1}(L)$ также КС.
		+	# Докажите или опровергните, что язык является контекстно-свободным: $0^a1^b2^a$, $a=2b$
		+	# Докажите или опровергните, что язык является контекстно-свободным: $0^a1^b2^a$, $2a=b$
		+	# Докажите или опровергните, что язык является контекстно-свободным: $0^a1^b2^a$, $a\ne 2b$
		+	# Докажите или опровергните, что язык является контекстно-свободным: $0^a1^b2^a$, $2a\ne b$

@@ Строка 130: / Строка 130: @@
 # Обозначим как $\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 \}$.

← Предыдущая		Версия 15:07, 27 апреля 2019
Строка 119:		Строка 119:
	# Предложите алгоритм проверки того, что объединение двух заданных регулярных языков совпадет с некоторым третьим заданным.		# Предложите алгоритм проверки того, что объединение двух заданных регулярных языков совпадет с некоторым третьим заданным.
	# Приведите пример регулярного языка и двух неизоморфных недетерминированных автоматов для него, которые при этом имеют минимальное число состояний среди всех недетерминированных автоматов для этого языка.		# Приведите пример регулярного языка и двух неизоморфных недетерминированных автоматов для него, которые при этом имеют минимальное число состояний среди всех недетерминированных автоматов для этого языка.
		+	# Петя строит автомат для конкатенации языков $L_1$ и $L_2$ из автоматов для этих языков. Оказалось, что автомат для $L_1$ содержит только одно терминальное состояние и Петя просто объединил в одно это состояние и начальное состояние автомата для $L_2$. Всегда ли у Пети получится то, что нужно?
		+	# Петя строит автомат для объединения языков $L_1$ и $L_2$ из автоматов для этих языков. Решив сэкономить, Петя просто объединил в одно начальные состояния автоматов для $L_1$ и $L_2$. Всегда ли у Пети получится то, что нужно?
		+	# Петя строит автомат для замыкания Клини языка $L$. Решив сэкономить, Петя просто провёл $\varepsilon$-переход из каждого терминального состояния в начальное состояние, и сделал начальное состояние также терминальным. Всегда ли у Пети получится то, что нужно?
		+	# Обозначим как $\min L$ множество слов $w \in L$, таких что никакой собственный префикс $w$ не является словом языка $L$. Докажите, что если $L$ регулярный, то и $\min L$ регулярный.
		+	# Обозначим как $\max L$ множество слов $w \in L$, таких что $w$ не является собственным префиксом никакого словом языка $L$. Докажите, что если $L$ регулярный, то и $\max L$ регулярный.
		+	# Обозначим как $\mbox{pref}\,L$ множество префиксов слов языка $L$. Докажите, что если $L$ регулярный, то и $\mbox{pref}\,L$ регулярный.
		+	# Обозначим как $\mbox{suf}\,L$ множество суффиксов слов языка $L$. Докажите, что если $L$ регулярный, то и $\mbox{suf}\,L$ регулярный.
		+	# Пусть $a$ и $b$ - слова равной длины $n$. Обозначим как $\mbox{alt}(a, b)$ слово $a_1b_2a_2b_2\ldots a_nb_n$. Для языков $R$ и $S$ обозначим как $\mbox{alt}(R, S)$ множество всех слов, которые получаются как $\mbox{alt}(a, b)$ где $a \in R$, $b \in S$. Докажите, что если $R$ и $S$ регулярные, то $\mbox{alt}(R, S)$ регулярный.
		+	# Пусть $a$ и $b$ - слова. Обозначим как $\mbox{shuffle}(a, b)$ множество слов, которые можно составить, вставив в слово $a$ все буквы слова $b$ в том порядке, в котором они идут в $b$. Например, $\mbox{shuffle}(01, 23)=\{0123, 0213, 0231, 2013, 2031, 2301\}$. Для языков $R$ и $S$ обозначим как $\mbox{shuffle}(R, S)$ объединение всех множеств $\mbox{shuffle}(a, b)$ где $a \in R$, $b \in S$. Докажите, что если $R$ и $S$ регулярные, то $\mbox{shuffle}(R, S)$ регулярный.
		+	# Обозначим как $\mbox{cycle}\,L$ множество циклических сдвигов слов языка $L$. Докажите, что если $L$ регулярный, то и $\mbox{cycle}\,L$ регулярный.
		+	# Обозначим как $\mbox{half}\,L$ множество таких слов $a$, что существует слово $b$ такой же длины, как и $a$, что $ab \in L$. Докажите, что если $L$ регулярный, то и $\mbox{half}\,L$ регулярный.
		+	# Приведите пример регулярного языка и двух неизоморфных недетерминированных автоматов для него, которые при этом имеют минимальное число состояний среди всех недетерминированных автоматов для этого языка.
		+	# Рассмотрим язык $\{x_0 y_0 z_0 x_1 y_1 z_1 \dots x_{n-1} y_{n-1} z_{n-1} \mid x_i, y_i, z_i \in \{0, 1\}\}$, где $ X = x_{n-1}x_{n-2}\dots x_0$ и аналогично представляется $Y$ и $Z$, причем $ X + Y = Z $. Докажите, что этот язык регулярный.
		+	# То же, что и предыдущее, только $\{x_{n-1} y_{n-1} z_{n-1} \dots x_1 y_1 z_1 x_0 y_0 z_0 \mid \dots \}$.
		+	# Рассмотрим язык $\{x_0 y_0 z_0 x_1 y_1 z_1 \dots x_{n-1} y_{n-1} z_{n-1} \mid x_i, y_i, z_i \in \{0, 1\}\}$, где $X = x_{n-1}x_{n-2}\dots x_0$ и аналогично представляется $Y$ и $Z$, причем $X \times Y = Z$. Докажите, что этот язык не является регулярным.
		+	# Рассмотрим отношение на словах $L$: $x \equiv y$, если для любых $u$, $v$ выполнено $uxv \in L \Leftrightarrow uyv \in L$. Классы эквивалентности этого отношения называются синтаксическим моноидом языка $L$. Докажите, что $L$ регулярный тогда и только тогда, когда синтаксический моноид $L$ конечен.
		+	# Придумайте семейство регулярных языков $L_i$, у которых ДКА для $L_i$ содержит $O(i)$ состояний, а синтаксический моноид $L_i$ имеет неполиномиальный размер.

@@ Строка 102: / Строка 102: @@
 # Докажите нерегулярность языка, каждое слово которого содержит поровну 0 и 1.
 # Докажите нерегулярность языка палиндромов.
-# Докажите нерегулярность языка тандемных повторов.
+# Докажите нерегулярность языка тандемных повторов $L = \{ ww | w \in \Sigma^* \}$.
 # Докажите нерегулярность языка $0^n1^m$, $n \le m$
 # Докажите нерегулярность языка $0^n1^m$, $n \ne m$

← Предыдущая		Версия 10:06, 21 апреля 2019
Строка 100:		Строка 100:
	# Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой развернутую двоичную запись чисел кратных 5 (сначала на вход подаются младшие разряды).		# Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой развернутую двоичную запись чисел кратных 5 (сначала на вход подаются младшие разряды).
	# Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой развернутую двоичную запись чисел кратных 6 (сначала на вход подаются младшие разряды).		# Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой развернутую двоичную запись чисел кратных 6 (сначала на вход подаются младшие разряды).
		+	# Докажите нерегулярность языка, каждое слово которого содержит поровну 0 и 1.
		+	# Докажите нерегулярность языка палиндромов.
		+	# Докажите нерегулярность языка тандемных повторов.
		+	# Докажите нерегулярность языка $0^n1^m$, $n \le m$
		+	# Докажите нерегулярность языка $0^n1^m$, $n \ne m$
		+	# Докажите нерегулярность языка $0^{n^2}$
		+	# Докажите нерегулярность языка $0^p$, $p$ {{---}} простое
		+	# Докажите нерегулярность языка двоичных записей простых чисел
		+	# Докажите нерегулярность языка $0^n1^m$, $gcd(n, m) = 1$
		+	# Докажите нерегулярность языка $0^a1^b2^c$, $a \ne b$ или $b \ne c$
		+	# Приведите пример нерегулярного языка, для которого выполнена лемма о разрастании
		+	# Из алгоритма построения множества различимых состояний следует, что $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n^2)$. Докажите, что если состояния $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n)$.
		+	# Предложите алгоритм проверки того, что регулярный язык бесконечен
		+	# Предложите алгоритм подсчёта числа слов в регулярном языке (если язык бесконечен, алгоритм должен выдать информацию, что он бесконечен). Алгоритм должен работать за полином от числа состояний в автомате.
		+	# Предложите алгоритм проверки того, что регулярный язык является беспрефиксным
		+	# Предложите алгоритм проверки того, что один регулярный язык является подмножеством другого
		+	# Предложите алгоритм проверки того, что регулярные языки не пересекаются
		+	# Предложите алгоритм проверки того, что объединение двух заданных регулярных языков совпадет с некоторым третьим заданным.
		+	# Приведите пример регулярного языка и двух неизоморфных недетерминированных автоматов для него, которые при этом имеют минимальное число состояний среди всех недетерминированных автоматов для этого языка.

← Предыдущая		Версия 15:23, 13 апреля 2019
Строка 83:		Строка 83:
	# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число единиц кратно 3. Сделайте вывод.		# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число единиц кратно 3. Сделайте вывод.
	# Постройте детерминированный конечный автомат для языка слов над бинарным алфавитом, в которых второй символ с конца равен последнему символу.		# Постройте детерминированный конечный автомат для языка слов над бинарным алфавитом, в которых второй символ с конца равен последнему символу.
		+	# Для заданного ДКА размера $n$ посчитать количество слов длины $d$, которые он допускает за $O(dn)$.
		+	# То же самое, что в предыдущей, но за $O(\log{(d)} \cdot Poly(n))$.
		+	# Посчитать количество слов длины не больше $d$, которые допускает автомат за $O(\log{(d)} \cdot Poly(n))$.
		+	# Запишите регулярное выражения для слов над бинарным алфавитом, содержащих два нуля подряд.
		+	# Запишите регулярное выражения для слов над бинарным алфавитом, содержащих не более одного места, где встречаются два нуля подряд.
		+	# Запишите регулярное выражения для слов над бинарным алфавитом, не содержащих два нуля подряд.
		+	# Запишите регулярное выражения для слов над алфавитом $\{a, b, c\}$, содержащих нечетное число букв $a$.
		+	# Запишите регулярное выражения для слов над бинарным алфавитом, задающих целое число в двоичной системе, не меньшее 8.
		+	# Запишите регулярное выражения для слов над бинарным алфавитом, задающих целое число в двоичной системе, не меньшее 51.
		+	# Запишите регулярное выражения для слов над алфавитом $\{a, b, c\}$, содержащих хотя бы одну букву $a$ и хотя бы одну букву $b$.
		+	# Запишите регулярное выражения для слов над алфавитом $\{a, b, c\}$, содержащих хотя бы две буквы $a$ и хотя бы одну букву $b$.
		+	# Запишите регулярное выражения для слов над бинарным алфавитом, которые представляют собой двоичную запись числа, кратного трем.
		+	# Постройте детерминированный конечный автомат для языка слов над бинарным алфавитом, в которых пятый символ с конца - единица.
		+	# Докажите, что любой детерминированный автомат для языка слов над бинарным алфавитом, в которых $k$-й символ с конца равен 0, содержит $\Omega(2^k)$ состояний.
		+	# Можно ли обобщить два предыдущих задания для любого размера алфавита $c$ следующим образом: построить семейство языков, для которых будут существовать НКА, содержащий $O(k)$ состояний, но любые ДКА будут содержать $\Omega(c^k)$ состояний?
		+	# Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой развернутую двоичную запись чисел кратных 5 (сначала на вход подаются младшие разряды).
		+	# Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой развернутую двоичную запись чисел кратных 6 (сначала на вход подаются младшие разряды).