Изменения

Пусть <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>.

Возьмем Пусть у грамматики <tex>L</tex> есть правила:

Предположим, что построенная грамматика <tex>L</tex> не однозначна. Тогда существует слово <tex>w</tex>, которое можно вывести хотя бы двумя способами. Значит, оно выводится через правила <tex>A</tex> и <tex>B</tex>, то есть существует последовательность <tex>(i_1,\,i_2,\,...,\,i_k)</tex> такая, что <tex>w=x_{i2}...x_{ik}z_{ik}z_{ik-1}...z_{i1}=</tex><tex>y_{i1}y_{i2}...y_{ik}z_{ik}z_{ik-1}...z_{i1}</tex>, значит проблема соответствий Поста имеет решение, но известно, что она не разрешима алгоритмически. Получили противоречие.