Изменения

Построим [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]] для языка <tex> L_1 \cup L_2 </tex>. Для этого рассмотрим соответствующие КС-грамматики для языков <tex> L_1 </tex> и <tex> L_2 </tex>. Пусть стартовые символы в них имеют имена <tex> S </tex> и <tex> T </tex> соответственно. Тогда стартовый символ для <tex> L_1 \cup L_2 </tex> обозначим за <tex> S' </tex> и добавим правило <tex> S' \to S\,|\,mid T </tex>.

Покажем, что <tex> S' \Rightarrow^{*} w \iff S \Rightarrow^{*} w \lor T \Rightarrow^{*} w </tex>. В левую сторону: поскольку <tex> S \Rightarrow^{*} w </tex> и есть правило <tex> S' \to S </tex>, то, по определению <tex> \Rightarrow^{*} </tex> получаем, что <tex> S' \Rightarrow^{*} w </tex>. Аналогично и для <tex> T </tex>.

В обратную сторону<tex>\Rightarrow</tex>: Поскольку <tex> S \Rightarrow^{*} w </tex> и есть правило <tex> S' \to S </tex>, то, по определению <tex> \Rightarrow^{*} </tex> получаем, пусть что <tex> S' \Rightarrow^{*} w </tex>. Аналогично и для <tex> T </tex>. <tex>\Leftarrow </tex>: Пусть <tex> S' \Rightarrow^{*} w </tex>. Поскольку <tex> S' \to S\,|\,mid T </tex> — единственные правила, в которых нетерминал <tex> S' </tex> присутствует в правой части, то это означает, что либо <tex> S' \Rightarrow S \Rightarrow^{*} w </tex>, либо <tex> S' \Rightarrow T \Rightarrow^{*} w </tex>, что и требовалось доказать.

|proof=Если <tex> S </tex> — стартовый символ КС-грамматики для языка <tex> L </tex>, то добавим в КС-грамматику для языка <tex> L^{*} </tex> новый стартовый символ <tex> S' </tex> и правила <tex> S' \to S S' \, | \, mid \varepsilon </tex>.

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

[[Файл:Homo{{ Утверждение|statement= КС-языки замкнуты относительно прямого гомоморфизма.png|300px|thumb|]]proof=Построим КС-грамматику, в которой каждый символ <tex> x \in \Sigma </tex> заменим на <tex> \mathrm{h}(x) </tex>. }}

В случае с ==== [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языкамисвязанные со строками#Гомоморфизм языков|прямым гомоморфизмомОбратный гомоморфизм]] всё просто: строится ===={{ Утверждение|statement= КС-грамматика, в которой каждый символ <tex> x \in \Sigma </tex> заменяется на <tex> 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> \mathrm{h}(c) </tex> в буфере (входная лента для автомата <tex> M </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>(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>.}}

Для того, чтобы построить КС-грамматику для языка {{ Утверждение|statement= <tex> L^{R} = \{ w^{R} \mid w \in L \}</tex> контекстно-свободен.|proof= Для того, чтобы построить <tex> L^{R} </tex>, необходимо развернуть все правые части правил грамматики для <tex> L </tex>.

Покажем, что <tex>w \in L \iff w^{R} \in L^{R}</tex>. Докажем (<tex>\Rightarrow</tex>) индукцией по длине порождения в грамматике <tex>L</tex>. В обратную сторону (<tex>\Leftarrow</tex>) рассуждения аналогичны.

<tex>\Rightarrow</tex>:Докажем с помощью метода математической индукции по длине порождения в грамматике <tex>L</tex>.:'''База'''. <tex>A \underset{L}{\Rightarrow} w</tex>.

:: В грамматике <tex>L</tex> существует правило <tex>A \rightarrow w</tex> и, так как мы развернули все правые части правил, то <tex>A \underset{L^{R}}{\Rightarrow} w^{R}</tex>.

:'''Предположение индукции'''. Пусть <tex>A \underset{L}{\Rightarrow}^* w</tex> менее чем за <tex>n</tex> шагов, тогда <tex>A \underset{L^{R}}{\Rightarrow}^* w^{R}</tex>.

:'''Переход'''. :: Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A \underset{L}{\Rightarrow}Y_1 Y_2...\ldots Y_m \underset{L}{\Rightarrow}^*w</tex>, где <tex> Y_i \in N \cup \Sigma </tex>. Цепочку <tex> w </tex> можно разбить на <tex>w_1 w_2...\ldots w_m</tex>, где <tex> Y_i \underset{L}{\Rightarrow}^*w_i</tex>. Так как каждое из порождений <tex> Y_i \underset{L}{\Rightarrow}^*w_i </tex> содержит менее <tex> n </tex> шагов, к ним можно применить предположение индукции и заключить, что <tex> Y_i \underset{L^{R}}{\Rightarrow}^*w_i^{R} </tex>. Так как <tex>A \underset{L}{\Rightarrow}Y_1 Y_2...\ldots Y_m</tex>, то <tex>A \underset{L^{R}}{\Rightarrow}Y_m Y_{m - 1}...\ldots Y_1</tex>, откуда следует, что <tex> A \underset{L^{R}}{\Rightarrow}^* w^{R} </tex>.

|statement= Язык тандемных повторов <tex> L = \{ww \mid w \in \Sigma^{*} \} </tex> не является КС-языком, однако .|proof=Это доказывается с помощью [[Лемма о разрастании для КС-грамматик|леммы о разрастании]]. }}{{ Утверждение|statement= Дополнение к языку тандемных повторов <tex> \overline{L} </tex> — является КС-языкязыком.

<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>, что который по [[Лемма о разрастании для КС-грамматик|лемме о разрастании]] для КС-языков не является КС-языком.

Для === Разность ==={{ Утверждение|statement= КС-языки не замкнуты относительно разности достаточно заметить, что .|proof=<tex> L_1 \overline{L} setminus L_2 = L_1 \Sigma^cap \overline{*L_2} \setminus L </tex>, поэтому разность КС-языков также необязательно является КС-языком.

=== Примеры других операций Половины тандемных повторов ===

{{ Утверждение|statement= Операция <tex> \mathrm{half} </tex> также не сохраняет КС-язык таковым. |proof= Покажем это на примере. Рассмотрим язык <tex> L = \{ a^n b a^n b a^m b a^l b a^k b a^k b \} </tex>.

{{УтверждениеТем не менее, хоть пересечение двух КС-языков не обязательно является КС-языком, но пересечение |statement = Пересечение КС-языка и [[Регулярные языки: два определения и их эквивалентность|регулярного языка]] — всегда КС-язык. Для доказательства этого построим |proof = Построим МП-автомат для пересечения регулярного языка и КС-языка.

Разность КС-языка и регулярного языка выражается следующим образом: <tex> L \setminus R = L \cap \overline{R} </tex>, а, поскольку регулярные Регулярные языки замкнуты относительно дополнения, то следовательно разность можно выразить через пересечение.}}