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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 25 промежуточных версий 8 участников)
Строка 1: Строка 1:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
−
Не существует алгоритма, определяющего по произвольной грамматике, является ли она однозначной.
+
Не существует алгоритма, определяющего по произвольной грамматике, является ли она [[Существенно неоднозначные языки | неоднозначной]].
 
|proof=
 
|proof=
−
Пусть <tex> E </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,\, \ldots ,\,x_n)</tex>, <tex>(y_1,\,y_2,\, \ldots ,\,y_n)</tex>. Рассмотрим грамматику <tex>L=\{\Sigma^{*}, N, P, S\}</tex>, где <tex> \Sigma^{*}= \Sigma+\{z_i\}</tex> и <tex>\{z_i\}=\{z_1,\,z_2,\, \ldots ,\,z_n\}</tex> {{---}} множество символов, не встречающихся в алфавите <tex> \Sigma</tex>. Символы <tex> \{z_i\} </tex> можно воспринимать как номера правил, по которым мы будем выводить слова в нашей грамматике. 
  
 +
Зададим грамматику <tex>L</tex> следующими правилами:
  
−
Возьмем правила:
+
<tex>S \rightarrow A </tex> <tex> | B </tex>
  
−
<tex>S \Rightarrow x_iAz_i</tex>
+
<tex>A \rightarrow x_iAz_i</tex>
  
−
<tex>S \Rightarrow y_iBz_i</tex>
+
<tex>A \rightarrow \varepsilon</tex>
  
−
<tex>A \Rightarrow x_iAz_i</tex>
+
<tex>B \rightarrow y_iBz_i</tex>
  
−
<tex>A \Rightarrow e</tex>
+
<tex>B \rightarrow \varepsilon</tex>
  
−
<tex>B \Rightarrow y_iBz_i</tex>
+
Заметим, что любое слово <tex>w</tex>, выводимое в этой грамматике, может быть представлено в виде <tex>w=x_{i1}x_{i2} \ldots x_{ik}z_{ik}z_{ik-1} \ldots z_{i1}</tex> или <tex>w=y_{i1}y_{i2} \ldots y_{ik}z_{ik}z_{ik-1} \ldots z_{i1}</tex>, причем, если <tex>L</tex> неоднозначна, то слово можно вывести двумя способами, и тогда <tex>w=x_{i1}x_{i2} \ldots x_{ik}z_{ik}z_{ik-1} \ldots z_{i1} = y_{i1}y_{i2} \ldots y_{ik}z_{ik}z_{ik-1} \ldots z_{i1}</tex>. Так как это одно и тоже слово, то все <tex> z_{i} </tex> в этом слове равны. А каждое <tex> z_{i} </tex> однозначно задает правило, по которому мы выводили слово.
  
−
<tex>B \Rightarrow e</tex>
+
Поэтому, если бы мы умели решать сформулированную нами ПСП, то могли бы сказать, однозначна грамматика или нет. То есть, если ПСП имеет решение, то мы можем восстановить два вывода слова. Если ПСП не имеет решения, то грамматика однозначна, и не существует двух выводов одного и того же слова. Таким образом, мы получили [[M-сводимость|m-сведение]] множества решений ПСП к множеству решений нашей задачи. А это значит, что задача об однозначности грамматики неразрешима.
  
−
Предположим, ССП имеет решение <tex>(i_1,\,i_2,\,...,\,i_k)</tex>. Следовательно, <tex>x_{i1}x_{i2}...x_{ik}=y_{i1}y_{i2}...y_{ik}</tex>, значит, <tex>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>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>, значит проблема соответствий Поста имеет решение, но она не разрешима алгоритмически. Получили противоречие.
 
  
 +
}}
  
−
Таким образом, не существует алгоритма, определяющего по произвольной грамматике, является ли она однозначной.
+
== См. также ==
 +
* [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора | Контекстно-свободные грамматики]]
 +
* [[Формальные грамматики]]
 +
* [[Иерархия Хомского формальных грамматик]]
 +
* [[Разрешимые (рекурсивные) языки | Разрешимые языки]]
 +
* [[m-сводимость]]
 +
* [[Примеры неразрешимых задач: проблема соответствий Поста | Проблема соответствий Поста]]
  
−
}}
+
== Источники информации ==
 +
* А. Маслов, Д. Стоцкий — Языки и автоматы. Издательство Мир, 1975, -361 с.
 +
* [https://en.wikipedia.org/wiki/Ambiguous_grammar Wikipedia {{---}} Ambiguous grammar]
  
−
== Литература ==
+
[[Категория: Теория формальных языков]]
−
* А. Маслов, Д. Стоцкий — Языки и автоматы.
+
[[Категория: Теория вычислимости]]
 +
[[Категория: Примеры неразрешимых задач]]

Текущая версия на 19:12, 4 сентября 2022

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

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

Пусть [math] \Sigma [/math] — алфавит для экземпляра ПСП [math](x_1,\,x_2,\, \ldots ,\,x_n)[/math], [math](y_1,\,y_2,\, \ldots ,\,y_n)[/math]. Рассмотрим грамматику [math]L=\{\Sigma^{*}, N, P, S\}[/math], где [math] \Sigma^{*}= \Sigma+\{z_i\}[/math] и [math]\{z_i\}=\{z_1,\,z_2,\, \ldots ,\,z_n\}[/math] — множество символов, не встречающихся в алфавите [math] \Sigma[/math]. Символы [math] \{z_i\} [/math] можно воспринимать как номера правил, по которым мы будем выводить слова в нашей грамматике.

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

[math]S \rightarrow A [/math] [math] | 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} \ldots x_{ik}z_{ik}z_{ik-1} \ldots z_{i1}[/math] или [math]w=y_{i1}y_{i2} \ldots y_{ik}z_{ik}z_{ik-1} \ldots z_{i1}[/math], причем, если [math]L[/math] неоднозначна, то слово можно вывести двумя способами, и тогда [math]w=x_{i1}x_{i2} \ldots x_{ik}z_{ik}z_{ik-1} \ldots z_{i1} = y_{i1}y_{i2} \ldots y_{ik}z_{ik}z_{ik-1} \ldots z_{i1}[/math]. Так как это одно и тоже слово, то все [math] z_{i} [/math] в этом слове равны. А каждое [math] z_{i} [/math] однозначно задает правило, по которому мы выводили слово.

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

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

См. также

Источники информации

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Примеры_неразрешимых_задач:_однозначность_грамматики&oldid=84608»