25
правок
Изменения
Нет описания правки
{{Теорема
|statement=
Не существует алгоритма, определяющего по произвольной грамматике, является ли она однозначной[[Существенно неоднозначные языки | неоднозначной]].
|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>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 rightarrow \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>однозначно задает правило, по которому мы выводили слово.
}}
== Источники информации ==
* А. Маслов, Д. Стоцкий — Языки и автоматы. Издательство Мир, 1975, -361 с.
* [https://en.wikipedia.org/wiki/Ambiguous_grammar Wikipedia {{---}} Ambiguous grammar]