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