Изменения

Не существует алгоритма, определяющего по произвольной грамматике, является ли она однозначной (''ambiguous grammar'')[[Существенно неоднозначные языки | неоднозначной]].

Будем доказывать от противного. Для этого произведем [[M-сводимость|m-сведение]] множества решений [[Примеры неразрешимых задач: проблема соответствий Поста|проблемы соответствий постаПоста]] (''post correspondence problem'') к множеству решений нашей задачи. А так как множество решений ПСП неразрешимо, то из 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>S \Rightarrow rightarrow A </tex> <tex> | B </tex>

<tex>A \Rightarrow rightarrow x_iAz_i</tex>

<tex>A \Rightarrow rightarrow \varepsilon</tex>

<tex>B \Rightarrow rightarrow y_iBz_i</tex>

<tex>B \Rightarrow rightarrow \varepsilon</tex>

Заметим, что любое слово <tex>w</tex>, выводимое в этой грамматике, может быть представлено в виде <tex>w=x_{i1}x_{i2}...x_{ik}z_{ik}z_{ik-1}...z_{i1}</tex> или <tex>w=y_{i1}y_{i2}...y_{ik}z_{ik}z_{ik-1}...z_{i1}</tex>, причем если <tex>L</tex> неоднозначна, то слово можно вывести двумя способами, и тогда <tex>w=x_{i1}x_{i2}...x_{ik}z_{ik}z_{ik-1}...z_{i1} = y_{i1}y_{i2}...y_{ik}z_{ik}z_{ik-1}...z_{i1}</tex>. Так как это одно и тоже слово, то все <tex> z_{i} </tex> в этом слове равны. А каждое <tex> z_{i} </tex> однозначно задает правило, по которому мы выводили слово. ЗначитПоэтому, если бы мы умели решать сформулированную нами ПСП, то могли бы сказать , однозначна грамматика или нет. То есть, если ПСП имеет решение, то мы можем восстановить два вывода слова. Если ПСП не имеет решения, то значит грамматика однозначна , и не существует два вывода двух выводов одного и того же слова. Таким образом, мы получили [[M-сводимость|m-сведение]] множества решений ПСП к множеству решений нашей задачи. А это значит, что задача об однозначности грамматики неразрешима.

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

== Литература См. также ==* [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора | Контекстно-свободные грамматики]]* [[Формальные грамматики]]* [[Иерархия Хомского формальных грамматик]]* [[Разрешимые (рекурсивные) языки | Разрешимые языки]]* [[m-сводимость]]* [[Примеры неразрешимых задач: проблема соответствий Поста | Проблема соответствий Поста]] == Источники информации ==

* [httphttps://en.wikipedia.org/wiki/Ambiguous_grammar ambiguous Wikipedia {{---}} Ambiguous grammar - Wikipedia] 

 [[Категория: Примеры неразрешимых задач ]]