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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 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>.
+
Будем доказывать от противного. Для этого произведем [[M-сводимость|m-сведение]] множества решений [[Примеры неразрешимых задач: проблема соответствий Поста|ПСП]] к множеству решений нашей задачи. А так как множество решений ПСП неразрешимо, то из m-сведения будет следовать неразрешимость нашей задачи.
 +
 
 +
Пусть <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> \{z_i\} </tex> можно воспринимать как номера правила, по которым мы будем выводить слова в нашей грамматике. 
  
 +
Зададим грамматику <tex>L</tex> следующими правилами:
  
Пусть у грамматики <tex>L</tex> есть правила:
+
<tex>S \Rightarrow A | B </tex>
 
 
<tex>S \Rightarrow x_iAz_i</tex>
 
 
 
<tex>S \Rightarrow y_iBz_i</tex>
 
  
 
<tex>A \Rightarrow x_iAz_i</tex>
 
<tex>A \Rightarrow x_iAz_i</tex>
Строка 21: Строка 20:
  
  
Заметим, что любое слово <tex>w</tex>, выводимое в этой грамматике, может быть представлено в виде <tex>w=x_{i1}x_{i2}...x_{ik}z_{ik}z_{ik-1}...z_{i1}=</tex> или <tex>w=y_{i1}y_{i2}...y_{ik}z_{ik}z_{ik-1}...z_{i1}</tex>, причем если <tex>L</tex> неоднозначна, то <tex>w=x_{i1}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>\forall i, j : i \ne j</tex> <tex>z_{i} \ne z_{j}</tex>, хвост последовательности однозначно задает ее. Таким образом, мы получили [[M-сводимость|m-сведение]] множества решений ПСП к множеству решений нашей задачи, так как если существует решение ПСП, то существует такой поднабор индексов, что слово <tex>w</tex> выводится двумя способами, то есть грамматика неоднозначна.
+
Заметим, что любое слово <tex>w</tex>, выводимое в этой грамматике, может быть представлено в виде <tex>w=x_{i1}x_{i2}...x_{ik}z_{ik}z_{ik-1}...z_{i1}</tex> или <tex>w=y_{i1}y_{i2}...y_{ik}z_{ik}z_{ik-1}...z_{i1}</tex>, причем если <tex>L</tex> неоднозначна, то слово можно вывести двумя способами, и тогда <tex>w=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}</tex>. Так как это одно и тоже слово, то все <tex> z_{i} </tex> в этом слове равны. А каждое <tex> z_{i} </tex> однозначно задает правило, по которому мы выводили слово. Значит, если бы мы умели решать сформулированную нами ПСП, то могли бы сказать однозначна грамматика или нет. То есть, если ПСП имеет решение, то мы можем восстановить два вывода слова. Если ПСП не имеет решения, то значит грамматика однозначна и не существует два вывода одного и того же слова. Таким образом, мы получили [[M-сводимость|m-сведение]] множества решений ПСП к множеству решений нашей задачи. А это значит, что задача об однозначности грамматики неразрешима.
  
 
Таким образом, не существует алгоритма, определяющего по произвольной грамматике, является ли она однозначной.
 
Таким образом, не существует алгоритма, определяющего по произвольной грамматике, является ли она однозначной.

Версия 22:47, 14 января 2013

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

Будем доказывать от противного. Для этого произведем m-сведение множества решений ПСП к множеству решений нашей задачи. А так как множество решений ПСП неразрешимо, то из m-сведения будет следовать неразрешимость нашей задачи.

Пусть [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] \{z_i\} [/math] можно воспринимать как номера правила, по которым мы будем выводить слова в нашей грамматике.

Зададим грамматику [math]L[/math] следующими правилами:

[math]S \Rightarrow A | B [/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]w[/math], выводимое в этой грамматике, может быть представлено в виде [math]w=x_{i1}x_{i2}...x_{ik}z_{ik}z_{ik-1}...z_{i1}[/math] или [math]w=y_{i1}y_{i2}...y_{ik}z_{ik}z_{ik-1}...z_{i1}[/math], причем если [math]L[/math] неоднозначна, то слово можно вывести двумя способами, и тогда [math]w=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}[/math]. Так как это одно и тоже слово, то все [math] z_{i} [/math] в этом слове равны. А каждое [math] z_{i} [/math] однозначно задает правило, по которому мы выводили слово. Значит, если бы мы умели решать сформулированную нами ПСП, то могли бы сказать однозначна грамматика или нет. То есть, если ПСП имеет решение, то мы можем восстановить два вывода слова. Если ПСП не имеет решения, то значит грамматика однозначна и не существует два вывода одного и того же слова. Таким образом, мы получили m-сведение множества решений ПСП к множеству решений нашей задачи. А это значит, что задача об однозначности грамматики неразрешима.

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

Литература

  • А. Маслов, Д. Стоцкий — Языки и автоматы. Издательство Мир, 1975, -361 с.