Изменения
Нет описания правки
# Предложите алгоритм получения следующего по номеру в лексикографическом порядке разбиения множества $\{1, \ldots, n\}$ на множества. Множества в каждом разбиении упорядочиваются лексикографически по представлениям в виде возрастающего списка элеметов. Разбиения далее упорядочиваются лексикографически как списки множеств.
# Предложите алгоритм получения следующего по номеру в лексикографическом порядке разбиения множества $\{1, \ldots, n\}$ на множества. Множества в каждом разбиении упорядочиваются лексикографически как битовые вектора. Разбиения далее упорядочиваются лексикографически как списки множеств.
# Построить Постройте конечный автомат для языка слов над бинарным алфавитом, в которых четность числа 0 равна четности числа 1# Построить Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3# Построить Постройте конечный автомат для языка слов над бинарным алфавитом, в которых нет трех нулей подряд# Построить Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой двоичную запись чисел, кратных 5# Построить Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей не кратно 3# Построить Постройте конечный автомат для языка слов над бинарным алфавитом, в которых есть три нуля подряд. Сделайте вывод из последних двух заданий.# Построить Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3 и которые представляют собой двоичную запись чисел кратных 5.# Построить Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3 или которые представляют собой двоичную запись чисел кратных 5. Сделайте вывод из последних двух заданий.# Построить Постройте конечный автомат для языка слов над бинарным алфавитом, в пятый символ с конца - 0. Можно построить недетерминированный автомат.
# Постройте детерминированный автомат для предыдущего задания или докажите, что в нем слишком много состояний, чтобы его рисовать ;).
# Постройте регулярное выражение для языка слов над бинарным алфавитом, в которых нет двух нулей подряд.
# Построить Постройте регулярное выражение для языка слов над бинарным алфавитом, в которых число 0 кратно 3.# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых нет трех одинаковых символов подряд.# Постройте конечный автомат для языка слов над бинарным алфавитом, которые заканчиваются на 01001.# Постройте конечный автомат для языка слов над бинарным алфавитом, которые содержат подстроку 01001.# Постройте конечный автомат для языка слов, которые содержат заданную подстроку $s$.# Постройте недетерминированный автомат для языка слов над бинарным алфавитом, в которых $k$-й символ с конца равен 0, содержащий $\O(k)$ состояний. # Докажите, что любой детерминированный автомат для языка слов над бинарным алфавитом, в которых $k$-й символ с конца равен 0, содержит $\Omega(2^k)$ состояний. # Можно ли обобщить два предыдущих задания для любого размера алфавита $c$ следующим образом: построить семейство языков, для которых будут существовать НКА, содержащий $O(k)$ состояний, но любые ДКА будут содержать $\Omega(c^k)$ состояний?# Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой развернутую двоичную запись чисел кратных 5 (сначала на вход подаются младшие разряды).# Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой развернутую двоичную запись чисел кратных 6 (сначала на вход подаются младшие разряды).# Рассмотрим язык $\{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 \}$.
</wikitex>
