Редактирование: Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

{{Теорема
|statement=
 Языки <tex> L_1 </tex> и <tex> L_2 </tex> {{---}} [[Разрешимые_(рекурсивные)_языки|разрешимы]], тогда следующие языки разрешимы:

* <tex>L_1 \cup L_2</tex> {{---}} объединение <tex>L_1</tex> и <tex>L_2</tex>
* <tex>L_1 \cap L_2</tex> {{---}} пересечение <tex>L_1</tex> и <tex>L_2</tex>
* <tex>\overline{L_1}</tex> {{---}} дополнение <tex>L_1\</tex>
* <tex>L_1 \backslash L_2</tex> {{---}} разность <tex>L_1</tex> и <tex>L_2</tex>
* <tex>L_1 \times L_2</tex> {{---}} декартово произведение <tex>L_1</tex> и <tex>L_2</tex>
* <tex>L_1^*</tex> {{---}} замыкание Клини <tex>L_1</tex>
* <tex>L_1 L_2</tex> {{---}} конкатенация <tex>L_1</tex> и <tex>L_2</tex>.

|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> {{---}} разрешающие программы для языков  
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешитель) для каждого случая. 

* Разрешающая программа для языка <tex> L_1 \cup L_2</tex>: 

 <tex>p(x):</tex>
     '''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex> 

* Для языка <tex> L_1 \cap L_2 </tex>: 

 <tex>p(x):</tex>
     '''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex> 

* Для языка <tex> \overline{L_1}</tex>: 

 <tex>p(x):</tex>
     '''return''' <tex>(p_1(x) == 0)</tex>

* Для языка <tex> L_1 \backslash L_2</tex>: 

 <tex>p(x):</tex>
     '''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex> 

* Для языка <tex> L_1 \times L_2</tex>: 

 <tex>p(\langle x, y \rangle):</tex>
     '''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex> 

* Для языка <tex>L_1^*</tex>: 
 
 <tex>p(x):</tex>
     '''forall''' <tex>{\{x_i\}}_{i=1}^n \in P </tex>, где <tex>P</tex> {{---}} множество всевозможных разбиений слова <tex>x</tex> на подстроки
         '''if''' <tex>(p_1(x_1) == 1) \land (p_1(x_2) == 1) \land \ldots \ \land (p_1(x_n) == 1)</tex> 
             '''return''' <tex>1</tex>
     '''return''' <tex>0</tex>  

Разрешитель будет перебирать все возможные разбиения данного ему слова на подстроки и для каждой проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подстроки будут принадлежать <tex> L_1 </tex>, то всё слово принадлежит <tex> L_1^* </tex>, иначе {{---}} не принадлежит. 

* Для языка <tex> L_1 L_2 : </tex> 

 <tex>p(x):</tex>
     '''forall''' <tex>{\{x_i\}}_{i=1}^2 \in P </tex>, где <tex>P</tex> {{---}} множество всевозможных разбиений слова <tex>x</tex> на две подстроки
         '''if''' <tex>(p_1(x_1) == 1) \land (p_2(x_2) == 1)</tex> 
             '''return''' <tex>1</tex>
     '''return''' <tex>0</tex>  

Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешителя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе {{---}} не принадлежит.
}}

