211
правок
Изменения
Нет описания правки
# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3 или которые представляют собой двоичную запись чисел кратных 5. Сделайте вывод из последних двух заданий.
# Постройте детерминированный конечный автомат для языка слов над бинарным алфавитом, в которых третий символ с конца равен последнему символу.
# Запишите регулярное выражение для слов над бинарным алфавитом, содержащих два нуля подряд.
# Запишите регулярное выражение для слов над бинарным алфавитом, содержащих не более одного места, где встречаются два нуля подряд.
# Запишите регулярное выражение для слов над бинарным алфавитом, не содержащих два нуля подряд.
# Запишите регулярное выражение для слов над бинарным алфавитом, не содержащих три нуля и не содержит три единицы подряд.
# Запишите регулярное выражение для слов над алфавитом $\{a, b, c\}$, содержащих нечетное число букв $a$.
# Запишите регулярное выражение для слов над бинарным алфавитом, задающих целое число в двоичной системе, не меньшее 51.
# Запишите регулярное выражение для слов над алфавитом $\{a, b, c\}$, содержащих хотя бы две буквы $a$ и хотя бы одну букву $b$.
# Запишите регулярное выражение для слов над бинарным алфавитом, которые представляют собой двоичную запись числа, кратного трем.
# Постройте детерминированный конечный автомат для языка слов над бинарным алфавитом, в которых пятый символ с конца - единица.
# Докажите, что любой детерминированный автомат для языка слов над бинарным алфавитом, в которых $k$-й символ с конца равен 0, содержит как минимум $2^k$ состояний.
# Можно ли обобщить два предыдущих задания для любого размера алфавита $c$ следующим образом: построить семейство языков, для которых будут существовать НКА, содержащий $k$ состояний, но любые ДКА будут содержать $\Omega(c^k)$ состояний?
# Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой развернутую двоичную запись чисел, кратных 5 (сначала на вход подаются младшие разряды).
# Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой развернутую двоичную запись чисел, кратных 6 (сначала на вход подаются младшие разряды).
# Предложите для заданного ДКА размера $n$ алгоритм подсчета количества слов длины $d$ которые он допускает, за $O(dn)$.
# Предложите для заданного ДКА размера $n$ алгоритм подсчета количества слов длины $d$ которые он допускает, за $O(\log{(d)} \cdot poly(n))$ для некоторого полинома $poly$.
# Предложите для заданного ДКА размера $n$ алгоритм подсчета количества слов длины не больше $d$ которые он допускает, за $O(\log{(d)} \cdot poly(n))$ для некоторого полинома $poly$.
# Петя строит автомат для конкатенации языков $L_1$ и $L_2$ из автоматов для этих языков. Оказалось, что автомат для $L_1$ содержит только одно терминальное состояние и Петя просто объединил в одно это состояние и начальное состояние автомата для $L_2$. Всегда ли у Пети получится то, что нужно?
# Петя строит автомат для объединения языков $L_1$ и $L_2$ из автоматов для этих языков. Решив сэкономить, Петя просто объединил в одно начальные состояния автоматов для $L_1$ и $L_2$. Всегда ли у Пети получится то, что нужно?
# Петя строит автомат для замыкания Клини языка $L$. Решив сэкономить, Петя просто провёл $\varepsilon$-переход из каждого терминального состояния в начальное состояние, и сделал начальное состояние также терминальным. Всегда ли у Пети получится то, что нужно?
# Докажите нерегулярность языка палиндромов, если алфавит содержит хотя бы два символа. Что если алфавит унарный?
# Докажите нерегулярность языка тандемных повторов $L = \{ ww | w \in \Sigma^* \}$, если алфавит содержит хотя бы два символа. Что если алфавит унарный?
# Докажите нерегулярность языка $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$
# Приведите пример нерегулярного языка, для которого выполнена лемма о разрастании
# Обозначим как $\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_1a_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=\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$ имеет неполиномиальный размер.
# Вспомните/узнайте определение моноида. Почему конструкция из задания 183 названа моноидом, опишите группоидную операцию для нее.
# Постройте КС грамматику для правильных скобочных последовательностей с двумя типами скобок. В этом и следующих заданиях, после разработки КС грамматики необходимо выбрать в качестве примера слово и продемонстрировать его левосторонний вывод и дерево разбора.
# Постройте КС грамматику для языка $0^k 1^n 2^{k+n}$.
# Постройте КС грамматику для языка $0^n 1^m 2^m 3^n$.
# Постройте КС грамматику для языка $0^n 1^n 2^m 3^m$.
# (кроме 35, 34, 31) Докажите, что КС языки замкнуты относительно регулярных операций (объединение, конкатенация, замыкание Клини)
# Пусть задана КС-грамматика для языка $L$. Обозначим как $L^R$ язык, составленный из слов, которые, если их прочитать от конца к началу, принадлежат языку $L$. Укажите, как построить КС грамматику для языка $L^R$.
# Обозначим как $\mbox{pref}\,L$ множество префиксов слов языка $L$. Докажите, что если $L$ контекстно-свободный, то и $\mbox{pref}\,L$ контекстно-свободный.
# Постройте КС грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей равно числу единиц. Докажите, что ваша грамматика является правильной.
# Постройте КС грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей равно удвоенному числу единиц. Докажите, что ваша грамматика является правильной.
# Постройте КС грамматику для языка $0^i1^j2^k$, $i \ne j$ или $j \ne k$.
# Постройте КС грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются палиндромами.
# Постройте КС грамматику для языка слов над алфавитом $\{(, )\}$, которые не являются правильными скобочными последовательностями.
# Постройте КС грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей не равно числу единиц.
# Постройте КС грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются тандемными повторами (не имеют вид $xx$ для некоторого слова $x$).
# Постройте КС грамматику, описывающие академические регулярные выражения над алфавитом $\{0, 1\}$.
# КС грамматика называется линейной, если в правых частях правил встречается максимум один нетерминал. Праволинейные грамматики, в которых этот нетерминал находится на последнем месте, порождают регулярные языки. Приведите пример линейной грамматики, которая порождает нерегулярный язык.
# КС грамматика называется леволинейной, если в правых частях правил встречается максимум один нетерминал, причем если он есть, то находится на первом месте. Докажите, что язык можно породить леволинейной грамматикой тогда и только тогда, когда он регулярный.
# КС грамматика называется смешанной линейной, если в правых частях правил встречается максимум один нетерминал, причем если он есть, то находится либо на первом, либо на последнем месте. Докажите, что существует КС язык, не являющийся регулярным, который можно породить смешанной линейной грамматикой.
