Изменения

Не существует алгоритма, определяющего по произвольной грамматике, является ли она [[wikipedia:ru:Неоднозначная грамматика | неоднозначной (англ. ''ambiguous grammar'')]].

Пусть <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>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> однозначно задает правило, по которому мы выводили слово.

* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BE%D0%BD%D1%82%D0%B5%D0%BA%D1%81%D1%82%D0%BD%D0%BE[Контекстно-%D1%81%D0%B2%D0%BE%D0%B1%D0%BE%D0%B4%D0%BD%D1%8B%D0%B5_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8свободные грамматики,_%D0%B2%D1%8B%D0%B2%D0%BE%D0%B4вывод,_%D0%BB%D0%B5%D0%B2%D0%BEлево-_%D0%B8_%D0%BF%D1%80%D0%B0%D0%B2%D0%BE%D1%81%D1%82%D0%BE%D1%80%D0%BE%D0%BD%D0%BD%D0%B8%D0%B9_%D0%B2%D1%8B%D0%B2%D0%BE%D0%B4и правосторонний вывод,_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D1%80%D0%B0%D0%B7%D0%B1%D0%BE%D1%80%D0%B0 дерево разбора | Контекстно-свободные грамматики]]* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8 [Формальные грамматики]]* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D0%B5%D1%80%D0%B0%D1%80%D1%85%D0%B8%D1%8F_%D0%A5%D0%BE%D0%BC%D1%81%D0%BA%D0%BE%D0%B3%D0%BE_%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA [Иерархия Хомского формальных грамматик]]* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D0%B5_[Разрешимые (%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B2%D0%BD%D1%8B%D0%B5рекурсивные)_%D1%8F%D0%B7%D1%8B%D0%BA%D0%B8 языки | Разрешимые языки]]* [http://neerc.ifmo.ru/wiki/index.php?title=M-%D1%81%D0%B2%D0%BE%D0%B4%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D1%8C [m-сводимость]]* [http[Примеры неразрешимых задач://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87:_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B9_%D0%9F%D0%BE%D1%81%D1%82%D0%B0 проблема соответствий Поста | Проблема соответствий Поста]]

* [httphttps://en.wikipedia.org/wiki/Ambiguous_grammar ambiguous Wikipedia {{---}} Ambiguous grammar - Wikipedia]