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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
  Языки <tex> L_1 </tex> и <tex> L_2 </tex> {{---}} [[Разрешимые_(рекурсивные)_языки|разрешимы]], тогда следующие языки разрешимы:
 
  Языки <tex> L_1 </tex> и <tex> L_2 </tex> {{---}} [[Разрешимые_(рекурсивные)_языки|разрешимы]], тогда следующие языки разрешимы:
  
* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
+
* <tex>L_1 \cup L_2</tex> {{---}} объединение <tex>L_1</tex> и <tex>L_2</tex>;
* Пересечение <tex>L_1</tex> и <tex>L_2\ (L_1 \cap L_2)</tex>
+
* <tex>L_1 \cap L_2</tex> {{---}} пересечение <tex>L_1</tex> и <tex>L_2\</tex>;
* Дополнение <tex>L_1\ (\overline{L_1})</tex>
+
* <tex>\overline{L_1}</tex> {{---}} дополнение <tex>L_1\</tex>;
* Разность <tex>L_1</tex> и <tex>L_2\ (L_1 \backslash L_2)</tex>
+
* <tex>L_1 \backslash L_2</tex> {{---}} разность <tex>L_1</tex> и <tex>L_2</tex>;
* Декартово произведение <tex>L_1</tex> и <tex>L_2\ (L_1 \times L_2)</tex>
+
* <tex>L_1 \times L_2</tex> {{---}} декартово произведение <tex>L_1</tex> и <tex>L_2</tex>;
* Замыкание Клини <tex>L_1\ (L_1^*)</tex>
+
* <tex>L_1^*</tex> {{---}} замыкание Клини <tex>L_1</tex>;
* Конкатенация <tex>L_1</tex> и <tex>L_2\ (L_1 L_2)</tex>
+
* <tex>L_1 L_2</tex> {{---}} конкатенация <tex>L_1</tex> и <tex>L_2</tex>.
  
 
|proof=
 
|proof=
Строка 15: Строка 15:
 
<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>
 
     '''forall''' <tex>{\{x_i\}}_{i=1}^n \in P </tex>, где <tex>P</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_1) == 1) \land (p_1(x_2) == 1) \land \ ... \ \land (p_1(x_n) == 1)</tex>  
 
         '''if''' <tex>(p_1(x_1) == 1) \land (p_1(x_2) == 1) \land \ ... \ \land (p_1(x_n) == 1)</tex>  

Версия 09:14, 23 декабря 2011

Теорема:
Языки [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 \ ... \ \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_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 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]
     for [math]k = 1 \ .. \ \infty[/math]
         if [math] (p_1(x)|_k == 1) \lor (p_2(x)|_k == 1) [/math]      
             return 1 
  • Для языка [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]p(x)[/math]
    for [math]k = 1 \ .. \ \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 \ ... \ \land (p_1|_k(x_n) == 1)[/math]
                return 1
  • Для языка [math] L_1 L_2 : [/math]
[math]p(x)[/math]
    for [math]k = 1 \ .. \ \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 1
 
[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