113
правок
Изменения
Нет описания правки
# ХМУ 9.4.3
# ХМУ 9.4.4
# Пусть $a = (a_1, a_2, ..., a_n)$ - список слов над алфавитом $\Sigma$. Обозначим как La $L_a$ множество слов над алфавитом $\Sigma \union cup \{[1], [2], ..., [n]\}$, которые порождаются грамматикой $S -> ai \rightarrow a_i S [i]$, $S -> eps\rightarrow \varepsilon$. Докажите, что дополнения языку La $L_a$ является КС-языком. Указание: постройте соответствующий МП-автомат
# Докажите, что проблема пустоты пересечения языков двух КС-грамматик неразрешима
# Докажите, что проблема равенства языков двух КС-грамматик неразрешима