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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
Не существует алгоритма, определяющего по произвольной грамматике, является ли она однозначной.
 
Не существует алгоритма, определяющего по произвольной грамматике, является ли она однозначной.
 
|proof=
 
|proof=
Пусть <tex> \Sigma </tex> — алфавит для постовской системы соответствия <tex>(x_1,\,x_2,\,...,\,x_n)</tex>,<tex>(y_1,\,y_2,\,...,\,y_n)</tex>. Рассмотрим грамматику <tex>L=\{\Sigma^{*}, N, P, S\}</tex>, где <tex> \Sigma^{*}= \Sigma+\{z_i\}</tex>,  где множество <tex>\{z_i\}=\{z_1,\,z_2,\,...,\,z_n\}</tex> — множество символов не встречающихся в алфавите <tex> \Sigma</tex>.
+
Пусть <tex> \Sigma </tex> — алфавит для постовской системы соответствия <tex>(x_1,\,x_2,\,...,\,x_n)</tex>,<tex>(y_1,\,y_2,\,...,\,y_n)</tex>. Рассмотрим грамматику <tex>L=\{\Sigma^{*}, N, P, S\}</tex>, где <tex> \Sigma^{*}= \Sigma+\{z_i\}</tex> и <tex>\{z_i\}=\{z_1,\,z_2,\,...,\,z_n\}</tex> — множество символов не встречающихся в алфавите <tex> \Sigma</tex>.
  
  
Возьмем правила:
+
Пусть у грамматики <tex>L</tex> есть правила:
  
 
<tex>S \Rightarrow x_iAz_i</tex>
 
<tex>S \Rightarrow x_iAz_i</tex>
Строка 23: Строка 23:
  
  
Предположим, что построенная грамматика не однозначна. Тогда существует слово <tex>w</tex>, которое можно вывести хотя бы двумя способами. Значит, оно выводится через правила   
+
Предположим, что построенная грамматика <tex>L</tex> не однозначна. Тогда существует слово <tex>w</tex>, которое можно вывести хотя бы двумя способами. Значит, оно выводится через правила   
<tex>A</tex> и <tex>B</tex>, то есть существует последовательность <tex>(i_1,\,i_2,\,...,\,i_k)</tex> такая, что <tex>w=x_{i2}...x_{ik}z_{ik}z_{ik-1}...z_{i1}=</tex><tex>y_{i1}y_{i2}...y_{ik}z_{ik}z_{ik-1}...z_{i1}</tex>, значит проблема соответствий Поста имеет решение, но она не разрешима алгоритмически. Получили противоречие.
+
<tex>A</tex> и <tex>B</tex>, то есть существует последовательность <tex>(i_1,\,i_2,\,...,\,i_k)</tex> такая, что <tex>w=x_{i2}...x_{ik}z_{ik}z_{ik-1}...z_{i1}=</tex><tex>y_{i1}y_{i2}...y_{ik}z_{ik}z_{ik-1}...z_{i1}</tex>, значит проблема соответствий Поста имеет решение, но известно, что она не разрешима алгоритмически. Получили противоречие.
  
  

Версия 01:42, 5 января 2012

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

Литература

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