Изменения
Нет описания правки
# Реализуйте на МТ сравнение двух чисел (числа в двоичном формате) а) б)
# Докажите, что если на МТ можно реализовать функцию f и функцию g, то можно реализовать функцию f(g)
# ХМУ 9.4.1 а
# ХМУ 9.4.1 б
# ХМУ 9.4.1 в
# ХМУ 9.4.2
# ХМУ 9.4.3
# Пусть $a = (a_1, a_2, ..., a_n)$ - список слов над алфавитом Sigma. Обозначим как La множество слов над алфавитом Sigma \union {[1], [2], ..., [n]}, которые порождаются грамматикой S -> ai S [i], S -> eps. Докажите, что дополнения языку La является КС-языком. Указание: постройте соответствующий МП-автомат
# Докажите, что проблема пустоты пересечения языков двух КС-грамматик неразрешима
# Докажите, что проблема равенства языков двух КС-грамматик неразрешима
# Докажите, что проблема равенства языка КС-грамматики и регулярного языка неразрешима
# Докажите, что проблема пустоты дополнения КС-языка неразрешима
# Докажите, что проблема включения одного КС-языка в другой неразрешима
# ХМУ, стр 418, 9.5.1
# ХМУ, стр 418, 9.5.2
# ХМУ, стр 418, 9.5.3
</wikitex>
