Замкнутость КС-языков относительно различных операций

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

Здесь и далее считаем, что [math] L_1 и L_2 [/math] -- КС языки.

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

Объединение

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

[math] L_1 \cup L_2 [/math] также является КС-языком.

[math]\triangleright[/math]

Построим КС-грамматику для языка [math] L_1 \cup L_2 [/math]. Для этого рассмотрим соответствующие КС-грамматики для языков [math] L_1 [/math] и [math] L_2 [/math]. Пусть стартовые символы в них имеют имена [math] S [/math] и [math] T [/math] соответственно. Тогда стартовый символ для [math] L_1 \cup L_2 [/math] обозначим за [math] S' [/math] и добавим правило [math] S' \to S\,|\,T [/math]. Покажем, что [math] S' \Rightarrow^{*} w \iff S \Rightarrow^{*} w \lor T \Rightarrow^{*} w [/math]. В левую сторону: коли [math] S \Rightarrow^{*} w [/math] и есть правило [math] S' \to S [/math], то, по определению [math] Rightarrow^{*} [/math] получаем, что [math] S' \Rightarrow^{*} w [/math]. Аналогично и для [math] T [/math]. В обратную сторону, пусть [math] S' \Rightarrow^{*} w [/math]. Поскольку [math] S' \to S\,|\,T [/math] -- единственные правила, в которых нетерминал [math] S' [/math] присутствует в правой части, а значит, либо [math] S' \Rightarrow S \Rightarrow^{*} w [/math], либо [math] S' \Rightarrow T \Rightarrow^{*} w [/math], что и требовалось доказать.

[math]\triangleleft[/math]

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

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

[math] L_1 L_2 [/math] -- КС-язык.

[math]\triangleright[/math]

КС-грамматика для [math] L_1 L_2 [/math] выглядит следующим образом: [math] S' \to S T [/math], и [math] S [/math] -- стартовый символ. Доказательство аналогично случаю с объединением.

[math]\triangleleft[/math]

Замыкание Клини

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

[math] L^{*} = \bigcup\limits_{i = 0}^{\infty} L^i [/math] -- КС-язык.

[math]\triangleright[/math]

Если [math] S [/math] -- стартовый символ КС-грамматики для языка [math] L [/math], то добавим в КС-грамматику для языка [math] L^{*} [/math] новый стартовый символ [math] S' [/math] и правила [math] S' \to S S' \, | \, \varepsilon [/math].

[math]\triangleleft[/math]

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

В случае с прямым гомоморфизмом всё просто: строится КС-грамматика, в которой каждый символ [math] x \in \Sigma [/math] заменяется на [math] h(x) [/math]. Для обратного гомоморфизма построим МП-автомат для [math] h^{-1}(L) [/math] по МП-автомату для языка [math] L [/math].

Разворот

Для того, чтобы построить КС-грамматику для языка [math] L^{R} = \{ w^{R} \mid w \in L \} [/math], необходимо развернуть все правые части правил грамматики для [math] L [/math].

Циклический сдвиг

...

Дополнение, пересечение и разность

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

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

[math] L = \{ww \mid w \in \Sigma^{*} \} [/math] не является КС-языком, однако [math] \overline{L} [/math] -- КС-язык.

[math]\triangleright[/math]

То, что [math] L [/math] -- не КС язык, доказывается с помощью леммы о накачке. Для [math] \overline{L} [/math] можно составить КС-грамматику. Предоставим это читателю в качестве упражнения.

[math]\triangleleft[/math]

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

Если [math] L_1 = a^i b^i c^j , L_2 = a^i b^j c^j [/math], то [math] L_1 \cap L_2 [/math] не является КС-языком.

[math]\triangleright[/math]

[math] L_1 = \{ a^i b^i \} \cdot \{ c^j \}, L_2 = \{ a^i \} \cdot \{ b^j c^j \} [/math]. По замкнутости КС-языков относительно конкатенации получаем, что [math] L_1 [/math] и [math] L_2 [/math] являются КС-языками. Но [math] L_1 \cap L_2 = \{ a^i b^i c^i \mid i \in \mathbb{N} \} [/math], что по лемме о накачке для КС-языков не является КС-языком.

[math]\triangleleft[/math]

Для разности достаточно заметить, что [math] \overline{L} = \Sigma^{*} \setminus L [/math], поэтому разность КС-языков также необязательно является КС-языком.

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

Операции над КС-языком и регулярным языком

Тем не менее, хоть пересечение двух КС-языков не обязательно является КС-языком, но пересечение КС-языка и регулярного языка -- всегда КС-язык. Для доказательства этого построим МП-автомат для пересечения регулярного языка и КС-языка.

Пусть регулярный язык задан своим ДКА, а КС-язык -- своим МП-автоматом. Построим прямое произведение этих автоматов также, как строилось прямое произведение для двух ДКА.

Более формально, ...