Изменения

Не существует алгоритма , определяющего по произвольной грамматике , является ли она однозначной.

Пусть <tex> E </tex> — алфавит для постовской системы соответствия <tex>(x_1,\,x_2,\,...,\,x_n)</tex>,<tex>(y_1,\,y_2,\,...,\,y_n)</tex>. Рассмотрим грамматику <tex>L=\{E\Sigma^{*}, N, P, S\}</tex>, где <tex>E\Sigma^{*}=E\Sigma+\{z_i\}</tex>, где множество <tex>\{z_i\}=\{z_1,\,z_2,\,...,\,z_n\}</tex> — множество символов не встречающихся в алфавите <tex>E\Sigma</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_{i2}...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_{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>, значит проблема соответствии поста соответствий Поста имеет решение. , но проблема соотв поста она не разрешима алгоритмически. Получили противоречие.

Таким образом , не существует алгоритма , определяющего по произвольной грамматике , является ли она однозначной.