62
правки
Изменения
→Гомоморфизмы
|statement= КС-языки замкнуты относительно прямого гомоморфизма.
|proof=
Построим КС-грамматику, в которой каждый символ <tex> x \in \Sigma </tex> заменим на <tex> \mathrm{h}(x) </tex>.
}}
|proof=
[[Файл:Homo.png|300px|right|frameless]]
Докажем аналогично соответствующему утверждению для регулярных языков. Построим [[Автоматы с магазинной памятью|МП-автомат]] для <tex> \mathrm{h^{-1}}(L) = \{ w \mid \mathrm{h}(w) \in L \} </tex> на основе МП-автомата для языка <tex> L </tex> (назовем его <tex> M </tex>). Новый автомат <tex> M' </tex> будет действовать следующим образом:
# Если входное слово закончилось, допускаем или не допускаем его [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность|по допускающему состоянию]].
# Считываем символ <tex> c </tex>.
# Сохраняем <tex> \mathrm{h}(c) </tex> в буфере (входная лента для автомата <tex> M </tex>).
# Запускаем <tex> M </tex> на слове, находящемся в буфере.
# После того, как <tex> M </tex> обработал весь буфер, переходим к пункту 1.
* <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, \mathrm{h}(c)), X) \mid c \in \Sigma, q \in Q, X \in \Gamma \}</tex>. Когда буфер пуст, <tex> M' </tex> может прочитать свой следующий входной символ <tex> c </tex> и поместить <tex> \mathrm{h}(c) </tex> в буфер.
** Если <tex> (p, \gamma) \in \delta(q, b, X), b \in T \cup \varepsilon </tex>, то <tex> ((p, x), \gamma) \in \delta'((q, bx), \varepsilon, X) </tex>. Таким образом, <tex> M' </tex> всегда имеет возможность имитации перехода <tex> M </tex>, используя голову буфера. Если <tex> b \in T </tex>, то буфер должен быть непустым, но если <tex> b = \varepsilon </tex>, то буфер может быть пустым.
* Начальным состоянием <tex> M' </tex> является <tex> (s, \varepsilon) </tex>, т.е. <tex> M' </tex> стартует в начальном состоянии <tex> M </tex> с пустым буфером.
* Допускающими состояниями <tex> M' </tex> являются состояния <tex> (q, \varepsilon)</tex>, где <tex> q \in T </tex>.
Таким образом получаем, что <tex>(s, \mathrm{h}(w), Z_0) \vdash_M^{*} (p, \varepsilon, \gamma) \Leftrightarrow ((s, \varepsilon), w, Z_0) \vdash_{M'}^{*} ((p, \varepsilon), \varepsilon, \gamma)</tex>, то есть автомат <tex> M' </tex> допускает те и только те слова, которые принадлежат языку <tex> \mathrm{h^{-1}}(L) </tex>.
}}
=== Разворот ===
