Изменения

* <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>;

'''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>p(x):</tex>

'''return''' <tex>1</tex> '''return''' <tex>0 </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> 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> '''for''' <tex>k = 1 \ .. \ldots \ \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 1'''<tex>1</tex>

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

<tex>p(x):</tex> '''for''' <tex>k = 1 \ .. \ldots \ \infty</tex> '''forall''' <tex>{\{x_i\}}_{i=1}^2 \in P </tex>, где <tex>P</tex> {{---}} множество всех возможных всевозможных разбиений слова <tex>x</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перечислимые языки]]