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

Материал из Викиконспекты
Перейти к: навигация, поиск
Теорема:
Не существует алгоритма определяющего по произвольной грамматике является ли она однозначной.
Доказательство:
[math]\triangleright[/math]

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


Таким образом не существует алгоритма определяющего по произвольной грамматике является ли она однозначной.
[math]\triangleleft[/math]

Литература

  • А. Маслов, Д. Стоцкий — Языки и автоматы.