Неразрешимость задачи о проверке на пустоту пересечения двух КС-грамматик
НЕТ ВОЙНЕ |
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Теорема: |
Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима. |
Доказательство: |
Пусть проблему соответствий Поста к , таким образом показав, что дополнение проблемы неразрешимо. Так как рекурсивные языки замкнуты относительно дополнения, то из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы. . СведемДля любого экземпляра ПСП и над алфавитом можно подобрать символ . Для каждого экземпляра построим грамматики:
Если данный экземпляр ПСП имеет решение, то Таким образом мы свели проблему соответствий Поста к содержит хотя бы одну строку вида , поэтому , и наоборот, если он не имеет решения, то не содержит строк такого вида, соответственно . , следовательно, задача о проверке на пустоту пересечения двух КС-грамматик неразрешима. |
Из неразрешимости вышеприведенной задачи следует неразрешимость ряда других задач. Рассмотрим несколько примеров.
По двум КС-грамматикам конкатенации задаваемых ими языков . По аналогии с этим мы можем рассматривать язык , где — новый символ, не встречающийся в алфавите. Заметим, что пересечение языков непусто, то есть , тогда и только тогда, когда содержит тандемный повтор.
и можно построить КС-грамматику дляАналогично можно заметить, что пересечение
тогда и только тогда, когда содержит палиндром.Таким образом, мы имеем:
Утверждение: |
Пусть дана грамматика , . Тогда следующие задачи неразрешимы:
|