222
правки
Изменения
→Прямой и обратный гомоморфизм
=== Прямой и обратный гомоморфизм ===
[[Файл:Homo.png|300px|thumb|]]
В случае с прямым гомоморфизмом всё просто: строится КС-грамматика, в которой каждый символ <tex> x \in \Sigma </tex> заменяется на <tex> h(x) </tex>.
Для доказательства замкнутости обратного гомоморфизма будем делать аналогично [[Замкнутость регулярных языков относительно различных операций|доказательству]] для регулярных языков. Построим [[Автоматы с магазинной памятью|МП-автомат]] для <tex> h^{-1}(L) = \{ w \mid h(w) \in L \} </tex> на основе МП-автомата для языка <tex> L </tex> (назовем его <tex> M </tex>). Считаем, что Новый автомат <tex> M ' </tex> допускает слова [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность|по пустому стеку]]. Новый автомат будет действовать следующим образом:
# Если входное слово закончилось, допускаем или не допускаем его [[МП-автоматы, допуск по пустому стекуи по допускающему состоянию, эквивалентность|по допускающему состоянию]].
# Иначе считываем символ <tex> c </tex>.
# Сохраняем <tex> h(c) </tex> в буфере.
