7
правок
Изменения
Первая теорема.
{{Теорема
|statement=
<tex> L_1, L_2 </tex> –- разрешимы, тогда
<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ \bar{L_1} \\ L_1 \backslash L_2 \\ L_1^* \\ L_1 L_2 \end{array} \right\} </tex> разрешимы
|proof=
Если языки разрешимы, значит для каждого из них есть разрешающая программа. Тогда разрешающая программа для языка <tex>L_1 \cup L_2</tex> будет запускать разрешающую для каждого языка и выводить 1, если оба разрешателя выдали 1, 0 во всех остальных случаях. Для языка <tex> L_1 \cap L_2 </tex> разрешающая программа будет запускать оба разрешателя и выдавать 0, если оба разрешателя выдали 0, 1 во всех остальынх случаях. Для языка <tex> \bar{L_1} </tex> разрешатель будет выдавать результат, обратный результату разрешателя для <tex> L_1 </tex>. Для языка <tex> L_1 \backslash L_2 </tex> разрешающая программа будет запускать оба разрешателя и выдавать 1, если первый разрешатель вернет 1, а второй 0 и 0 во всех остальных случаях. Для языка <tex> L_1^* </tex> разрешатель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все слова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex> иначе не принадлежит. Для языка <tex> L_1 L_2 </tex> разрешающая программа будет перебирать все возможные разбиения на 2 слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешателя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex> иначе не принадлежит.
}}
|statement=
<tex> L_1, L_2 </tex> –- разрешимы, тогда
<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ \bar{L_1} \\ L_1 \backslash L_2 \\ L_1^* \\ L_1 L_2 \end{array} \right\} </tex> разрешимы
|proof=
Если языки разрешимы, значит для каждого из них есть разрешающая программа. Тогда разрешающая программа для языка <tex>L_1 \cup L_2</tex> будет запускать разрешающую для каждого языка и выводить 1, если оба разрешателя выдали 1, 0 во всех остальных случаях. Для языка <tex> L_1 \cap L_2 </tex> разрешающая программа будет запускать оба разрешателя и выдавать 0, если оба разрешателя выдали 0, 1 во всех остальынх случаях. Для языка <tex> \bar{L_1} </tex> разрешатель будет выдавать результат, обратный результату разрешателя для <tex> L_1 </tex>. Для языка <tex> L_1 \backslash L_2 </tex> разрешающая программа будет запускать оба разрешателя и выдавать 1, если первый разрешатель вернет 1, а второй 0 и 0 во всех остальных случаях. Для языка <tex> L_1^* </tex> разрешатель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все слова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex> иначе не принадлежит. Для языка <tex> L_1 L_2 </tex> разрешающая программа будет перебирать все возможные разбиения на 2 слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешателя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex> иначе не принадлежит.
}}
