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