Примеры неразрешимых задач: однозначность грамматики — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
Не существует алгоритма определяющего по произвольной грамматике является ли она однозначной.
 
Не существует алгоритма определяющего по произвольной грамматике является ли она однозначной.
 
|proof=
 
|proof=
Пусть <tex> E </tex> — алфавит для постовской системы соответствия <tex>(x_1,\,x_2,\,...,\,x_n)</tex>,<tex>(y_1,\,y_2,\,...,\,y_n)</tex>. Рассмотрим грамматику <tex>L=\{E^{*}, N, P, S\}</tex>, где <tex>E^{*}=E+(z_i)</tex> при <tex>z_i \in N</tex>.
+
Пусть <tex> E </tex> — алфавит для постовской системы соответствия <tex>(x_1,\,x_2,\,...,\,x_n)</tex>,<tex>(y_1,\,y_2,\,...,\,y_n)</tex>. Рассмотрим грамматику <tex>L=\{E^{*}, N, P, S\}</tex>, где <tex>E^{*}=E+\{z_i\}</tex>,  где множество <tex>\{z_i\}</tex> — множество символов не встречающихся в алфавите <tex>E</tex>.
  
  

Версия 08:21, 15 января 2011

Теорема:
Не существует алгоритма определяющего по произвольной грамматике является ли она однозначной.
Доказательство:
[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\}[/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]

Литература

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