Изменения

Пусть <tex>(x_1, x_2, ..., x_n)</tex> и <tex>(y_1, y_2, ..., y_n) </tex> входные последовательности для ПСП. Пусть <tex> L_1 = List(x_1, x_2, ..., x_n), L_2 = List(y_1, y_2, ..., y_n) </tex>. Тогда решение ПСП для последовательностей <tex>(x_1, x_2, ..., x_n)</tex> и <tex>(y_1, y_2, ..., y_n) </tex> существует только в том случае, когда <tex> L_1 \cap L_2 \ne \varnothing </tex>. Перейдя к дополнению и применив закон де Моргана, мы получим, что решения для заданных последовательностей существует, только когда <tex> \overline{L_1} \cup \overline{L_2} \ne \Sigma^* </tex>, где <tex> \Sigma </tex> {{---}} алфавит для языков <tex> L_1 </tex> и <tex> L_2 </tex>. Но по [[#Лемма|лемме]] <tex> \overline{L_1} </tex> и <tex> \overline{L_2} </tex> {{---}} контекстно-свободные. Так как КС-языки замкнуты относительно объединения, то язык <tex> \overline{L_1} \cup \overline{L_2} </tex> {{---}} контекстно-свободный. Построив КС-грамматики для языков <tex> \overline{L_1} \cup \overline{L_2} </tex> и <tex>\Sigma^*</tex> и воспользовавшись предположением, что задача об эквивалентности КС-грамматик разрешима, мы разрешим и язык ПСП. Но язык ПСП неразрешим, следовательно. Следовательно, мы пришли к противоречию, и значит наше предположение неверно.