Редактирование: Список заданий по ТФЯ 2015

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 115: Строка 115:
 
# Пусть множество пар $A=\{(x, y)\}$ перечислимо. Можно ли утверждать, что множество $B$ минимальных парных для каждого $x$ ($B = \{(x, y)| (x, y) \in A \wedge (x, z)\in A \Rightarrow z \ge y\}$ перечислимо?
 
# Пусть множество пар $A=\{(x, y)\}$ перечислимо. Можно ли утверждать, что множество $B$ минимальных парных для каждого $x$ ($B = \{(x, y)| (x, y) \in A \wedge (x, z)\in A \Rightarrow z \ge y\}$ перечислимо?
 
# Пусть множество пар $A=\{(x, y)\}$ разрешимо. Можно ли утверждать, что множество $B$ минимальных парных для каждого $x$ ($B = \{(x, y)| (x, y) \in A \wedge (x, z)\in A \Rightarrow z \ge y\}$ перечислимо? Разрешимо?
 
# Пусть множество пар $A=\{(x, y)\}$ разрешимо. Можно ли утверждать, что множество $B$ минимальных парных для каждого $x$ ($B = \{(x, y)| (x, y) \in A \wedge (x, z)\in A \Rightarrow z \ge y\}$ перечислимо? Разрешимо?
# Пусть $A$ - произвольный список слов $(a_1, a_2, \ldots, a_n)$ над алфавитом $\Sigma$, содержащем хотя бы 2 символа. Рассмотрим алфавит $\Pi = \Sigma \cup \{1, 2, \ldots, n\}$. Обозначим как $L_A$ язык, содержащий множество слов, порождаемых грамматикой $S\to\varepsilon$, $S\to a_1S1$, ..., $S\to a_n S n$. Докажите, что для любого списка язык $\overline{L_A}$ дополнение до $L_A$ является контекстно-свободным.
 
# В этой и последующих задачах для задания КС-языка используется некоторая произвольная его КС-грамматика, а для задания регулярного языка - на ваш выбор конечный автомат или регулярное выражение. Докажите, что задача проверки пустоты пересечения контекстно-свободных языков алгоритмически неразрешима.
 
# Докажите, что задача равенства двух контекстно-свободных языков алгоритмически неразрешима.
 
# Докажите, что задача проверка равенства заданных контекстно-свободного языка и регулярного языка алгоритмически неразрешима.
 
# Докажите, что задача проверки равенства КС-языка языку $\Sigma^*$ алгоритмически неразрешима
 
# Докажите, что задача проверки, что один контекстно-свободный язык является подмножеством другого алгоритмически неразрешима.
 
# Докажите, что задача проверки, что заданный регулярный язык является подмножеством заданного контекстно-свободного алгоритмически неразрешима.
 
# Докажите, что множество КС-грамматик, порождающих язык, содержащий хотя бы один палиндром, неразрешимо
 
# Докажите, что язык $\overline{L_A}\cup\overline{L_B}$ является регулярным тогда и только тогда, когда он совпадает с $\Sigma^*$, то есть соответствующий экземпляр ПСП неразрешим. Сделайте вывод относительно возможности проверки КС-языка на регулярность.
 
# Докажите, что задача проверки, что дополнение КС-языка является КС-языком, алгоритмически неразрешима
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: