Изменения

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

Будем доказывать от противного. Для этого произведем [[M-сводимость|m-сведение]] множества решений [[Примеры неразрешимых задач: проблема соответствий Поста|проблемы соответствий Поста]] к множеству решений нашей задачи. А так как множество решений ПСП неразрешимо, то из m-сведения будет следовать неразрешимость нашей задачи. Пусть <tex> E \Sigma </tex> — {{---}} алфавит для постовской системы соответствия экземпляра ПСП <tex>(x_1,\,x_2,\,...\ldots ,\,x_n)</tex>,<tex>(y_1,\,y_2,\,...\ldots ,\,yny_n)</tex>. Рассмотрим грамматику <tex>L=\{E\Sigma^{*}, N, P, S\}</tex>, где <tex>E\Sigma^{*}=E\Sigma+(\{z_i\}</tex> и <tex>\{z_i)\}=\{z_1,\,z_2,\, \ldots ,\,z_n\}</tex> {{---}} множество символов, не встречающихся в алфавите <tex> \Sigma</tex> при . Символы <tex>\{z_i \in N} </tex>можно воспринимать как номера правил, по которым мы будем выводить слова в нашей грамматике.

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

<tex>S A \Rightarrow y_iBz_irightarrow \varepsilon</tex>

<tex>A B \Rightarrow x_iAz_irightarrow y_iBz_i</tex>

<tex>A B \Rightarrow erightarrow \varepsilon</tex>

Заметим, что любое слово <tex>B w</tex>, выводимое в этой грамматике, может быть представлено в виде <tex>w=x_{i1}x_{i2} \Rightarrow y_iBz_ildots 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>однозначно задает правило, по которому мы выводили слово.

Предположим ССП имеет решение <tex>(i_1-i_k)</tex>. Следовательно <tex>x_{i1}-x_{ik}=y_{i1}-y_{ik}</tex>, значит <tex>x_{i1}-x_{ik}+z_{ik}-z_{i1}=y_{i1}-y_{ik}+z_{ik}-z_{i1}</tex>. Значит это слово можно вывести двумя способами. То есть такая грамматика будет неоднозначной.  ПредположимПолучили, что построенная грамматика не однозначна. Тогда существует слово <tex>w</tex>, которое можно вывести хотя бы двумя способами. Значит оно выводится через правила <tex>A</tex> и <tex>B</tex>, то есть существует последовательность <tex>i_1-i_k</tex> такаяалгоритма, что <tex>w=x_{i1}-x_{ik}+z_{ik}-z_{i1}=y_{i1}-y_{ik}+z_{ik}-z_{i1}</tex>определяющего по произвольной грамматике, значит проблема соответствии поста имеет решение. но проблема соотв поста не разрешима алгоритмически. Получили противоречиеявляется ли она однозначной.

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

== Источники информации ==* А. Маслов, Д. Стоцкий — Языки и автоматы. Издательство Мир, 1975, -361 с.* [https://en.wikipedia.org/wiki/Ambiguous_grammar Wikipedia {{---}}Ambiguous grammar]