Изменения

=== [[Основные определения, связанные со строками#Гомоморфизм языков | Прямой и обратный гомоморфизмы]] ===

{{ Утверждение

|statement= КС-языки замкнуты относительно прямого гомоморфизма.

Построим КС-грамматику, в которой каждый символ <tex> x \in \Sigma </tex> заменим на <tex> h(x) </tex>.

}}

{{ Утверждение

|statement= КС-языки замкнуты относительно [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками#Гомоморфизм языков|обратного гомоморфизма]]

|proof=

Докажем аналогично соответствующему утверждению для регулярных языков. Построим [[Автоматы с магазинной памятью|МП-автомат]] для <tex> h^{-1}(L) = \{ w \mid h(w) \in L \} </tex> на основе МП-автомата для языка <tex> L </tex> (назовем его <tex> M </tex>). Новый автомат <tex> M' </tex> будет действовать следующим образом: