Примеры неразрешимых задач: однозначность грамматики

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Теорема:

Не существует алгоритма, определяющего по произвольной грамматике, является ли она неоднозначной.

Доказательство:

[math]\triangleright[/math]

Будем доказывать от противного. Для этого произведем m-сведение множества решений проблемы соответствий Поста к множеству решений нашей задачи. А так как множество решений ПСП неразрешимо, то из m-сведения будет следовать неразрешимость нашей задачи. Пусть [math] \Sigma [/math] — алфавит для экземпляра ПСП [math](x_1,\,x_2,\, \ldots ,\,x_n)[/math], [math](y_1,\,y_2,\, \ldots ,\,y_n)[/math]. Рассмотрим грамматику [math]L=\{\Sigma^{*}, N, P, S\}[/math], где [math] \Sigma^{*}= \Sigma+\{z_i\}[/math] и [math]\{z_i\}=\{z_1,\,z_2,\, \ldots ,\,z_n\}[/math] — множество символов, не встречающихся в алфавите [math] \Sigma[/math]. Символы [math] \{z_i\} [/math] можно воспринимать как номера правил, по которым мы будем выводить слова в нашей грамматике. Зададим грамматику [math]L[/math] следующими правилами: [math]S \rightarrow A [/math] [math] | B [/math] [math]A \rightarrow x_iAz_i[/math] [math]A \rightarrow \varepsilon[/math] [math]B \rightarrow y_iBz_i[/math] [math]B \rightarrow \varepsilon[/math] Заметим, что любое слово [math]w[/math], выводимое в этой грамматике, может быть представлено в виде [math]w=x_{i1}x_{i2} \ldots x_{ik}z_{ik}z_{ik-1} \ldots z_{i1}[/math] или [math]w=y_{i1}y_{i2} \ldots y_{ik}z_{ik}z_{ik-1} \ldots z_{i1}[/math], причем, если [math]L[/math] неоднозначна, то слово можно вывести двумя способами, и тогда [math]w=x_{i1}x_{i2} \ldots x_{ik}z_{ik}z_{ik-1} \ldots z_{i1} = y_{i1}y_{i2} \ldots y_{ik}z_{ik}z_{ik-1} \ldots z_{i1}[/math]. Так как это одно и тоже слово, то все [math] z_{i} [/math] в этом слове равны. А каждое [math] z_{i} [/math] однозначно задает правило, по которому мы выводили слово. Поэтому, если бы мы умели решать сформулированную нами ПСП, то могли бы сказать, однозначна грамматика или нет. То есть, если ПСП имеет решение, то мы можем восстановить два вывода слова. Если ПСП не имеет решения, то грамматика однозначна, и не существует двух выводов одного и того же слова. Таким образом, мы получили m-сведение множества решений ПСП к множеству решений нашей задачи. А это значит, что задача об однозначности грамматики неразрешима. Получили, что не существует алгоритма, определяющего по произвольной грамматике, является ли она однозначной.

[math]\triangleleft[/math]

См. также

• Контекстно-свободные грамматики
• Формальные грамматики
• Иерархия Хомского формальных грамматик
• Разрешимые языки
• m-сводимость
• Проблема соответствий Поста

Источники информации

• А. Маслов, Д. Стоцкий — Языки и автоматы. Издательство Мир, 1975, -361 с.
• Wikipedia — Ambiguous grammar