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