271
правка
Изменения
Нет описания правки
Языки <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\ (L_1 \cap 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\ (</tex>;* <tex>L_1 \backslash 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>.
|proof=
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешитель) для каждого случая.
* Разрешающая программа для языка <tex> L_1 \cup L_2 :</tex> :
<tex>p(x):</tex>
'''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex>
* Для языка <tex> L_1 \cap L_2 :</tex> :
<tex>p(x):</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex>
* Для языка <tex> \overline{L_1} :</tex> :
<tex>p(x):</tex>
'''return''' <tex>(p_1(x) == 0)</tex>
* Для языка <tex> L_1 \backslash L_2 :</tex> :
<tex>p(x):</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex>
* Для языка <tex> L_1 \times L_2 :</tex> :
<tex>p(\langle x, y \rangle):</tex>
'''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex>
* Для языка <tex>L_1^* :</tex> :
<tex>p(x):</tex>
'''forall''' <tex>{\{x_i\}}_{i=1}^n \in P </tex>, где <tex>P</tex> {{---}} множество всех возможных разбиений слова <tex>x</tex> на подстроки
'''if''' <tex>(p_1(x_1) == 1) \land (p_1(x_2) == 1) \land \ ... \ \land (p_1(x_n) == 1)</tex>
