Изменения

В случае с [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками|прямым гомоморфизмом ]] всё просто: строится КС-грамматика, в которой каждый символ <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> будет действовать следующим образом: