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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
Строка 1: Строка 1:
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 
|+
 
|-align="center"
 
|'''НЕТ ВОЙНЕ'''
 
|-style="font-size: 16px;"
 
|
 
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 
 
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 
 
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 
 
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 
 
''Антивоенный комитет России''
 
|-style="font-size: 16px;"
 
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 
|-style="font-size: 16px;"
 
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 
|}
 
 
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=

Текущая версия на 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