Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций

Теорема:

[math] L_1, L_2 [/math] –- разрешимы, тогда [math]\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\} [/math] разрешимы

Доказательство:

[math]\triangleright[/math]

Если языки разрешимы, значит для каждого из них есть разрешающая программа. Тогда разрешающая программа для языка [math]L_1 \cup L_2[/math] будет запускать разрешающую для каждого языка и выводить 1, если оба разрешателя выдали 1, 0 во всех остальных случаях. Для языка [math] L_1 \cap L_2 [/math] разрешающая программа будет запускать оба разрешателя и выдавать 0, если оба разрешателя выдали 0, 1 во всех остальынх случаях. Для языка [math] \bar{L_1} [/math] разрешатель будет выдавать результат, обратный результату разрешателя для [math] L_1 [/math]. Для языка [math] L_1 \backslash L_2 [/math] разрешающая программа будет запускать оба разрешателя и выдавать 1, если первый разрешатель вернет 1, а второй 0 и 0 во всех остальных случаях. Для языка [math] L_1^* [/math] разрешатель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность [math] L_1 [/math]. Если хотя бы в одном разбиении все слова будут принадлежать [math] L_1 [/math], то все слово принадлежит [math] L_1^* [/math] иначе не принадлежит. Для языка [math] L_1 L_2 [/math] разрешающая программа будет перебирать все возможные разбиения на 2 слова и проверять принадлежность первого слова [math] L_1 [/math] и второго слова [math] L_2 [/math]. Если хотя бы для одного разбиения оба разрешателя вернут 1, то слово принадлежит [math] L_1 L_2 [/math], иначе не принадлежит.

[math]\triangleleft[/math]

Теорема:

[math] L_1, L_2 [/math] –- перечислимы, тогда [math]\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ L_1^* \\ L_1 L_2 \end{array} \right\} [/math] перечислимы [math]\left. \begin{array}{lll} \bar{L_1} \\ L_1 \backslash L_2 \end{array} \right\} [/math] могут быть не перечислимы

Доказательство:

[math]\triangleright[/math]

Для [math] L_1 \cup L_2 [/math] перечислитель будет по очереди на один шаг запускать перечислители [math] L_1 [/math] и [math] L_2 [/math] и выдавать по очереди слова из [math] L_1 [/math] и [math] L_2 [/math]. Дальше воспользуемся возможностью построить полувычислитель для перечислимого языка. Для языка [math] L_1 \cap L_2 [/math] построим полувычислитель. Запустим по очереди полувычислители для [math] L_1 [/math] и [math] L_2 [/math]. Если слово принадлежит [math] L_1 \cap L_2 [/math], то оба полувычислителя выдадут 1, иначе один из полувычислителей зависнет, и полувычислитель для [math] L_1 \cap L_2 [/math] тоже зависнет, что допустимо. Для [math] L_1^* [/math] перечислитель строится следующим образом: запускаем перечислитель для [math] L_1 [/math] в цикле и запоминаем выданные им слова. При выдаче каждого нового слова перебираем все возможные перестановки уже выданных слов и выдаем их. Перечислитель для [math] L_1 L_2 [/math] строим следующим образом: запускаем одновременно перечислители для [math] L_1 [/math] и [math] L_2 [/math], запоминая все выданные слова. При выдаче новых слов перебираем все возможные пары из запомненных слов и выдаем их. Рассмотрим язык [math] \bar{L_1} [/math]. Предположим, что он перечислим. Тогда имея какое-либо слово, мы можем одновременно запустить перечислители для [math] L_1 [/math] и [math] \bar{L_1} [/math]. В какой-то момент времени слово появится либо в выводе перечислителя для [math] L_1 [/math], либо в выводе перечислителя для [math] \bar{L_1} [/math]. Тогда получится что [math] L_1 [/math] разрешим, так как про любое слово мы можем узнать принадлежит оно [math] L_1 [/math] или не принадлежит. Но мы знаем, что существуют перечислимые, но не разрешимые языки, следовательно, язык [math] \bar{L_1} [/math] может быть не перечислим. Теперь рассмотрим [math] L_1 \backslash L_2 [/math]. В качестве [math] L_1 [/math] возьмем язык, состоящий из всех слов. Тогда получится, что язык [math] L_1 \backslash L_2 [/math] это [math] \bar{L_2} [/math]. Про язык [math] \bar{L_2} [/math] мы знаем, что он перечислим не всегда, следовательно и язык [math] L_1 \backslash L_2 [/math] также не всегда перечислим.

[math]\triangleleft[/math]