Изменения
Нет описания правки
# Петя строит автомат для объединения языков $L_1$ и $L_2$ из автоматов для этих языков. Решив сэкономить, Петя просто объединил в одно начальные состояния автоматов для $L_1$ и $L_2$. Всегда ли у Пети получится то, что нужно?
# Петя строит автомат для замыкания Клини языка $L$. Решив сэкономить, Петя просто провёл $\varepsilon$-переход из каждого терминального состояния в начальное состояние, и сделал начальное состояние также терминальным. Всегда ли у Пети получится то, что нужно?
# Для символа $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$, (г) $aa^{-1}L=L$.
# Пусть $R$ и $S$ - регулярные языки. Выразите $(RS)a^{-1}$ через $R$, $S$, $Ra^{-1}$ и $Sa^{-1}$. Указание: рассмотрите два случая: $\varepsilon \in S$ или $\varepsilon \not\in S$.
# Докажите нерегулярность языка, каждое слово которого содержит поровну 0 и 1.
# Докажите нерегулярность языка палиндромов.
# Докажите нерегулярность языка тандемных повторов.
# Докажите нерегулярность языка $0^n1^m$, $n \le m$
# Докажите нерегулярность языка $0^n1^m$, $n \ne m$
# Докажите нерегулярность языка $0^{n^2}$
# Докажите нерегулярность языка $0^p$, $p$ {{---}} простое
# Докажите нерегулярность языка двоичных записей простых чисел
# Докажите нерегулярность языка $0^n1^m$, $gcd(n, m) = 1$
# Докажите нерегулярность языка $0^a1^b2^c$, $a \ne b$ и $b \ne c$
# Приведите пример нерегулярного языка, для которого выполнена лемма о разрастании
# Из алгоритма построения множества различимых состояний следует, что $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n^2)$. Докажите, что если состояния $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n)$.
