Изменения
Нет описания правки
Не существует алгоритма определяющего по произвольной грамматике является ли она однозначной.
|proof=
Пусть <tex> E </tex> — алфавит для постовской системы соответствия <tex>(x_1,\,x_2,\,...,\,x_n)</tex>,<tex>(y_1,\,y_2,\,...,\,y_n)</tex>. Рассмотрим грамматику <tex>L=\{E^{*}, N, P, S\}</tex>, где <tex>E^{*}=E+\{z_i\}</tex>, где множество <tex>\{z_i\}=(z_1,\,z_2,\,...,\,z_n)</tex> — множество символов не встречающихся в алфавите <tex>E</tex>.
