Изменения

Заметим, что любое слово <tex>w</tex>, выводимое в этой грамматике, может быть представлено в виде <tex>w=x_{i1}x_{i2}...x_{ik}z_{ik}z_{ik-1}...z_{i1}=</tex> или <tex>w=y_{i1}y_{i2}...y_{ik}z_{ik}z_{ik-1}...z_{i1}</tex>, причем если <tex>L</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>. Поскольку для любых <tex>\forall i, j : i \ne j</tex> <tex>z_{i} \ne z_{j}</tex>, хвост последовательности однозначно задает ее. Таким образом, мы получили [[M-сводимость|m-сведение]] множества решений ПСП к множеству решений нашей задачи, так как если существует решение ПСП, то существует такой поднабор индексов, что слово <tex>w</tex> выводится двумя способами, то есть грамматика неоднозначна.