Изменения
Нет описания правки
Предположим, что построенная грамматика <tex>L</tex> не однозначна. Тогда существует слово <tex>w</tex>, которое можно вывести хотя бы двумя способами. Значит, оно выводится через правила
<tex>A</tex> и <tex>B</tex>, то есть существует последовательность <tex>(i_1,\,i_2,\,...,\,i_k)</tex> такая, что <tex>w=x_{i2i1}...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>, значит проблема соответствий Поста имеет решение, но известно, что она не разрешима алгоритмически. Получили противоречие.
