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