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