{{Теорема
|statement=
 Языки <tex> L_1 </tex> и <tex> L_2 </tex> {{---}} [[Перечислимые_языки|перечислимы]], тогда следующие языки перечислимы:

* <tex>L_1 \cup L_2</tex> {{---}} объединение <tex>L_1</tex> и <tex>L_2</tex>
* <tex>L_1 \cap L_2</tex> {{---}} пересечение <tex>L_1</tex> и <tex>L_2\</tex>
* <tex>L_1 \times L_2</tex> {{---}} декартово произведение <tex>L_1</tex> и <tex>L_2</tex>
* <tex>L_1^*</tex> {{---}} замыкание Клини <tex>L_1</tex>
* <tex>L_1 L_2</tex> {{---}} конкатенация <tex>L_1</tex> и <tex>L_2</tex>.

|proof=

Пусть <tex>p_1</tex> и <tex>p_2</tex> {{---}} полуразрешающие программы для языков <tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать полуразрешающую программу для каждого случая. Заметим, что <tex>p_1</tex> и <tex>p_2</tex> могут зависнуть при использовании в полуразрешающей программе для соответствующего языка, но это допустимо.

* Полуразрешающая программа для языка <tex> L_1 \cup L_2</tex>: 

 <tex>p(x):</tex>
      '''for''' <tex>k = 1 \ .. \ \infty</tex>
          '''if''' <tex> (p_1(x)|_k == 1) \lor (p_2(x)|_k == 1) </tex> 
              '''return''' <tex>1</tex> 

* Для языка <tex> L_1 \cap L_2</tex>: 

 <tex>p(x):</tex>
     '''if''' <tex> (p_1(x) == 1) \land (p_2(x) == 1) </tex>      
         '''return''' <tex>1</tex> 

* Для языка <tex> L_1 \times L_2</tex>: 

 <tex>p(\langle x, y \rangle):</tex>
     '''if''' <tex> (p_1(x) == 1) \land (p_2(y) == 1) </tex>      
         '''return''' <tex>1</tex> 

* Для языка <tex> L_1^*</tex>:
 
 <tex>p(x):</tex>
     '''for''' <tex>k = 1 \ .. \ \infty</tex>
         '''forall''' <tex>{\{x_i\}}_{i=1}^n \in P </tex>, где <tex>P</tex> {{---}} множество всевозможных разбиений слова <tex>x</tex> на подстроки
             '''if''' <tex>(p_1|_k(x_1) == 1) \land (p_1|_k(x_2) == 1) \land \ \dots \ \land (p_1|_k(x_n) == 1)</tex>
                 '''return''' <tex>1</tex> 

* Для языка <tex> L_1 L_2 </tex>: 

 <tex>p(x):</tex>
     '''for''' <tex>k = 1 \ .. \ \infty</tex>
         '''forall''' <tex>{\{x_i\}}_{i=1}^2 \in P </tex>, где <tex>P</tex> {{---}} множество всевозможных разбиений слова <tex>x</tex> на две подстроки
             '''if''' <tex>(p_1|_k(x_1) == 1) \land (p_2|_k(x_2) == 1)</tex>
                 '''return''' <tex>1</tex> 
&nbsp;
}}


{{Теорема
|statement=
 Языки <tex> L_1 </tex> и <tex> L_2 </tex> {{---}} перечислимы, тогда следующие языки могут быть неперечислимы:

* <tex>\overline{L_1}</tex> {{---}} дополнение <tex>L_1\</tex>
* <tex>L_1 \backslash L_2</tex> {{---}} разность <tex>L_1</tex> и <tex>L_2</tex>.

|proof=

Рассмотрим язык <tex> \overline{L_1} </tex>. Предположим, что он перечислим. Тогда, имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \overline{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \overline{L_1} </tex>. Тогда получится, что <tex> L_1 </tex> разрешим, так как про любое слово можно сказать, принадлежит ли оно <tex> L_1 </tex> или нет. Но мы знаем, что [[Разрешимые (рекурсивные) языки#Пример неразрешимого множества|существуют перечислимые, но неразрешимые языки]], следовательно, язык <tex> \overline{L_1} </tex> может быть неперечислим. 

Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмём язык, состоящий из всех слов. Тогда получится, что <tex> L_1 \backslash L_2 </tex> {{---}} это <tex> \overline{L_2} </tex>. Про <tex> \overline{L_2} </tex> мы знаем, что он перечислим не всегда, поэтому и <tex> L_1 \backslash L_2 </tex> не всегда перечислим.
}}
== См. также ==

* [[Разрешимые (рекурсивные) языки]]
* [[Перечислимые языки]]

== Источники информации ==
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7

[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Разрешимые и перечислимые языки]]