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

Теорема:

Языки [math] L_1, L_2 [/math] –- разрешимы, тогда следующие языки разрешимы: Объединение [math]L_1[/math] и [math]L_2\ (L_1 \cup L_2)[/math] Пересечение [math]L_1[/math] и [math]L_2\ (L_1 \cap L_2)[/math] Дополнение [math]L_1\ (\overline{L_1})[/math] Разность [math]L_1[/math] и [math]L_2\ (L_1 \backslash L_2)[/math] Декартово произведение [math]L_1[/math] и [math]L_2\ (L_1 \times L_2)[/math] Замыкание Клини [math]L_1\ (L_1^*)[/math] Конкатенация [math]L_1[/math] и [math]L_2\ (L_1 L_2)[/math]

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

[math]\triangleright[/math]

Пусть [math]p_1[/math] и [math]p_2[/math] — разрешающие программы для языков [math]L_1[/math] и [math]L_2[/math] соответственно. Для доказательства достаточно написать разрешающую программу (разрешитель) для каждого случая. Разрешающая программа для языка [math] L_1 \cup L_2 :[/math] [math]p(x)[/math] return [math](p_1(x) == 1) \lor (p_2(x) == 1)[/math] Для языка [math] L_1 \cap L_2 :[/math] [math]p(x)[/math] return [math](p_1(x) == 1) \land (p_2(x) == 1)[/math] Для языка [math] \overline{L_1} :[/math] [math]p(x)[/math] return [math](p_1(x) == 0)[/math] Для языка [math] L_1 \backslash L_2 :[/math] [math]p(x)[/math] return [math](p_1(x) == 1) \land (p_2(x) == 0)[/math] Для языка [math] L_1 \times L_2 :[/math] [math]p(\langle x, y \rangle)[/math] return [math](p_1(x) == 1) \land (p_2(y) == 1)[/math] Для языка [math]L_1^* :[/math] [math]p(x)[/math] forall [math]x_i :[/math] разбиение [math]x[/math] if [math](p_1(x_1) == 1) \land (p_1(x_2) == 1) \land \ ... \ \land (p_1(x_n) == 1)[/math] return 1 return 0 Разрешитель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность [math] L_1 [/math]. Если хотя бы в одном разбиении все подслова будут принадлежать [math] L_1 [/math], то все слово принадлежит [math] L_1^* [/math], иначе — не принадлежит. Для языка [math] L_1 L_2 : [/math] [math]p(x)[/math] forall [math]x_1, x_2 :[/math] разбиение [math]x[/math] if [math](p_1(x_1) == 1 \land p_2(x_2) == 1)[/math] return 1 return 0 Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова [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]L_1[/math] и [math]L_2\ (L_1 \cup L_2)[/math] Пересечение [math]L_1[/math] и [math]L_2\ (L_1 \cap L_2)[/math] Декартово произведение [math]L_1[/math] и [math]L_2\ (L_1 \times L_2)[/math] Замыкание Клини [math]L_1\ (L_1^*)[/math] Конкатенация [math]L_1[/math] и [math]L_2\ (L_1 L_2)[/math]

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

[math]\triangleright[/math]

Пусть [math]p_1[/math] и [math]p_2[/math] — полуразрешающие программы для языков [math]L_1[/math] и [math]L_2[/math] соответственно. Для доказательства достаточно написать полуразрешающую или перечисляющую программу для каждого случая. Для некоторых языков предоставим оба варианта. Заметим, что [math]p_1[/math] и [math]p_2[/math] могут зависнуть при использовании в полуразрешающей программе для соответствующего языка, но это допустимо. Для языка [math] L_1 \cup L_2 :[/math] полуразрешающая программа: [math]p(x)[/math] if [math] (p_1(x) == 1) \lor (p_2(x) == 1) [/math] return 1 Перечислитель же для этого языка будет по очереди на один шаг запускать перечислители для [math]L_1[/math] и [math]L_2[/math] и выдавать по очереди слова из [math]L_1[/math] и [math]L_2[/math] соответственно. Для языка [math] L_1 \cap L_2 :[/math] полуразрешающая программа: [math]p(x)[/math] if [math] (p_1(x) == 1) \land (p_2(x) == 1) [/math] return 1 Для языка [math] L_1 \times L_2 :[/math] полуразрешающая программа: [math]p(\langle x, y \rangle)[/math] if [math] (p_1(x) == 1) \land (p_2(y) == 1) [/math] return 1 Для языка [math] L_1^* :[/math] полуразрешающая программа (по аналогии с [math]L_1^*[/math] для разрешимого [math]L_1[/math]): [math]p(x)[/math] forall [math]x_i :[/math] разбиение [math]x[/math] if [math](p_1(x_1) == 1) \land (p_1(x_2) == 1) \land \ ... \ \land (p_1(x_n) == 1)[/math] return 1 Перечислитель же строится следующим образом: запускаем перечислитель для [math] L_1 [/math] в цикле по тайм-лимиту и запоминаем выданные им слова. При выдаче каждого нового слова перебираем все возможные перестановки уже выданных слов и выдаем их. Для языка [math] L_1 L_2 : [/math] полуразрешающая программа: [math]p(x)[/math] forall [math]x_1, x_2 :[/math] разбиение [math]x[/math] if [math](p_1(x_1) == 1 \land p_2(x_2) == 1)[/math] return 1 Перечислитель же для [math] L_1 L_2 [/math] строим следующим образом: запускаем одновременно перечислители для [math] L_1 [/math] и [math] L_2 [/math], запоминая все выданные слова. При выдаче новых слов перебираем все возможные пары из запомненных слов и выдаем их конкатенацию.

[math]\triangleleft[/math]

Теорема:

Языки [math] L_1, L_2 [/math] –- перечислимы, тогда следующие языки могут быть не перечислимы: Дополнение [math]L_1\ (\overline{L_1})[/math] Разность [math]L_1[/math] и [math]L_2\ (L_1 \backslash L_2)[/math]

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

[math]\triangleright[/math]

Рассмотрим язык [math] \overline{L_1} [/math]. Предположим, что он перечислим. Тогда имея какое-либо слово, мы можем одновременно запустить перечислители для [math] L_1 [/math] и [math] \overline{L_1} [/math]. В какой-то момент времени слово появится либо в выводе перечислителя для [math] L_1 [/math], либо в выводе перечислителя для [math] \overline{L_1} [/math]. Тогда получится что [math] L_1 [/math] разрешим, так как про любое слово мы можем узнать принадлежит оно [math] L_1 [/math] или не принадлежит. Но мы знаем, что существуют перечислимые, но не разрешимые языки, следовательно, язык [math] \overline{L_1} [/math] может быть не перечислим. Теперь рассмотрим [math] L_1 \backslash L_2 [/math]. В качестве [math] L_1 [/math] возьмем язык, состоящий из всех слов. Тогда получится, что язык [math] L_1 \backslash L_2 [/math] это [math] \overline{L_2} [/math]. Про язык [math] \overline{L_2} [/math] мы знаем, что он перечислим не всегда, следовательно и язык [math] L_1 \backslash L_2 [/math] также не всегда перечислим.

[math]\triangleleft[/math]

Литература

• Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции — М.: МЦНМО, 1999