25
правок
Изменения
Нет описания правки
{{Теорема
|statement=
Не существует алгоритма, определяющего по произвольной грамматике, является ли она однозначной (''unambiguous grammar'')[[Существенно неоднозначные языки | неоднозначной]].
|proof=
Будем доказывать от противного. Для этого произведем [[M-сводимость|m-сведение]] множества решений [[Примеры неразрешимых задач: проблема соответствий Поста|проблемы соответствий постаПоста]] к множеству решений нашей задачи. А так как множество решений ПСП неразрешимо, то из m-сведения будет следовать неразрешимость нашей задачи.
Пусть <tex> \Sigma </tex> {{---}} алфавит для экземпляра ПСП <tex>(x_1,\,x_2,\,...\ldots ,\,x_n)</tex>, <tex>(y_1,\,y_2,\,...\ldots ,\,y_n)</tex>. Рассмотрим грамматику <tex>L=\{\Sigma^{*}, N, P, S\}</tex>, где <tex> \Sigma^{*}= \Sigma+\{z_i\}</tex> и <tex>\{z_i\}=\{z_1,\,z_2,\,...\ldots ,\,z_n\}</tex> {{---}} множество символов, не встречающихся в алфавите <tex> \Sigma</tex>. Символы <tex> \{z_i\} </tex> можно воспринимать как номера правил, по которым мы будем выводить слова в нашей грамматике.
Зададим грамматику <tex>L</tex> следующими правилами:
<tex>B \rightarrow \varepsilon</tex>
Заметим, что любое слово <tex>w</tex>, выводимое в этой грамматике, может быть представлено в виде <tex>w=x_{i1}x_{i2} \ldots x_{ik}z_{ik}z_{ik-1} \ldots z_{i1}</tex> или <tex>w=y_{i1}y_{i2} \ldots y_{ik}z_{ik}z_{ik-1} \ldots z_{i1}</tex>, причем, если <tex>L</tex> неоднозначна, то слово можно вывести двумя способами, и тогда <tex>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}</tex>. Так как это одно и тоже слово, то все <tex> z_{i} </tex> в этом слове равны. А каждое <tex> z_{i} </tex> однозначно задает правило, по которому мы выводили слово.
Получили, что не существует алгоритма, определяющего по произвольной грамматике, является ли она однозначной.
}}
== Литература См. также ==* [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора | Контекстно-свободные грамматики]]* [[Формальные грамматики]]* [[Иерархия Хомского формальных грамматик]]* [[Разрешимые (рекурсивные) языки | Разрешимые языки]]* [[m-сводимость]]* [[Примеры неразрешимых задач: проблема соответствий Поста | Проблема соответствий Поста]] == Источники информации ==
* А. Маслов, Д. Стоцкий — Языки и автоматы. Издательство Мир, 1975, -361 с.
* [httphttps://en.wikipedia.org/wiki/Ambiguous_grammar ambiguous Wikipedia {{---}} Ambiguous grammar - Wikipedia]
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Примеры неразрешимых задач]]