Изменения

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

Пусть <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>

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

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

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

* Для языка <tex>p(x)</tex> '''for''' <tex>k = 1\ .. \ \infty </tex> '''if''' <tex> (p_1|_k(x) == 1) L_1 \lor (p_2|_k(x) == 1) cap L_2</tex> '''then return 1''' :

Перечислитель же для этого языка будет по очереди на один шаг запускать перечислители для <tex>L_1p(x):</tex> и '''if''' <tex>L_2(p_1(x) == 1) \land (p_2(x) == 1) </tex> и выдавать по очереди слова из '''return''' <tex>L_11</tex> и <tex>L_2</tex> соответственно.

* Для языка <tex> L_1 \cap 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>p(x)</tex> '''for''' <tex>k = 1\ .. \ \infty </tex> '''if''' <tex> (p_1|_k(x) == 1) \land (p_2|_k(x) == 1) </tex> '''then return 1'''  * Для языка <tex> L_1 \times L_2 :</tex>  полуразрешающая программа:  <tex>p(\langle x, y \rangle)</tex> '''for''' <tex>k = 1\ .. \ \infty </tex> '''if''' <tex> (p_1|_k(x) == 1) \land (p_2|_k(y) == 1) </tex> '''then return 1'''  * Для языка <tex> L_1^* :</tex> полуразрешающая программа (по аналогии с <tex>L_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_ix_2) == 1) \land \ \dots \ \land (p_1|_k(x_n) == 1)</tex> '''then return''' <tex>1</tex>

Перечислитель строится следующим образом: запускаем перечислитель для * Для языка <tex> L_1 L_2 </tex> в цикле по тайм-лимиту и запоминаем выданные им слова. При выдаче каждого нового слова перебираем все возможные перестановки уже выданных слов и выдаем их. :

* Для языка <tex> L_1 L_2 p(x): </tex>  полуразрешающая программа:  '''for''' <tex>p(x)k = 1 \ \ldots \ \infty</tex> '''forforall''' <tex>x_1{\{x_i\}}_{i=1}^2 \in P </tex>, x_2 :где <tex>P</tex> разбиение {{---}} множество всевозможных разбиений слова <tex>x</tex> на две подстроки '''if''' <tex>(p_1|_k(x_1) == 1 ) \land (p_2|_k(x_2) == 1)</tex> '''then return''' 1  Перечислитель для <tex> L_1 L_2 1</tex> строим следующим образом: запускаем одновременно перечислители для <tex> L_1 </tex> и <tex> L_2 </tex>, запоминая все выданные слова. При выдаче новых слов перебираем все возможные пары из запомненных слов и выдаем их конкатенацию.&nbsp;

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

* <tex>\left. \beginoverline{arrayL_1}</tex> {lll{---} \overline{} дополнение <tex>L_1} \\ </tex>* <tex>L_1 \backslash L_2 \end</tex> {{array---} \right\} разность <tex>L_1</tex> и <tex>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перечислимые языки]]