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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 7: Строка 7:
 
|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>  
Строка 37: Строка 37:
 
   
 
   
 
  <tex>p(x)</tex>
 
  <tex>p(x)</tex>
     '''for''' <tex>x_i :</tex> разбиение <tex>x</tex>     
+
     '''forall''' <tex>x_i :</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 \ ... \ \land (p_1(x_n) == 1)</tex>  
 
         '''then return''' 1
 
         '''then return''' 1
 
     '''return''' 0   
 
     '''return''' 0   
  
Разрешатель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <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_1, x_2 :</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
 
         '''then return''' 1
 
     '''return''' 0   
 
     '''return''' 0   
  
Разрешатель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <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>, иначе — не принадлежит.
 
}}
 
}}
  
Строка 63: Строка 63:
 
|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>  
Строка 70: Строка 70:
  
 
  <tex>p(x)</tex>
 
  <tex>p(x)</tex>
     '''for''' <tex>k = 1\ .. \ \infty </tex>     
+
     '''if''' <tex> (p_1(x) == 1) \lor (p_2(x) == 1) </tex>       
        '''if''' <tex> (p_1|_k(x) == 1) \lor (p_2|_k(x) == 1) </tex>       
+
    '''then return 1'''  
        '''then return 1'''  
 
  
 
Перечислитель же для этого языка будет по очереди на один шаг запускать перечислители для <tex>L_1</tex> и <tex>L_2</tex> и выдавать по очереди слова из <tex>L_1</tex> и <tex>L_2</tex> соответственно.
 
Перечислитель же для этого языка будет по очереди на один шаг запускать перечислители для <tex>L_1</tex> и <tex>L_2</tex> и выдавать по очереди слова из <tex>L_1</tex> и <tex>L_2</tex> соответственно.
Строка 81: Строка 80:
  
 
  <tex>p(x)</tex>
 
  <tex>p(x)</tex>
     '''for''' <tex>k = 1\ .. \ \infty </tex>     
+
     '''if''' <tex> (p_1(x) == 1) \land (p_2(x) == 1) </tex>       
        '''if''' <tex> (p_1|_k(x) == 1) \land (p_2|_k(x) == 1) </tex>       
+
    '''then return 1'''  
        '''then return 1'''  
 
  
 
* Для языка <tex> L_1 \times L_2 :</tex>  
 
* Для языка <tex> L_1 \times L_2 :</tex>  
Строка 90: Строка 88:
  
 
  <tex>p(\langle x, y \rangle)</tex>
 
  <tex>p(\langle x, y \rangle)</tex>
     '''for''' <tex>k = 1\ .. \ \infty </tex>     
+
     '''if''' <tex> (p_1(x) == 1) \land (p_2(y) == 1) </tex>       
        '''if''' <tex> (p_1|_k(x) == 1) \land (p_2|_k(y) == 1) </tex>       
+
    '''then return 1'''  
        '''then return 1'''  
 
  
 
* Для языка <tex> L_1^* :</tex>
 
* Для языка <tex> L_1^* :</tex>
Строка 99: Строка 96:
 
   
 
   
 
  <tex>p(x)</tex>
 
  <tex>p(x)</tex>
     '''for''' <tex>x_i :</tex> разбиение <tex>x</tex>     
+
     '''forall''' <tex>x_i :</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 \ ... \ \land (p_1(x_n) == 1)</tex>
 
         '''then return''' 1
 
         '''then return''' 1
  
Строка 110: Строка 107:
  
 
  <tex>p(x)</tex>
 
  <tex>p(x)</tex>
     '''for''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>     
+
     '''forall''' <tex>x_1, x_2 :</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
 
         '''then return''' 1
Строка 134: Строка 131:
  
 
== Литература ==
 
== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' М.: МЦНМО, 1999
+
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' -- М.: МЦНМО, 1999

Версия 05:31, 19 декабря 2011

Теорема:
Языки [math] L_1, L_2 [/math] –- разрешимы, тогда языки


[math]\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\} [/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] 
        then 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] 
        then 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]\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\} [/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]      
    then 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]      
    then 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]      
    then 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]
        then 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] 
        then 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]\left. \begin{array}{lll} \overline{L_1} \\ L_1 \backslash L_2 \end{array} \right\} [/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