Изменения

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

Список заданий по ДМ 2018 весна

3750 байт добавлено, 12:30, 18 марта 2018
Нет описания правки
# Постройте регулярную Марковскую цепь с двумя состояниями и эргодическим распределением $[a, 1-a]$ для заданного $a$.
# Постройте регулярную Марковскую цепь с $n$ состояниями и заданным эргодическим распределением.
# Пусть $L$ - формальный язык. Докажите, что $(L^*)^* = L^*$
# Пусть $R$ и $S$ - языки. Докажите или опровергните, что $(R \cup S)^* = R^* \cup S^*$.
# Пусть $R$ и $S$ - языки. Докажите или опровергните, что $(R \cap S)^* = R^* \cap S^*$.
# Пусть $R$ и $S$ - языки. Докажите или опровергните, что $(R \cup S)^* = (R^*S^*)^*$.
# Пусть $R$ и $S$ - языки. Обозначим как $RS$ язык слов, представимых в виде конкатенации слова из $R$ и слова из $S$ (в этом порядке). Докажите, что $(R\cup S)T=RT \cup ST$, $(R\cap S)T=RT \cap ST$.
# Пусть $L$ - язык. Обозначим как $Lc$ язык, который получается из $L$ дописыванием в конец каждому слову символа $c$. Обозначим как $Lc^{-1}$ язык, который получается из $L$ откидыванием всех слов, которые не заканчиваются на $c$, а затем у оставшихся слов откидыванием конечного символа $c$. Докажите или опровергните, что $(Lc)c^{-1}=L$, $(Lc^{-1})c=L$.
# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых четность числа 0 равна четности числа 1
# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3
# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей не кратно 3. Сделайте вывод из последних двух заданий.
# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых нет трех нулей подряд
# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых есть три нуля подряд
# Постройте конечный автомат для языка слов над бинарным алфавитом, которые представляют собой двоичную запись чисел, кратных 5
# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3 и которые представляют собой двоичную запись чисел кратных 5.
# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3 или которые представляют собой двоичную запись чисел кратных 5. Сделайте вывод из последних двух заданий.
# Постройте конечный автомат для языка слов над бинарным алфавитом, в которых число единиц кратно 3. Сделайте вывод.
# Постройте детерминированный конечный автомат для языка слов над бинарным алфавитом, в которых второй символ с конца равен последнему символу.
Анонимный участник

Навигация