Изменения
Нет описания правки
# Постройте конечный автомат для языка слов над бинарным алфавитом, которые содержат подстроку 01001.
# Постройте конечный автомат для языка слов, которые содержат заданную подстроку $s$.
# Постройте недетерминированный автомат для языка слов над бинарным алфавитом, в которых $k$-й символ с конца равен 0, содержащий $\O(k)$ состояний.
# Докажите, что любой детерминированный автомат для языка слов над бинарным алфавитом, в которых $k$-й символ с конца равен 0, содержит $\Omega(2^k)$ состояний.
# Можно ли обобщить два предыдущих задания для любого размера алфавита $c$ следующим образом: построить семейство языков, для которых будут существовать НКА, содержащий $O(k)$ состояний, но любые ДКА будут содержать $\Omega(c^k)$ состояний?
