Изменения
Нет описания правки
Не существует алгоритма определяющего по произвольной грамматике является ли она однозначной.
|proof=
Пусть <tex> E </tex> — алфавит для постовской системы соответствия <tex>(x_1,\,x_2,\,...,\,x_n)</tex>,<tex>(y_1,\,y_2,\,...,\,yn)</tex>. Рассмотрим грамматику <tex>L=\{E^{*}, N, P, S\}</tex>, где <tex>E^{*}=E+(z_i)</tex> при <tex>z_i \in N</tex>.
Возьмем правила:
<tex>S \Rightarrow a_iAz_i</tex>
<tex>S \Rightarrow b_iBz_i</tex>
<tex>A \Rightarrow a_iAz_i</tex>
<tex>A \Rightarrow e</tex>
<tex>B \Rightarrow b_iBz_i</tex>
<tex>B \Rightarrow e</tex>
Предположим ССП имеет решение <tex>(i_1-i_k)</tex>. Следовательно <tex>x_{i1}-x_{ik}=y_{i1}-y_{ik}</tex>, значит <tex>x_{i1}-x_{ik}+z_{ik}-z_{i1}=y_{i1}-y_{ik}+z_{ik}-z_{i1}</tex>. Значит это слово можно вывести двумя способами. То есть такая грамматика будет неоднозначной.
Предположим, что построенная грамматика не однозначна. Тогда существует слово <tex>w</tex>, которое можно вывести хотя бы двумя способами. Значит оно выводится через правила
<tex>A</tex> и <tex>B</tex>, то есть существует последовательность <tex>i_1-i_k</tex> такая, что <tex>w=x_{i1}-x_{ik}+z_{ik}-z_{i1}=y_{i1}-y_{ik}+z_{ik}-z_{i1}</tex>, значит проблема соответствии поста имеет решение. но проблема соотв поста не
разрешима алгоритмически. Получили противоречие.
Таким образом не существует алгоритма определяющего по произвольной грамматике является ли она однозначной.
== Литература ==
* А. Маслов, Д. Стоцкий — Языки и автоматы.
}}
