Изменения
Нет описания правки
# Для КС-языка $L$ существует число $n$, что любое слово $w \in L$, $|w| \ge n$ можно разбить на четыре части $w = vxyz$, где $|vxy| \le n$, $vy \neq \varepsilon$, что для любого $k \ge 0$, $v^kxy^kz \in L$.
# Докажите, что следующая модификация леммы о разрастании верна: Для КС-языка $L$ существует число $n$, что любое слово $w \in L$, $|w| \ge n$ можно разбить на пять частей $w = uvxyz$, где $|vxy| \le n$, $v \neq \varepsilon$, $y \neq \varepsilon$ что для любого $k \ge 0$, $uv^kxy^kz \in L$.
# Постройте МП-автомат для языка слов, где число нулей равно числу единиц.
# Постройте МП-автомат для языка $0^n1^{2n}$.
# Постройте МП-автомат для языка $0^n1^m2^{n+m}$.
# Постройте МП-автомат для языка $0^{2n}1^n$.
# Постройте МП-автомат для языка $0^n1^n\cup0^n1^{2n}$.
# Постройте МП-автомат для языка слов $0^n1^m$, где $n \le m \le 2n$.
# Докажите, что для любых $p$ и $q$ существует МП-автомат для языка слов $0^n1^m$, где $n/m=p/q$
# Постройте автомат с магазинной памятью для языка слов над алфавитом $\{0, 1, 2\}$, которые содержат равное число двоек и равное число единиц, или равное число двоек и равное число нулей.
# Рассмотрим список слов $A = \{\alpha_1, \alpha_2, \ldots, \alpha_n\}$ над алфавитом $\Sigma$. Введем $n$ новых различных символов $d_1, d_2, \ldots, d_n$. Рассмотрим алфавит $\Sigma' = \Sigma \cup \{d_1, d_2, \ldots, d_n\}$. Рассмотрим язык списка $A$, обозначаемый как $L_A$, в который входят все слова вида $\alpha_{i_1}\alpha_{i_2}\ldots\alpha_{i_k}d_{i_k}d_{i_{k-1}}\ldots d_{i_1}$. Докажите, что для любого списка $A$ язык $L_A$ является контекстно-свободным.
# Докажите, что дополнение к языку списка $L_A$ является контекстно-свободным для любого списка $A$.
# Можно неправильно определить язык списка $A = \{\alpha_1, \alpha_2, \ldots, \alpha_n\}$ из предыдущего задания, составив его из слов вида $\alpha_{i_1}\alpha_{i_2}\ldots\alpha_{i_k}d_{i_1}d_{i_2}\ldots d_{i_k}$. Докажите или опровергните, что при таком неправильном определении язык списка все еще будет конткстно-свободным для любого списка $A$.
# Предложите алгоритм проверки, что МП-автомат допускает заданное слово.
# Назовем состояние МП-автомата бесполезным, если автомат не может перейти в него ни при каком входном слове. Предложите алгоритм проверки состояния МП-автомата на бесполезность.
# Предложите алгоритм проверки, что МП-автомат допускает хотя бы одно слово, содержащее заданное в качестве подстроки.
# Предложите алгоритм проверки, что МП-автомат допускает бесконечное число слов.
# Пусть $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)$ также КС.
