Изменения
Нет описания правки
Не существует алгоритма определяющего по произвольной грамматике является ли она однозначной.
|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 \in N}</tex> — множество символов не встречающихся в алфавите <tex>E</tex>.
