|
Пусть [math] E [/math] — алфавит для постовской системы соответствия [math](x_1,\,x_2,\,...,\,x_n)[/math],[math](y_1,\,y_2,\,...,\,y_n)[/math]. Рассмотрим грамматику [math]L=\{E^{*}, N, P, S\}[/math], где [math]E^{*}=E+\{z_i\}[/math], где множество [math]\{z_i\}=(z_1,\,z_2,\,...,\,z_n)[/math] — множество символов не встречающихся в алфавите [math]E[/math].
Возьмем правила:
[math]S \Rightarrow x_iAz_i[/math]
[math]S \Rightarrow y_iBz_i[/math]
[math]A \Rightarrow x_iAz_i[/math]
[math]A \Rightarrow e[/math]
[math]B \Rightarrow y_iBz_i[/math]
[math]B \Rightarrow e[/math]
Предположим ССП имеет решение [math](i_1-i_k)[/math]. Следовательно [math]x_{i1}-x_{ik}=y_{i1}-y_{ik}[/math], значит [math]x_{i1}-x_{ik}+z_{ik}-z_{i1}=y_{i1}-y_{ik}+z_{ik}-z_{i1}[/math]. Значит это слово можно вывести двумя способами. То есть такая грамматика будет неоднозначной.
Предположим, что построенная грамматика не однозначна. Тогда существует слово [math]w[/math], которое можно вывести хотя бы двумя способами. Значит оно выводится через правила
[math]A[/math] и [math]B[/math], то есть существует последовательность [math]i_1-i_k[/math] такая, что [math]w=x_{i1}-x_{ik}+z_{ik}-z_{i1}=y_{i1}-y_{ik}+z_{ik}-z_{i1}[/math], значит проблема соответствии поста имеет решение. но проблема соотв поста не
разрешима алгоритмически. Получили противоречие.
Таким образом не существует алгоритма определяющего по произвольной грамматике является ли она однозначной. |
