Примеры неразрешимых задач: однозначность грамматики

Теорема:

Не существует алгоритма, определяющего по произвольной грамматике, является ли она однозначной.

Доказательство:

[math]\triangleright[/math]

Пусть [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], значит проблема соответствий Поста имеет решение, но известно, что она не разрешима алгоритмически. Получили противоречие. Таким образом, не существует алгоритма, определяющего по произвольной грамматике, является ли она однозначной.

[math]\triangleleft[/math]

Литература

• А. Маслов, Д. Стоцкий — Языки и автоматы. Издательство Мир, 1975, -361 с.