129
правок
Изменения
м
Нет описания правки
}}
===Гомоморфизмы ======= [[Основные определения, связанные со строками#Гомоморфизм языков | Прямой и обратный гомоморфизмыгомоморфизм]] ====
{{ Утверждение
}}
==== [[Основные определения, связанные со строками#Гомоморфизм языков | Обратный гомоморфизм]] ====
{{ Утверждение
|statement= КС-языки замкнуты относительно [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками#Гомоморфизм языков|обратного гомоморфизма]].
{{ Утверждение
|statement= <tex> L^{R} = \{ w^{R} \mid w \in L \}</tex> контекстно-свободнасвободен.
|proof=
Для того, чтобы построить <tex> L^{R} </tex>, необходимо развернуть все правые части правил грамматики для <tex> L </tex>.
|statement= Если <tex> L_1 = a^i b^i c^j , L_2 = a^i b^j c^j </tex>, то <tex> L_1 \cap L_2 </tex> не является КС-языком.
|proof=
<tex> L_1 = \{ a^i b^i \} \cdot \{ c^j \}, L_2 = \{ a^i \} \cdot \{ b^j c^j \} </tex>
По замкнутости КС-языков относительно конкатенации получаем, что <tex> L_1 </tex> и <tex> L_2 </tex> являются КС-языками.
Но <tex> L_1 \cap L_2 = \{ a^i b^i c^i \mid i \in \mathbb{N} \} </tex>, что который по [[Лемма о разрастании для КС-грамматик|лемме о разрастании]] для КС-языков не является КС-языком.
}}
{{ Утверждение
