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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Отмена правки 14881 участника 192.168.0.2 (обсуждение))
м (rollbackEdits.php mass rollback)
 
(не показано 37 промежуточных версий 8 участников)
Строка 1: Строка 1:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
  Языки <tex> L_1, L_2 </tex> - разрешимы, тогда языки
+
  Языки <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>.
  
<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ \overline{L_1} \\ L_1 \backslash L_2 \\ L_1 \times L_2 \\L_1^* \\  L_1 L_2 \end{array} \right\} </tex> тоже разрешимы.
 
 
|proof=
 
|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> разрешающие программы для языков   
+
Пусть <tex>p_1</tex> и <tex>p_2</tex> {{---}} разрешающие программы для языков   
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешатель) для каждого случая.  
+
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешитель) для каждого случая.  
  
* Разрешающая программа для языка <tex> L_1 \cup L_2 :</tex>  
+
* Разрешающая программа для языка <tex> L_1 \cup L_2</tex>:
  
  <tex>p(x)</tex>
+
  <tex>p(x):</tex>
 
     '''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex>  
 
     '''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex>  
  
* Для языка <tex> L_1 \cap L_2 :</tex>  
+
* Для языка <tex> L_1 \cap L_2 </tex>:
  
  <tex>p(x)</tex>
+
  <tex>p(x):</tex>
 
     '''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex>  
 
     '''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex>  
  
* Для языка <tex> \overline{L_1} :</tex>  
+
* Для языка <tex> \overline{L_1}</tex>:
  
  <tex>p(x)</tex>
+
  <tex>p(x):</tex>
 
     '''return''' <tex>(p_1(x) == 0)</tex>
 
     '''return''' <tex>(p_1(x) == 0)</tex>
  
* Для языка <tex> L_1 \backslash L_2 :</tex>  
+
* Для языка <tex> L_1 \backslash L_2</tex>:
  
  <tex>p(x)</tex>
+
  <tex>p(x):</tex>
 
     '''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex>  
 
     '''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex>  
  
* Для языка <tex> L_1 \times L_2 :</tex>  
+
* Для языка <tex> L_1 \times L_2</tex>:
  
  <tex>p(\langle x, y \rangle)</tex>
+
  <tex>p(\langle x, y \rangle):</tex>
 
     '''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex>  
 
     '''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex>  
  
* Для языка <tex>L_1^* :</tex>  
+
* Для языка <tex>L_1^*</tex>:
 
   
 
   
  <tex>p(x)</tex>
+
  <tex>p(x):</tex>
     '''for''' <tex>x_i :</tex> разбиение <tex>x</tex>    
+
     '''forall''' <tex>{\{x_i\}}_{i=1}^n \in P </tex>, где <tex>P</tex> {{---}} множество всевозможных разбиений слова <tex>x</tex> на подстроки
         '''if''' <tex>(p_1(x_i) == 1)</tex>  
+
         '''if''' <tex>(p_1(x_1) == 1) \land (p_1(x_2) == 1) \land \ldots \land (p_1(x_n) == 1)</tex>  
        '''then return''' 1
+
            '''return''' <tex>1</tex>
     '''return''' 0   
+
     '''return''' <tex>0</tex>  
  
Разрешатель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подслова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex>, иначе не принадлежит.  
+
Разрешитель будет перебирать все возможные разбиения данного ему слова на подстроки и для каждой проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подстроки будут принадлежать <tex> L_1 </tex>, то всё слово принадлежит <tex> L_1^* </tex>, иначе {{---}} не принадлежит.  
  
 
* Для языка <tex> L_1 L_2 : </tex>  
 
* Для языка <tex> L_1 L_2 : </tex>  
  
  <tex>p(x)</tex>
+
  <tex>p(x):</tex>
     '''for''' <tex>x_1, x_2 :</tex> разбиение <tex>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>  
+
         '''if''' <tex>(p_1(x_1) == 1) \land (p_2(x_2) == 1)</tex>  
        '''then return''' 1
+
            '''return''' <tex>1</tex>
     '''return''' 0   
+
     '''return''' <tex>0</tex>  
  
Разрешатель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешателя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе не принадлежит.
+
Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешителя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе {{---}} не принадлежит.
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
  Языки <tex> L_1, L_2 </tex> - перечислимы, тогда языки
