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

2017-01-14T17:48:16Z

188.162.65.87:

{{Теорема
|statement=
Языки <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 \cap L_2</tex> {{---}} пересечение <tex>L_1</tex> и <tex>L_2\</tex>
* <tex>\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 \times L_2</tex> {{---}} декартово произведение <tex>L_1</tex> и <tex>L_2</tex>
* <tex>L_1^*</tex> {{---}} замыкание Клини <tex>L_1</tex>
* <tex>L_1 L_2</tex> {{---}} конкатенация <tex>L_1</tex> и <tex>L_2</tex>.

|proof=
Пусть <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) \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>
'''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>
'''forall''' <tex>{\{x_i\}}_{i=1}^2 \in P </tex>, где <tex>P</tex> {{---}} множество всевозможных разбиений слова <tex>x</tex> на две подстроки
'''if''' <tex>(p_1(x_1) == 1) \land (p_2(x_2) == 1)</tex>
'''return''' 1
'''return''' 0

Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешителя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе {{---}} не принадлежит.
}}

{{Теорема
|statement=
Языки <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 \cap L_2</tex> {{---}} пересечение <tex>L_1</tex> и <tex>L_2\</tex>
* <tex>L_1 \times L_2</tex> {{---}} декартово произведение <tex>L_1</tex> и <tex>L_2</tex>
* <tex>L_1^*</tex> {{---}} замыкание Клини <tex>L_1</tex>
* <tex>L_1 L_2</tex> {{---}} конкатенация <tex>L_1</tex> и <tex>L_2</tex>.

|proof=

Пусть <tex>p_1</tex> и <tex>p_2</tex> {{---}} полуразрешающие программы для языков <tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать полуразрешающую программу для каждого случая. Заметим, что <tex>p_1</tex> и <tex>p_2</tex> могут зависнуть при использовании в полуразрешающей программе для соответствующего языка, но это допустимо.

* Полуразрешающая программа для языка <tex> L_1 \cup L_2</tex>:

<tex>p(x):</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''if''' <tex> (p_1(x)|_k == 1) \lor (p_2(x)|_k == 1) </tex>
'''return 1'''

* Для языка <tex> L_1 \cap L_2</tex>:

<tex>p(x):</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(x) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1 \times L_2</tex>:

<tex>p(\langle x, y \rangle):</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(y) == 1) </tex>
'''return 1'''

* Для языка <tex> L_1^*</tex>:

<tex>p(x):</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''forall''' <tex>{\{x_i\}}_{i=1}^n \in P </tex>, где <tex>P</tex> {{---}} множество всевозможных разбиений слова <tex>x</tex> на подстроки
'''if''' <tex>(p_1|_k(x_1) == 1) \land (p_1|_k(x_2) == 1) \land \ ... \ \land (p_1|_k(x_n) == 1)</tex>
'''return 1'''

* Для языка <tex> L_1 L_2 </tex>:

<tex>p(x):</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''forall''' <tex>{\{x_i\}}_{i=1}^2 \in P </tex>, где <tex>P</tex> {{---}} множество всевозможных разбиений слова <tex>x</tex> на две подстроки
'''if''' <tex>(p_1|_k(x_1) == 1) \land (p_2|_k(x_2) == 1)</tex>
'''return 1'''
 
}}

{{Теорема
|statement=
Языки <tex> L_1 </tex> и <tex> L_2 </tex> {{---}} перечислимы, тогда следующие языки могут быть неперечислимы:

* <tex>\overline{L_1}</tex> {{---}} дополнение <tex>L_1\</tex>
* <tex>L_1 \backslash L_2</tex> {{---}} разность <tex>L_1</tex> и <tex>L_2</tex>.

|proof=

Рассмотрим язык <tex> \overline{L_1} </tex>. Предположим, что он перечислим. Тогда, имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \overline{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \overline{L_1} </tex>. Тогда получится, что <tex> L_1 </tex> разрешим, так как про любое слово можно сказать, принадлежит ли оно <tex> L_1 </tex> или нет. Но мы знаем, что [[Разрешимые (рекурсивные) языки#Пример неразрешимого множества|существуют перечислимые, но неразрешимые языки]], следовательно, язык <tex> \overline{L_1} </tex> может быть неперечислим.

Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмём язык, состоящий из всех слов. Тогда получится, что <tex> L_1 \backslash L_2 </tex> {{---}} это <tex> \overline{L_2} </tex>. Про <tex> \overline{L_2} </tex> мы знаем, что он перечислим не всегда, поэтому и <tex> L_1 \backslash L_2 </tex> не всегда перечислим.
}}

== Источники информации ==
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7

[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Разрешимые и перечислимые языки]]

Викиконспекты - Вклад участника [ru]

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