55
правок
Изменения
Нет описания правки
# Приведите пример не КС-языка, для которого выполнена лемма о разрастании.
# Приведите пример КС-языка, не являющегося регулярным, дополнение к которому также является КС.
# Приведите пример двух КС-языкаязыков, не являющихся регулярными, пересечение которых также является КС, но не регулярным, причем отлично от обоих пересекаемых языков.
# Пусть $f : \Sigma \to \Sigma^*$ - функция, сопоставляющая каждому символу некоторую строку. Распространим $f$ на слова следующим образом: $f(c_1c_2\ldots c_k) = f(c_1)f(c_2)\ldots f(c_k)$. Обозначим как $f(L)$ множество слов $f(x)$ для всех $x \in L$. Докажите или опровергните, что если $L$ - КС, то $f(L)$ также КС.
# Пусть $f : \Sigma \to \Sigma^*$ - функция, сопоставляющая каждому символу некоторую строку. Распространим $f$ на слова следующим образом: $f(c_1c_2\ldots c_k) = f(c_1)f(c_2)\ldots f(c_k)$. Обозначим как $f^{-1}(L)$ множество таких слов $x$, для которых $f(x) \in L$. Докажите или опровергните, что если $L$ - КС, то $f^{-1}(L)$ также КС.
