Изменения

# Пусть $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)$ также КС.# Докажите или опровергните, что язык является контекстно-свободным: $0^a1^b2^a$, $a=2b$# Докажите или опровергните, что язык является контекстно-свободным: $0^a1^b2^a$, $2a=b$# Докажите или опровергните, что язык является контекстно-свободным: $0^a1^b2^a$, $a\ne 2b$# Докажите или опровергните, что язык является контекстно-свободным: $0^a1^b2^a$, $2a\ne b$# Рассмотрим список слов $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$.# Постройте МП-автомат для языка $0^n1^n$.# Постройте МП-автомат для языка слов, где число нулей равно числу единиц.# Постройте МП-автомат для языка $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\}$, которые содержат равное число двоек и равное число единиц, или равное число двоек и равное число нулей.# Предложите алгоритм проверки, что МП-автомат допускает заданное слово.# Назовем состояние МП-автомата бесполезным если автомат не может перейти в него ни при каком входном слове. Предложите алгоритм проверки состояния МП-автомата на бесполезность.# Предложите алгоритм проверки, что МП-автомат допускает хотя бы одно слово, содержащее заданное в качестве подстроки.# Предложите алгоритм проверки, что МП-автомат допускает бесконечное число слов.