Изменения
Отмена правки 14881 участника 192.168.0.2 (обсуждение)
<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ \overline{L_1} \\ L_1 \backslash 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> соответственно. Для доказательства достаточно написать разрешающую программу (разрешатель) для каждого случая.
'''return''' 0
* Для языка <tex> L_1 L_2 : </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> L_1^* :</tex>
<tex>p(x)</tex>
