<tex>B \Rightarrow \varepsilon</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_{i1}x_{i2}...x_{ik}z_{ik}z_{ikВыполним [[M-1}...z_{i1}=y_{i1}y_{i2}...y_{ik}z_{ik}z_{ikсводимость|m-1}сведение]] множества решений нашей задачи к множеству решений ПСП...z_{i1}=w</tex>. Значит, слово <tex>w</tex> можно вывести двумя способами. То есть такая грамматика будет неоднозначной. Предположим теперь, что построенная грамматика <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>, значит проблема соответствий Поста имеет решение, но известно, что она не разрешима алгоритмически. Получили противоречие.
