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

Теорема:

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

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

[math]\triangleright[/math]

Пусть [math] E [/math] — алфавит для постовской системы соответствия [math](x_1,\,x_2,\,...,\,x_n)[/math],[math](y_1,\,y_2,\,...,\,yn)[/math]. Рассмотрим грамматику [math]L=\{E^{*}, N, P, S\}[/math], где [math]E^{*}=E+(z_i)[/math] при [math]z_i \in N[/math]. Возьмем правила: [math]S \Rightarrow a_iAz_i[/math] [math]S \Rightarrow b_iBz_i[/math] [math]A \Rightarrow a_iAz_i[/math] [math]A \Rightarrow e[/math] [math]B \Rightarrow b_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], значит проблема соответствии поста имеет решение. но проблема соотв поста не разрешима алгоритмически. Получили противоречие. Таким образом не существует алгоритма определяющего по произвольной грамматике является ли она однозначной. Литература А. Маслов, Д. Стоцкий — Языки и автоматы.

[math]\triangleleft[/math]