Примеры неразрешимых задач: однозначность грамматики

Теорема:

Не существует алгоритма, определяющего по произвольной грамматике, является ли она однозначной.

Доказательство:

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

[math]\triangleleft[/math]

Литература

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