Изменения

В отличие от [[Замкнутость регулярных языков относительно различных операций|регулярных языков]], [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-языки ]] не замкнуты относительно всех теоретико-множественных операций. К примеру, дополнение и пересечение КС-языков не обязательно являются КС-языками.

Здесь и далее считаем, что <tex> L_1 </tex> и <tex> L_2 </tex> — КС-- КС языки.

== Операции с КС-языками ==

=== Объединение ===

|statement= <tex> L_1 \cup L_2 </tex> также является КС-языком.

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

=== Конкатенация ===

|statement= <tex> L_1 L_2 </tex> -- — КС-язык.|proof=Аналогично предыдущему случаю построим КС-грамматика грамматику для языка <tex> L_1 L_2 </tex> выглядит следующим образом: . Для этого добавим правило <tex> S' \to S T </tex>, где <tex> S </tex> и <tex> T </tex> — стартовые символы языков <tex> L_1 </tex> и <tex> S L_2 </tex> -- стартовый символ.Доказательство аналогично случаю с объединениемсоответственно.

== = [[Основные определения, связанные со строками#Формальные языки | Замыкание Клини ]] === {{ Утверждение|statement= <tex> L^{*} = \bigcup\limits_{i = 0}^{\infty} L^i </tex> — КС-язык.|proof=Если <tex> S </tex> — стартовый символ КС-грамматики для языка <tex> L </tex>, то добавим в КС-грамматику для языка <tex> L^{*} </tex> новый стартовый символ <tex> S' </tex> и правила <tex> S' \to S S' \mid \varepsilon </tex>. }} ===Гомоморфизмы ======= [[Основные определения, связанные со строками#Гомоморфизм языков | Прямой гомоморфизм]] ==== {{ Утверждение|statement=КС-языки замкнуты относительно прямого гомоморфизма.|proof=Построим КС-грамматику, в которой каждый символ <tex> x \in \Sigma </tex> заменим на <tex> \mathrm{h}(x) </tex>. }}

|statement= КС-языки замкнуты относительно обратного гомоморфизма.|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> M = \bigcuplangle Q, \limits_Sigma, \Gamma, \delta, s, Z_{i 0}, T\rangle </tex>, тогда <tex> M' = \langle Q', \Sigma, \Gamma, \delta', (s, \varepsilon), Z_{0}^, T \times {\inftyvarepsilon} L^i \rangle</tex> -- КС-язык.|proof* <tex> Q' =Если \{ (q, x) \mid q \in Q \} </tex>, где <tex> x </tex> — суффикс (не обязательно собственный) некоторой цепочки <tex> S h(c) </tex> -- стартовый символ КС-грамматики для языка символа <tex> c \in \Sigma </tex>. Таким образом, первый компонент состояния <tex> M' </tex> является состоянием <tex> L M </tex>, то добавим в КС-грамматику для языка а второй — компонентом буфера.* <tex> \delta' </tex> определяется следующими правилами:** <tex> L^\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> Sc </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> SM' </tex> является <tex> (s, \to S Svarepsilon) </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>.

== Прямой и обратный гомоморфизм = Разворот ===

В случае с прямым гомоморфизмом всё просто: строится КС-грамматика, в которой каждый символ {{ Утверждение|statement= <tex> x L^{R} = \{ w^{R} \mid w \in L \Sigma </tex> заменяется на <tex> h(x) }</tex>контекстно-свободен. |proof= Для обратного гомоморфизма построим МП-автомат для того, чтобы построить <tex> hL^{-1R}(L) </tex> по МП-автомату , необходимо развернуть все правые части правил грамматики для языка <tex> L </tex>.

Для того, чтобы построить КС-грамматику для языка <tex> L^{R} = \{ w^{R} \mid w \in Rightarrow</tex>:Докажем с помощью метода математической индукции по длине порождения в грамматике <tex>L \} </tex>, необходимо развернуть все правые части правил грамматики для .:'''База'''. <tex> A \underset{L }{\Rightarrow} w</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>.

В отличие от регулярных языков, дополнение до <tex>\Leftarrow</tex>:Доказательство аналогично.}}'''Пример разворота''': Пусть задана КС-грамматика <tex>G</tex> для языка, пересечение <tex>L = a^i b^j c^i</tex> со следующими правилами: * <tex> A \to bA \mid \varepsilon </tex>* <tex> B \to aBc \mid A </tex> В таком случае КС-языков и разность КС-языков может не быть КС-языком.грамматика <tex>G^R</tex> для языка <tex>L^R = c^i b^j a^i </tex> выглядит следующим образом: * <tex> A \to Ab \mid \varepsilon </tex>* <tex> B \to cBa \mid A </tex> === Дополнение к языку тандемных повторов ===

|statement= Язык тандемных повторов <tex> L = \{ww \mid w \in \Sigma^{*} \} </tex> не является КС-языком, однако <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>, поэтому разность КС-языков также необязательно является КС-языком.

}}Более того, даже задачи определения того, является ли дополнение КС-языка КС-языком и проверки непустоты пересечения или включения КС-языков являются алгоритмически [[Разрешимые (рекурсивные) языки|неразрешимыми]].

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

