Изменения

Языки <tex> L_1, L_2 </tex> –- разрешимы, тогдаязыки

<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ \baroverline{L_1} \\ L_1 \backslash L_2 \\ L_1 \times L_2 \\ L_1^* \\ L_1 L_2 \end{array} \right\} </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> '''return''' <tex>(p_1(x) == 1, если оба разрешателя выдали ) \land (p_2(x) == 1, 0 во всех остальных случаях. )</tex>   Для языка <tex> L_1 \cap L_2 :</tex>   <tex>p(x)</tex> разрешающая программа будет запускать оба разрешателя и выдавать 0, если оба разрешателя выдали 0, '''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1 во всех остальынх случаях. )</tex>   Для языка <tex> \baroverline{L_1} :</tex> разрешатель будет выдавать результат, обратный результату разрешателя для   <tex>p(x)</tex> '''return''' <tex> L_1 (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, а второй 0 и 0 во всех остальных случаях. )</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 '''return''' 0  Разрешатель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все слова подслова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <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 '''return''' 0  Разрешитель будет перебирать все возможные разбиения на 2 два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешателя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе — не принадлежит.