Изменения
Нет описания правки
Не существует алгоритма, определяющего по произвольной грамматике, является ли она однозначной.
|proof=
Пусть <tex> E \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>.