+
  Языки <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>.
  
<tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ L_1 \times L_2\\ L_1^* \\  L_1 L_2 \end{array} \right\} </tex> тоже перечислимы.
 
 
|proof=
 
|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>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> L_1 \cup L_2</tex>:
  
полуразрешающая программа:
+
<tex>p(x):</tex>
 +
      '''for''' <tex>k = 1 \ \ldots \ \infty</tex>
 +
          '''if''' <tex> (p_1(x)|_k == 1) \lor (p_2(x)|_k == 1) </tex>
 +
              '''return''' <tex>1</tex>
  
<tex>p(x)</tex>
+
* Для языка <tex> L_1 \cap L_2</tex>:
    '''for''' <tex>k = 1\ .. \ \infty </tex>     
 
        '''if''' <tex> (p_1|_k(x) == 1) \lor (p_2|_k(x) == 1) </tex>    
 
        '''then return 1'''
 
  
Перечислитель же для этого языка будет по очереди на один шаг запускать перечислители для <tex>L_1</tex> и <tex>L_2</tex> и выдавать по очереди слова из <tex>L_1</tex> и <tex>L_2</tex> соответственно.
+
<tex>p(x):</tex>
 +
    '''if''' <tex> (p_1(x) == 1) \land (p_2(x) == 1) </tex>    
 +
        '''return''' <tex>1</tex>  
  
* Для языка <tex> L_1 \cap L_2 :</tex>  
+
* Для языка <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''' <tex>1</tex>
  
<tex>p(x)</tex>
+
* Для языка <tex> L_1^*</tex>:
    '''for''' <tex>k = 1\ .. \ \infty </tex>     
 
        '''if''' <tex> (p_1|_k(x) == 1) \land (p_2|_k(x) == 1) </tex>     
 
        '''then return 1'''
 
 
 
* Для языка <tex> L_1 \times L_2 :</tex>
 
 
 
полуразрешающая программа:
 
 
 
<tex>p(\langle x, y \rangle)</tex>
 
    '''for''' <tex>k = 1\ .. \ \infty </tex>     
 
        '''if''' <tex> (p_1|_k(x) == 1) \land (p_2|_k(y) == 1) </tex>     
 
        '''then return 1'''
 
 
 
* Для языка <tex> L_1^* :</tex>
 
 
 
полуразрешающая программа (по аналогии с <tex>L_1^*</tex> для разрешимого <tex>L_1</tex>):
 
 
   
 
   
  <tex>p(x)</tex>
+
  <tex>p(x):</tex>
     '''for''' <tex>x_i :</tex> разбиение <tex>x</tex>    
+
     '''for''' <tex>k = 1 \ \ldots \ \infty</tex>
        '''if''' <tex>(p_1(x_i) == 1)</tex>  
+
        '''forall''' <tex>{\{x_i\}}_{i=1}^n \in P </tex>, где <tex>P</tex> {{---}} множество всевозможных разбиений слова <tex>x</tex> на подстроки
        '''then return''' 1
+
            '''if''' <tex>(p_1|_k(x_1) == 1) \land (p_1|_k(x_2) == 1) \land \ \dots \ \land (p_1|_k(x_n) == 1)</tex>
 +
                '''return''' <tex>1</tex>
  
Перечислитель строится следующим образом: запускаем перечислитель для <tex> L_1 </tex> в цикле по тайм-лимиту и запоминаем выданные им слова. При выдаче каждого нового слова перебираем все возможные перестановки уже выданных слов и выдаем их.
+
* Для языка <tex> L_1 L_2 </tex>:
  
* Для языка <tex> L_1 L_2 : </tex>  
+
<tex>p(x):</tex>
 
+
    '''for''' <tex>k = 1 \ \ldots \ \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>
<tex>p(x)</tex>
+
                '''return''' <tex>1</tex>  
    '''for''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>    
