54
правки
Изменения
Нет описания правки
{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- разрешимы, тогда следующие языкиразрешимы:
* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup 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_2\ (L_1 \backslash 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_2\ (L_1 L_2)</tex>
|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> — разрешающие программы для языков
{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда следующие языкиперечислимы:
* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
* Пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap 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_2\ (L_1 L_2)</tex>
|proof=
{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –- перечислимы, тогда следующие языкимогут быть не перечислимы:
* Дополнение <tex>L_1\left. \begin{array}{lll} (\overline{L_1} )</tex>* Разность <tex>L_1</tex> и <tex>L_2\\ (L_1 \backslash L_2 \end{array} \right\} )</tex> могут быть не перечислимы.
|proof=
