1632
правки
Изменения
м
rollbackEdits.php mass rollback
# Верно ли, что любую КС-грамматику можно привести к форме, когда любое правило имеет вид $A\to BCD$ или $A\to a$?
# Верно ли, что любой КС-язык над односимвольным алфавитом является регулярным?
# Докажите, что язык не является КС: $0^i1^j2^k$, $i<j<k$.
# Докажите, что язык не является КС: $0^n1^n2^k$, $k<n$.
# Докажите, что язык не является КС: $0^p$, $p$ простое.
# Докажите, что язык двоичных записей простых чисел не является КС.
# Докажите, что язык не является КС: $0^i1^j$, $j=i^2$.
# Докажите, что язык не является КС: $0^n1^n2^k$, $n<k<2n$.
# Докажите, что язык не является КС: $ww^Rw$, $w$ - строка из 0 и 1, $w^R$ - развернутая строка $w$.
# Докажите, что язык $\{0^n1^m2^n3^m\}$ не является КС.
# Докажите, что язык $\{0^n1^m2^n| n \ne m\}$ не является КС.
# Приведите пример не КС-языка, для которого выполнена лемма о разрастании.
# Постройте МП-автомат для языка $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\}$, которые содержат равное число двоек и равное число единиц, или равное число двоек и равное число нулей.
</wikitex>
