editor
143
правки
Изменения
Нет описания правки
<tex>B \Rightarrow \varepsilon</tex>
Заметим, что любое слово <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>i \ne j</tex> <tex>z_{i} \ne z_{j}</tex>, хвост последовательности однозначно задает ее. Таким образом, мы получили [[M-сводимость|m-сведение]] множества решений ПСП к множеству решений нашей задачи, так как если существует решение ПСП, то существует такой поднабор индексов, что слово <tex>w</tex> выводится двумя способами, то есть грамматика неоднозначна.
Таким образом, не существует алгоритма, определяющего по произвольной грамматике, является ли она однозначной.
