Изменения
Нет описания правки
# Предложите алгоритм проверки того, что объединение двух заданных регулярных языков совпадет с некоторым третьим заданным.
# Приведите пример регулярного языка и двух неизоморфных недетерминированных автоматов для него, которые при этом имеют минимальное число состояний среди всех недетерминированных автоматов для этого языка.
# Петя строит автомат для конкатенации языков $L_1$ и $L_2$ из автоматов для этих языков. Оказалось, что автомат для $L_1$ содержит только одно терминальное состояние и Петя просто объединил в одно это состояние и начальное состояние автомата для $L_2$. Всегда ли у Пети получится то, что нужно?
# Петя строит автомат для объединения языков $L_1$ и $L_2$ из автоматов для этих языков. Решив сэкономить, Петя просто объединил в одно начальные состояния автоматов для $L_1$ и $L_2$. Всегда ли у Пети получится то, что нужно?
# Петя строит автомат для замыкания Клини языка $L$. Решив сэкономить, Петя просто провёл $\varepsilon$-переход из каждого терминального состояния в начальное состояние, и сделал начальное состояние также терминальным. Всегда ли у Пети получится то, что нужно?
# Обозначим как $\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_2a_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$: $x \equiv y$, если для любых $u$, $v$ выполнено $uxv \in L \Leftrightarrow uyv \in L$. Классы эквивалентности этого отношения называются синтаксическим моноидом языка $L$. Докажите, что $L$ регулярный тогда и только тогда, когда синтаксический моноид $L$ конечен.
# Придумайте семейство регулярных языков $L_i$, у которых ДКА для $L_i$ содержит $O(i)$ состояний, а синтаксический моноид $L_i$ имеет неполиномиальный размер.