<tex> Half\mathrm{half}(L) = \{ w \mid ww \in L \} </tex>

{{ Утверждение|statement= Операция <tex> Half \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>. Посмотрим Заметим, что он может быть сгенерирован при помощи следующей КС-грамматики: * <tex> S \to AbBbBbAb </tex>* <tex> B \to a \mid aB</tex>* <tex> A \to b \mid aAa</tex> '''Докажем, что есть <tex> Half\mathrm{half}(L) </tex>не является КС-языком. '''  Пусть <tex> \alpha = a^n b a^n b a^m b a^l b a^k b a^k b = ww </tex>. Отсюда следует, что:

А значит, <tex> n = l = k = m </tex>, и <tex> Half\mathrm{half}(L) = \{ a^n b a^n b a^т n b \} </tex>, и по [[Лемма о разрастании для КС-грамматик|лемме о накачке разрастании]] КС-языком не является.}}== Операции над КС-языком и регулярным языком ==

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

Тем не менееПусть регулярный язык задан своим [[Детерминированные конечные автоматы|ДКА]], хоть пересечение двух КС-языков не обязательно является КС-языком, но пересечение КС-языка и регулярного языка -- всегда а КС-язык. Для доказательства этого построим — своим [[Автоматы с магазинной памятью|МП-автомат автоматом]] c допуском по допускающему состоянию. Построим прямое произведение этих автоматов так же, как строилось прямое произведение для пересечения регулярного языка и КС-языкадвух ДКА.

Пусть Более формально, пусть <tex> R </tex> — регулярный язык задан , заданный своим ДКА<tex> \langle \Sigma, Q_1, s_1, T_1, \delta_1 \rangle </tex>, а и <tex> L </tex> — КС-язык -- , заданный своим МП-автоматом c допуском по допускающему состоянию. Построим прямое произведение этих автоматов также: <tex> \langle \Sigma, \Gamma, Q_2, s_2, T_2, z_0, как строилось прямое произведение для двух ДКА\delta_2 \rangle </tex>.Тогда прямым произведением назовем следующий автомат:

Более формально, пусть <tex> R </tex> -- регулярный язык, заданный своим ДКА <tex> \langle \Sigma, Q_1, s_1, T_1, \delta_1 \rangle </tex>, и <tex> L </tex> -- КС-язык, заданный своим МП-автоматом: <tex> \langle \Sigma, \Gamma, Q_2, s_2, T_2, z_0, \delta_2 \rangle </tex>. Тогда прямым произведением назовем следующий автомат: * <tex> Q = \{ \langle q_1, q_2 \rangle \mid q_1 \in Q_1, q_2 \in Q_2 \} </tex>. Иначе говоря, состояние в новом автомате -- — пара из состояния первого автомата и состояния второго автомата.

* <tex> T = \{ \langle t_1, t_2 \rangle \mid t_1 \in T_1, t_2 \in T_2 \} </tex>. Допускающие состояния нового автомата -- — пары состояний, где оба состояния были допускающими в своем автомате.