Изменения
Нет описания правки
{{Теорема
|statement=
Не существует алгоритма, определяющего по произвольной грамматике, является ли она однозначной(''ambiguous grammar'').
|proof=
Будем доказывать от противного. Для этого произведем [[M-сводимость|m-сведение]] множества решений [[Примеры неразрешимых задач: проблема соответствий Поста|ПСПпроблемы соответствий поста]] (''post correspondence problem'') к множеству решений нашей задачи. А так как множество решений ПСП неразрешимо, то из m-сведения будет следовать неразрешимость нашей задачи.
Пусть <tex> \Sigma </tex> {{---}} алфавит для постовской системы соответствия <tex>(x_1,\,x_2,\,...,\,x_n)</tex>,<tex>(y_1,\,y_2,\,...,\,y_n)</tex>. Рассмотрим грамматику <tex>L=\{\Sigma^{*}, N, P, S\}</tex>, где <tex> \Sigma^{*}= \Sigma+\{z_i\}</tex> и <tex>\{z_i\}=\{z_1,\,z_2,\,...,\,z_n\}</tex> {{---}} множество символов, не встречающихся в алфавите <tex> \Sigma</tex>. Символы <tex> \{z_i\} </tex> можно воспринимать как номера правила, по которым мы будем выводить слова в нашей грамматике.
== Литература ==
* А. Маслов, Д. Стоцкий — Языки и автоматы. Издательство Мир, 1975, -361 с.
* [http://en.wikipedia.org/wiki/Ambiguous_grammar ambiguous grammar - Wikipedia]
[[Категория: Теория вычислимости]]
[[Категория: Примеры неразрешимых задач ]]
