Изменения

В случае с прямым гомоморфизмом всё просто: строится КС-грамматика, в которой каждый символ <tex> x \in \Sigma </tex> заменяется на <tex> h(x) </tex>. Для обратного гомоморфизма можно построить [[Автоматы с магазинной памятью|МП-автомат]] для <tex> h^{-1}(L) </tex> на основе МП-автомата для языка <tex> L </tex> (назовем его <tex> M </tex>). Считаем, что <tex> M </tex> допускает слова [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность|по пустому стеку]]. Новый автомат будет действовать следующим образом:

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

Пусть в автомате <tex> M </tex> было <tex> n </tex> состоянийдальше будет. Для того, чтобы научиться сохранять слова в буфере, создадим <tex> |\Sigma|^{k+1} n </tex> дополнительных состояний в новом автомате, где <tex> k = \max\limits_{c \in \Sigma} | h(c) | </tex>завтра. Это позволит в состоянии кодировать словоточнее уже сегодня, которое находится сейчас в буфереага. Переходы в этих состояниях совершаются на основе того, что стоит на первом месте в буфере, состояния автомата и вершины стека. На ленту переходы в этих состояниях не смотрят. Из состояния, в котором буфер пуст, добавим <tex> \varepsilon </tex>-переход в начальное состояние. Необходима И картинка.тоже :)