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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 29: Строка 29:
  
 
Таким образом не существует алгоритма определяющего по произвольной грамматике является ли она однозначной.
 
Таким образом не существует алгоритма определяющего по произвольной грамматике является ли она однозначной.
 +
 +
}}
  
 
== Литература ==
 
== Литература ==
 
* А. Маслов, Д. Стоцкий — Языки и автоматы.
 
* А. Маслов, Д. Стоцкий — Языки и автоматы.
 
}}
 

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

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

Литература

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