Викиконспекты - Свежие правки [ru]

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

2026-05-17T07:11:46Z

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

2026-05-17T07:09:26Z

← Предыдущая		Версия 07:11, 17 мая 2026
Строка 216:		Строка 216:
	# Приведите пример невычислимого предела сходящейся (но не вычислимо) последовательности вычислимых чисел		# Приведите пример невычислимого предела сходящейся (но не вычислимо) последовательности вычислимых чисел
	# Приведите пример невычислимого предела вычислимо сходящейся (но не вычислимой) последовательности вычислимых чисел		# Приведите пример невычислимого предела вычислимо сходящейся (но не вычислимой) последовательности вычислимых чисел
		+	# Рассмотрим список слов $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\}$. Рассмотрим КС-грамматику с одним нетерминалом $S$, алфавитом $\Sigma'$ и $n + 1$ правилом: $S \to \alpha_1 S d_1$, $S \to \alpha_2 S d_2, \ldots, S \to \alpha_n S d_n$, $S \to \varepsilon$. Язык, порождаемый этой грамматикой, называется языком списка $A$ и обозначается как $L_A$. Опишите все слова языка $L_A$.
		+	# Докажите, что для любого списка $A$ дополнение до его языка списка $\overline{L_A}$ является КС-языком. Указание: постройте МП-автомат для $\overline{L_A}$.
		+	# Докажите, что проблема проверки пустоты пересечения двух КС-грамматик неразрешима.
		+	# Докажите, что проблема проверки эквивалентности двух КС-грамматик неразрешима.
		+	# Докажите, что проблема проверки, что язык заданной КС-грамматики совпадает с языком заданного регулярного выражения, неразрешима.
		+	# Докажите, что проблема проверки того, что любое слово можно породить в заданной КС-грамматике, неразрешима.
		+	# Докажите, что проблема проверки того, что язык одной заданной КС-грамматики входит в язык другой заданной КС-грамматики, неразрешима.
		+	# Докажите, что проблема проверки того, что язык заданного регулярного выражения входит в язык заданной КС-грамматики, неразрешима.
		+	# Докажите, что проблема проверки того, что язык заданной КС-грамматики содержит палиндром, неразрешима.
		+	# Пусть задано два списка $A$ и $B$. Докажите, что $\overline{L_A} \cup \overline{L_B}$ является регулярным тогда и только тогда, когда он совпадает с $\Sigma'^*$. Следовательно проблема проверки того, что КС-грамматика порождает регулярный язык, неразрешима.
		+	# Докажите, что проблема проверки того, что дополнение языка заданной КС-грамматики является КС-языком, неразрешима.
		+	# Односторонние исчисления. Рассмотрим конечный набор правил $P$ вида $\alpha \rightarrow \beta$. Будем говорить, что из слова $x$ выводится $y$ с помощью $P$, если можно получить $x$ из $y$, выполнив ноль или более раз замену подстроки $x$, совпадающей с $\alpha$ для некоторого правила на $\beta$ для этого правила. Докажите, что множество троек $(P, x, y)$, где из $x$ выводится $y$ с помощью $P$ неразрешимо.
		+	# Двусторонние исчисления. Рассмотрим конечный алфавит $\Sigma$ и набор правил вида $\alpha \leftrightarrow \beta$. Будем говорить, что слова $x$ и $y$ эквивалентны с точностью до $P$, если можно получить $x$ из $y$, выполнив ноль или более раз замену подстроки $x$, совпадающей с $\alpha$ для некоторого правила на $\beta$ для этого правила или $\beta$ для некоторого правила на $\alpha$ для этого правила. Докажите, что множество троек $(P, x, y)$, где $x$ эквивалентен $y$ с точность до $P$ неразрешимо.
		+	# Докажите, существует конкретное множество правил одностороннего исчисления $P$, что для него множество пар $(x, y)$, где из $x$ выводится $y$ с помощью $P$ неразрешимо.
		+	# Докажите, существует конкретное множество правил двустороннего исчисления $P$, что для него множество пар $(x, y)$, где $x$ эквивалентно $y$ с точностью до $P$ неразрешимо. (Это задание можно переформулировать в терминах полугрупп так: докажите, что существует полугруппа с конечным множеством образующих и конечным множеством соотношений, что проверка равенства слов в этой полугруппе неразрешима)
		+	# Предыдущее задание можно обобщить на группы: докажите, что существует группа с конечным множеством образующих и конечным множеством соотношений, что проверка равенства слов в этой группе неразрешима. Отличие от предыдущего задания: вместе с каждым символом $c$ существует также символ $c^{-1}$ и соотношения $cc^{-1}\leftrightarrow\varepsilon$, $c^{-1}c\leftrightarrow\varepsilon$.
		+	# Множество $A$ назвается эффективно бесконечным, если существует всюду определенная вычислимая функция $f$, которая по числу $n$ выводит $n$ различных элементов множества $A$. Докажите, что если множество $A$ содержит бесконечное перечислимое подмножество, то оно эффективно бесконечно.
		+	# Докажите, что если множество $A$ эффективно бесконечно, то оно содержит бесконечное перечислимое подмножество.
		+	# Обозначим как $L(p)$ множество слов, которые допускается программой $p$. Множество $A$ назвается эффективно неперечислимым, если существует всюду определенная вычислимая функция $f$, которая по программе $p$ указывает слово $x$, такое что $x \in L(p) \oplus A$. Докажите, что дополнение к диагонали универсального множества $\overline D$, где $D = \left\{p \| \langle p, p\rangle \in U\right\}$, является эффективно неперечислимым.
		+	# Докажите, что дополнение к универсальному множеству $\overline U$ является эффективно неперечислимым.
		+	# Докажите, что любое эффективно неперечислимое множество является эффективно бесконечным.
		+	# Множество называется иммунным, если оно бесконечно, но не содержит бесконечных перечислимых подмножеств. Перечислимое множество называется простым, если дополнение к нему иммунно. Докажите, что существует простое множество.
		+	# Докажите, что множество является иммунным тогда и только тогда, когда оно не содержит бесконечных разрешимых подмножеств.

← Предыдущая		Версия 07:09, 17 мая 2026
Строка 222:		Строка 222:
	# Докажите, что для любого КС-языка существует МП-автомат, который на каждом переходе кладет в стек не более двух символов.		# Докажите, что для любого КС-языка существует МП-автомат, который на каждом переходе кладет в стек не более двух символов.
	# Можно ли в условии предыдущего задания заменить два символа на один?		# Можно ли в условии предыдущего задания заменить два символа на один?
		+	# Петя хочет решить уравнение в регулярных выражениях $L=\alpha L\xi+\beta$, где $\alpha$, $\beta$ и $\xi$ — регулярные выражения, а $L$ — неизвестный язык. Всегда ли решение будет регулярным языком?
		+	# В этом и последующих заданиях регулярный язык подается на вход вашему алгоритму как ДКА, распознающий этот язык. Предложите алгоритм проверки того, что регулярный язык бесконечен.
		+	# Предложите алгоритм подсчёта числа слов в регулярном языке (если язык бесконечен, алгоритм должен выдать информацию, что он бесконечен). Алгоритм должен работать за полином от числа состояний в автомате.
		+	# Предложите алгоритм проверки того, что регулярный язык является беспрефиксным.
		+	# Предложите алгоритм проверки того, что один регулярный язык является подмножеством другого.
		+	# Предложите алгоритм проверки того, что регулярные языки не пересекаются.
		+	# Предложите алгоритм проверки того, что объединение двух заданных регулярных языков совпадет с некоторым третьим заданным.
		+	# Приведите пример регулярного языка и двух неизоморфных недетерминированных автоматов для него, которые при этом имеют минимальное число состояний среди всех недетерминированных автоматов для этого языка.
		+	# Из алгоритма построения множества различимых состояний следует, что если состояния $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n^2)$. Докажите, что если состояния $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n)$.
		+	# Правые контексты. Правым контекстом слова $x$ в языке $A$ называется множество $R_A(x)$ таких слов $y$, что $xy \in A$. Рассмотрим правые контексты всех слов $x \in \Sigma^*$. Докажите, что если число различных правых контекстов конечно, то язык $A$ является регулярным.
		+	# Докажите, что если число различных правых контекстов бесконечно, то язык $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$ имеет неполиномиальный размер.
		+	# Вспомните/узнайте определение моноида. Почему конструкция из задания 238 названа моноидом, опишите группоидную операцию для нее.