Изменения

Языки <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 \cup cap L_2)</tex>* Пересечение {{---}} пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap L_2)</tex>* Дополнение <tex>L_1\ (\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 \backslash times L_2)</tex>* Декартово {{---}} декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>* Замыкание Клини <tex>L_1\ (L_1^*)</tex> {{---}} замыкание Клини <tex>L_1</tex>* Конкатенация <tex>L_1 L_2</tex> {{---}} конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>.

Пусть <tex>p_1</tex> и <tex>p_2</tex> — {{---}} разрешающие программы для языков

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

<tex>p(x):</tex>

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

<tex>p(x):</tex>

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

<tex>p(x):</tex>

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

<tex>p(x):</tex>

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

<tex>p(\langle x, y \rangle):</tex>

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

<tex>p(x):</tex> '''forall''' <tex>d_i :{\{x_i\}}_{i=1}^n \in P </tex> все возможные разбиения , где <tex>P</tex>x_{d_1}x_{d_2---} \ .. \ x_{d_n} :</tex> текущее разбиение множество всевозможных разбиений слова <tex>x</tex>на подстроки '''if''' <tex>(p_1(x_{d_1}x_1) == 1) \land (p_1(x_{d_2}x_2) == 1) \land \ ... \ ldots \land (p_1(x_{d_n}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>p(x):</tex> '''forall''' <tex>d_{\{x_i\}}_{i=1,}^2} :\in P </tex> все возможные разбиения на две части , где <tex>x_{d_1}x_{d_2} :P</tex> текущее разбиение {{---}} множество всевозможных разбиений слова <tex>x</tex> на две подстроки '''if''' <tex>(p_1(x_{d_1}x_1) == 1 ) \land (p_2(x_{d_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>, иначе — {{---}} не принадлежит.

Языки <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 \cup cap L_2)</tex>* Пересечение {{---}} пересечение <tex>L_1</tex> и <tex>L_2\ (</tex>* <tex>L_1 \cap times L_2)</tex>* Декартово {{---}} декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>* Замыкание Клини <tex>L_1\ (L_1^*)</tex> {{---}} замыкание Клини <tex>L_1</tex>* Конкатенация <tex>L_1 L_2</tex> {{---}} конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>.

Пусть <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 \ .. \ldots \ \infty</tex> '''if''' <tex> (p_1(x)|_k == 1) \lor (p_2(x)|_k == 1) </tex> '''return 1''' <tex>1</tex>

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

<tex>p(x):</tex>

'''return 1''' <tex>1</tex>

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

<tex>p(\langle x, y \rangle):</tex>

'''return 1''' <tex>1</tex>

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

<tex>p(x):</tex> '''forallfor''' <tex>d_i :k = 1 \ \ldots \ \infty</tex> все возможные разбиения '''forall''' <tex>x_{d_1\{x_i\}x_}_{d_2i=1} ^n \ .. \ x_{d_n} :in P </tex>, где <tex>P</tex> текущее разбиение {{---}} множество всевозможных разбиений слова <tex>x</tex>на подстроки '''if''' <tex>(p_1|_k(x_{d_1}x_1) == 1) \land (p_1|_k(x_{d_2}x_2) == 1) \land \ ... \dots \ \land (p_1|_k(x_{d_n}x_n) == 1)</tex> '''return 1'''<tex>1</tex>

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

<tex>p(x):</tex> '''forallfor''' <tex>d_{k = 1,2} :\ \ldots \ \infty</tex> все возможные разбиения на две части '''forall''' <tex>x_{d_1\{x_i\}}x__{d_2i=1} :^2 \in P </tex>, где <tex>P</tex> текущее разбиение {{---}} множество всевозможных разбиений слова <tex>x</tex> на две подстроки '''if''' <tex>(p_1|_k(x_{d_1}x_1) == 1 ) \land (p_2|_k(x_{d_2}x_2) == 1)</tex> '''return 1'''<tex>1</tex>

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

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

Рассмотрим язык <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перечислимые языки]]