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