Изменения
Нет описания правки
Не существует алгоритма определяющего по произвольной грамматике является ли она однозначной.
|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>.
<tex>B \Rightarrow e</tex>
Предположим ССП имеет решение <tex>(i_1-,\,i_2,\,...,\,i_k)</tex>. Следовательно <tex>x_{i1}-x_{i2}...x_{ik}=y_{i1}-y_{i2}...y_{ik}</tex>, значит <tex>x_{i1i2}-...x_{ik}+z_{ik}z_{ik-1}...z_{i1}=y_{i1}-y_{i2}...y_{ik}+z_{ik}z_{ik-1}...z_{i1}</tex>. Значит это слово можно вывести двумя способами. То есть такая грамматика будет неоднозначной.
Предположим, что построенная грамматика не однозначна. Тогда существует слово <tex>w</tex>, которое можно вывести хотя бы двумя способами. Значит оно выводится через правила
<tex>A</tex> и <tex>B</tex>, то есть существует последовательность <tex>(i_1-,\,i_2,\,...,\,i_k)</tex> такая, что <tex>w=x_{i1i2}-...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>, значит проблема соответствии поста имеет решение. но проблема соотв поста не разрешима алгоритмически. Получили противоречие.
