В случае с прямым гомоморфизмом всё просто: строится КС-грамматика, в которой каждый символ <tex> x \in \Sigma </tex> заменяется на <tex> h(x) </tex>.
Если <tex> h </tex> — гомоморфизм, а <tex> L </tex> — произвольный язык, то <tex> h^{-1}(L) = \{ w \mid h(w) \in L \} </tex>. Для доказательства замкнутости обратного гомоморфизма будем делать аналогично [[Замкнутость регулярных языков относительно различных операций|доказательству]] для регулярных языков. Построим [[Автоматы с магазинной памятью|МП-автомат]] для <tex> h^{-1}(L) = \{ w \mid h(w) \in L \} </tex> на основе МП-автомата для языка <tex> L </tex> (назовем его <tex> M </tex>). Считаем, что <tex> M </tex> допускает слова [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность|по пустому стеку]]. Новый автомат будет действовать следующим образом:
# Если входное слово закончилось, допускаем или не допускаем его по пустому стеку.
# После того, как <tex> M </tex> обработал весь буфер, переходим к пункту 2.
дальше будетЕсли рассмотреть более формально, пусть <tex> M =\langle Q, \Sigma, \Gamma, \delta, s, Z_{0}, T\rangle </tex>, тогда <tex> M' =\langle Q', \Sigma, \Gamma, \delta', (s, \varepsilon), Z_{0}, T \times {\varepsilon}\rangle</tex>. завтра* <tex> Q' = \{ (q, x) \mid q \in Q \} </tex>, где <tex> x </tex> — суффикс (не обязательно собственный) некоторой цепочки <tex> h(c) </tex> для символа <tex> c \in \Sigma </tex>. точнее уже сегодняТаким образом, агапервый компонент состояния <tex> M' </tex> является состоянием <tex> M </tex>, а второй — компонентом буфера. И картинка тоже * <tex> \delta' </tex> определяется следующими правилами:а) <tex> \delta'((q, \varepsilon), c, X) = \{((q, h(c)), X) \mid c \in \Sigma, q \in Q, X \in \Gamma \}</tex>. Когда буфер пуст, <tex> M' </tex> может прочитать свой следующий входной символ <tex> c </tex> и поместить <tex> h(c) </tex> в буфер. б) если δ(q, b, X) содержит (p, γ), где b ∈ T или b = ε, то δ′((q, bx), ε, X) содержит ((p, x), γ). Таким образом, P′ всегда имеет возможность имитации перехода P,используя голову буфера. Если b ∈ T, то буфер должен быть непустым, но если b = ε, то буфер может быть пустым.* начальным состоянием P′ является (q0, ε), т.е. P′ стартует в начальном состоянии P с пустым буфером.* Аналогично, допускающими состояниями P′ являются такие состояния (q, ε), у которых q — допускающее состояние P. Следующее утверждение характеризует взаимосвязь P′ и P.
=== Разворот ===
