Изменения

<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешительразрешатель) для каждого случая.

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

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

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

Языки <tex> L_1, L_2 </tex> –- перечислимы, тогдаязыки  <tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ L_1 \times L_2\\ L_1^* \\ L_1 L_2 \end{array} \right\} </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|_k(x) == 1) \lor (p_2|_k(x) == 1) </tex> '''then return 1'''  Перечислитель же для этого языка будет по очереди на один шаг запускать перечислители для <tex>L_1</tex> и <tex>L_2</tex> и выдавать по очереди слова из <tex>L_1</tex> и <tex>L_2</tex> соответственно.  Для языка <tex> L_1 \cap L_2 :</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>x_i :</tex> разбиение <tex>x</tex> '''if''' <tex>(p_1(x_i) == 1)</tex> '''then return''' 1 Перечислитель строится следующим образом: запускаем перечислитель для <tex> L_1 </tex> в цикле по тайм-лимиту и запоминаем выданные им слова. При выдаче каждого нового слова перебираем все возможные перестановки уже выданных слов и выдаем их.   Для языка <tex> L_1 L_2 : </tex>  полуразрешающая программа:  <tex>p(x)</tex> '''for''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex> '''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex> '''then return''' 1  Перечислитель для <tex> L_1 L_2 </tex> строим следующим образом: запускаем одновременно перечислители для <tex> L_1 </tex> и <tex> L_2 </tex>, запоминая все выданные слова. При выдаче новых слов перебираем все возможные пары из запомненных слов и выдаем их конкатенацию.}}  {{Теорема|statement= Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда языки 

Рассмотрим язык <tex> \bar{L_1} </tex>. Предположим, что он перечислим. Тогда имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \bar{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \bar{L_1} </tex>. Тогда получится что <tex> L_1 </tex> разрешим, так как про любое слово мы можем узнать принадлежит оно <tex> L_1 </tex> или не принадлежит. Но мы знаем, что существуют перечислимые, но не разрешимые языки, следовательно, язык <tex> \bar{L_1} </tex> может быть не перечислим. Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмем язык, состоящий из всех слов. Тогда получится, что язык <tex> L_1 \backslash L_2 </tex> это <tex> \baroverline{L_2} </tex>. Про язык <tex> \baroverline{L_2} </tex> мы знаем, что он перечислим не всегда, следовательно и язык <tex> L_1 \backslash L_2 </tex> также не всегда перечислим.