Изменения

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

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

4 байта добавлено, 17:40, 11 апреля 2018
Нет описания правки
# Для символа $a$ обозначим как $La^{-1}$ множество слов $w$, таких что $wa \in L$. Докажите, что если $L$ регулярный, то $La^{-1}$ регулярный.
# Для символа $a$ обозначим как $a^{-1}L$ множество слов $w$, таких что $aw \in L$. Докажите, что если $L$ регулярный, то $a^{-1}L$ регулярный.
# Докажите или опровергните утверждения: (а) $Laa^{-1}=L$, (б) $La^{-1}a=L$, (в) $a^{-1}(aL)=L$, (г) $aaa(a^{-1}L)=L$.
# Пусть $R$ и $S$ - регулярные языки. Выразите $(RS)a^{-1}$ через $R$, $S$, $Ra^{-1}$ и $Sa^{-1}$. Указание: рассмотрите два случая: $\varepsilon \in S$ или $\varepsilon \not\in S$.
# Докажите нерегулярность языка, каждое слово которого содержит поровну 0 и 1.
Анонимный участник

Навигация