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

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

Здесь и далее считаем, что [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]