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