+
&nbsp;
        '''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>  
 
        '''then return''' 1
 
 
 
 
Перечислитель для <tex> L_1 L_2 </tex> строим следующим образом: запускаем одновременно перечислители для <tex> L_1 </tex>  и <tex> L_2 </tex>, запоминая все выданные слова. При выдаче новых слов перебираем все возможные пары из запомненных слов и выдаем их конкатенацию.
 
 
}}
 
}}
  
Строка 121: Строка 115:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
  Языки <tex> L_1, L_2 </tex> - перечислимы, тогда языки
+
  Языки <tex> L_1 </tex> и <tex> L_2 </tex> {{---}} перечислимы, тогда следующие языки могут быть неперечислимы:
 
 
  
<tex>\left. \begin{array}{lll} \overline{L_1} \\ L_1 \backslash L_2 \end{array} \right\} </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=
 
|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> \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> также не всегда перечислим.
+
Теперь рассмотрим <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
  
== Литература ==
+
[[Категория: Теория формальных языков]]
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' -- М.: МЦНМО, 1999
+
[[Категория: Теория вычислимости]]
 +
[[Категория: Разрешимые и перечислимые языки]]

Текущая версия на 19:12, 4 сентября 2022

Теорема:
Языки [math] L_1 [/math] и [math] L_2 [/math]разрешимы, тогда следующие языки разрешимы:
  • [math]L_1 \cup 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]\overline{L_1}[/math] — дополнение [math]L_1\[/math]
  • [math]L_1 \backslash L_2[/math] — разность [math]L_1[/math] и [math]L_2[/math]
  • [math]L_1 \times L_2[/math] — декартово произведение [math]L_1[/math] и [math]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]\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\}}_{i=1}^n \in P [/math], где [math]P[/math] — множество всевозможных разбиений слова [math]x[/math] на подстроки
        if [math](p_1(x_1) == 1) \land (p_1(x_2) == 1) \land \ldots \land (p_1(x_n) == 1)[/math] 
            return [math]1[/math]
    return [math]0[/math]  

Разрешитель будет перебирать все возможные разбиения данного ему слова на подстроки и для каждой проверять принадлежность [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_i\}}_{i=1}^2 \in P [/math], где [math]P[/math] — множество всевозможных разбиений слова [math]x[/math] на две подстроки
        if [math](p_1(x_1) == 1) \land (p_2(x_2) == 1)[/math] 
            return [math]1[/math]
    return [math]0[/math]  
Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова [math] L_1 [/math] и второго слова [math] L_2 [/math]. Если хотя бы для одного разбиения оба разрешителя вернут 1, то слово принадлежит [math] L_1 L_2 [/math], иначе — не принадлежит.
[math]\triangleleft[/math]
Теорема:
Языки [math] L_1 [/math] и [math] L_2 [/math]перечислимы, тогда следующие языки перечислимы:
  • [math]L_1 \cup 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 \times L_2[/math] — декартово произведение [math]L_1[/math] и [math]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]\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]
     for [math]k = 1 \ \ldots \ \infty[/math]
         if [math] (p_1(x)|_k == 1) \lor (p_2(x)|_k == 1) [/math] 
             return [math]1[/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 [math]1[/math] 
  • Для языка [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 [math]1[/math] 
  • Для языка [math] L_1^*[/math]:
[math]p(x):[/math]
    for [math]k = 1 \ \ldots \ \infty[/math]
        forall [math]{\{x_i\}}_{i=1}^n \in P [/math], где [math]P[/math] — множество всевозможных разбиений слова [math]x[/math] на подстроки
            if [math](p_1|_k(x_1) == 1) \land (p_1|_k(x_2) == 1) \land \ \dots \ \land (p_1|_k(x_n) == 1)[/math]
                return [math]1[/math] 
  • Для языка [math] L_1 L_2 [/math]:
[math]p(x):[/math]
    for [math]k = 1 \ \ldots \ \infty[/math]
        forall [math]{\{x_i\}}_{i=1}^2 \in P [/math], где [math]P[/math] — множество всевозможных разбиений слова [math]x[/math] на две подстроки
            if [math](p_1|_k(x_1) == 1) \land (p_2|_k(x_2) == 1)[/math]
                return [math]1[/math] 
 
[math]\triangleleft[/math]


Теорема:
Языки [math] L_1 [/math] и [math] L_2 [/math] — перечислимы, тогда следующие языки могут быть неперечислимы:
  • [math]\overline{L_1}[/math] — дополнение [math]L_1\[/math]
  • [math]L_1 \backslash L_2[/math] — разность [math]L_1[/math] и [math]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. С. 134. ISBN 5-900916-36-7