Редактирование: Список заданий по ДМ 2020 весна

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 164: Строка 164:
 
# Предложите алгоритм проверки, что в грамматике выводится хотя бы одно слово.
 
# Предложите алгоритм проверки, что в грамматике выводится хотя бы одно слово.
 
# Предложите алгоритм нахождения слова минимальной длины, выводящегося в заданной грамматике.
 
# Предложите алгоритм нахождения слова минимальной длины, выводящегося в заданной грамматике.
# Грамматика называется леворекурсивной, если найдется такой нетерминал A, что за один или более шаг из A можно вывести строку, которая начинается с A ($A \Rightarrow^+ A\alpha$). Предложите алгоритм, который проверяет, является ли грамматика леворекурсивной.
+
# Грамматика называется леворекурсивной, если найдется такой нетерминал A, что за один или более шаг из A можно вывести строку, которая начинается с A ($A \Rightarrow^+ A\alpha$).  
 +
# Предложите алгоритм, который проверяет, является ли грамматика леворекурсивной.
 
# Предложите алгоритм проверки, что в заданная КС грамматика в НФХ порождает конечное число слов.
 
# Предложите алгоритм проверки, что в заданная КС грамматика в НФХ порождает конечное число слов.
# Предложите алгоритм, который получает на вход КС грамматику в НФХ, про которую с помощью алгоритма из предыдущего задания выяснили, что она порождает конечное число слов. На выход необходимо выдать самое длинное слово, которое порождается этой КСГ.
+
# Предложите алгоритм, который, получает на вход КС грамматику в НФХ, про которую с помощью алгоритма из предыдущего задания выяснили, что она порождает конечное число слов. На выход необходимо выдать самое длинное слово, которое порождается этой КСГ.
 
# Билл поменял местами шаги алгоритма приведения КСГ к НФХ: он сначала удаляет цепные правила, а затем eps-правила. Будет ли корректно работать алгоритм?
 
# Билл поменял местами шаги алгоритма приведения КСГ к НФХ: он сначала удаляет цепные правила, а затем eps-правила. Будет ли корректно работать алгоритм?
 
# Билл поменял местами шаги алгоритма приведения КСГ к НФХ: он сначала удаляет eps-правила, а затем длинные правые части. Можно ли поправить алгоритм удаления eps-правил, чтобы он работал с длинными правыми частями? Чем эта версия алгоритма хуже оригинальной?
 
# Билл поменял местами шаги алгоритма приведения КСГ к НФХ: он сначала удаляет eps-правила, а затем длинные правые части. Можно ли поправить алгоритм удаления eps-правил, чтобы он работал с длинными правыми частями? Чем эта версия алгоритма хуже оригинальной?
Строка 172: Строка 173:
 
# Алиса разработала свою нормальную форму грамматики, в которой каждое правило имеет вид $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$.
 
# Постройте МП-автомат для языка слов, где число нулей равно числу единиц.
 
# Постройте МП-автомат для языка $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\}$, которые содержат равное число двоек и равное число единиц, или равное число двоек и равное число нулей.
 
# Рассмотрим список слов $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$.
 
# Предложите алгоритм проверки, что МП-автомат допускает заданное слово.
 
# Назовем состояние МП-автомата бесполезным, если автомат не может перейти в него ни при каком входном слове. Предложите алгоритм проверки состояния МП-автомата на бесполезность.
 
# Предложите алгоритм проверки, что МП-автомат допускает хотя бы одно слово, содержащее заданное в качестве подстроки.
 
# Предложите алгоритм проверки, что МП-автомат допускает бесконечное число слов.
 
# Пусть $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)$ также КС.
 

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

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

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

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