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

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

2026-05-01T10:46:49Z

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

2026-05-01T10:45:55Z

← Предыдущая		Версия 10:46, 1 мая 2026
Строка 179:		Строка 179:
	# Множество называется m-полным, если к нему m-сводится любое перечислимое множество. Докажите, что универсальное множество является $m$-полным.		# Множество называется m-полным, если к нему m-сводится любое перечислимое множество. Докажите, что универсальное множество является $m$-полным.
	# Докажите, что диагональ универсального множества (множество $\{u \| (u, u) \in U\}$ является m-полным.		# Докажите, что диагональ универсального множества (множество $\{u \| (u, u) \in U\}$ является m-полным.
		+	# Используя теорему о рекурсии, докажите, что язык программ, которые останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым?
		+	# Используя теорему о рекурсии, докажите, что язык программ, которые не останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым?
		+	# Используя теорему о рекурсии, докажите, что язык программ, которые допускают бесконечное число слов, является неразрешимым.
		+	# Используя теорему о рекурсии, докажите, что язык программ, которые допускают свой собственный исходный код, является неразрешимым.
		+	# Докажите, что существуют две различные программы $p$ и $q$, такие что программа $p$ печатает текст программы $q$, а программа $q$ печатает текст программы $p$.
		+	# Докажите, что существует бесконечная последовательность различных программ $p_i$, такая что $p_1$ печатает пустую строку, а $p_i$ печатает текст программы $p_{i-1}$.
		+	# Докажите, что существует бесконечная последовательность различных программ $p_i$, такая что $p_i$ печатает текст программы $p_{i+1}$.
		+	# Докажите, что для любого конечного $n$ существует последовательность программ $p_1, p_2, \ldots, p_n$, что $p_i$ печатает текст $p_{i+1}$, а $p_n$ печатает текст $p_1$.
		+	# Докажите, что язык программ, для которых не существует более короткой программы, которая на любом входе ведёт себя так же, является неразрешимым.
		+	# Докажите, что язык программ, для которых не существует программы такой же длины, которая на любом входе ведёт себя так же, является либо конечным, либо неразрешимым.
		+	# Докажите, что для любой всюду определенной вычислимой функции $f$ найдется значение $n$, для которого $BB(n) > f(n)$.
		+	# Докажите, что для любой всюду определенной вычислимой функции $f$ найдется бесконечно много значений $n$, для которых $BB(n) > f(n)$.
		+	# Пусть для любой строки $s$ выполнено $K(s) \ge f(s)$, где $f$ — всюду определенная вычислимая функция. Докажите, что найдется константа $C$, такая что $f(s) \le C$ для любой $s$.
		+	# Рассмотрим функцию $S(n)$, равную максимальной длине строки, выводимой программой длины $n$ на пустом входе. Докажите, что $S(n)$ невычислима.
		+	# Рассмотрим произвольную всюду определенную вычислимую функцию $f : \Sigma^* \to \Sigma^*$. Докажите, что существует программа $p$, что $L(p) = L(f(p))$.

← Предыдущая		Версия 10:45, 1 мая 2026
Строка 185:		Строка 185:
	# КС грамматика называется леволинейной, если в правых частях правил встречается максимум один нетерминал, причем если он есть, то находится на первом месте. Докажите, что язык можно породить леволинейной грамматикой тогда и только тогда, когда он регулярный.		# КС грамматика называется леволинейной, если в правых частях правил встречается максимум один нетерминал, причем если он есть, то находится на первом месте. Докажите, что язык можно породить леволинейной грамматикой тогда и только тогда, когда он регулярный.
	# КС грамматика называется смешанной линейной, если в правых частях правил встречается максимум один нетерминал, причем если он есть, то находится либо на первом, либо на последнем месте. Докажите, что существует КС язык, не являющийся регулярным, который можно породить смешанной линейной грамматикой.		# КС грамматика называется смешанной линейной, если в правых частях правил встречается максимум один нетерминал, причем если он есть, то находится либо на первом, либо на последнем месте. Докажите, что существует КС язык, не являющийся регулярным, который можно породить смешанной линейной грамматикой.
		+	# Постройте МП-автомат для языка слов, где число нулей равно числу единиц.
		+	# Постройте МП-автомат для языка $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$. Как обобщить алгоритм КЯК на грамматики в такой форме? Сравните получившийся алгоритм с оригинальным.
		+	# Рассмотрим дерево разбора некоторого слова в грамматике в НФХ. Как соотносятся количество нетерминалов и терминалов в дереве?