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