403
правки
Изменения
Нет описания правки
}}
{{Теорема
|statement= Задача об эквивалентности двух КС-грамматик неразрешима
|proof=
Будем доказывать от противного.
Предположим, что данная задача разрешима. Тогда покажем, как с помощью нее разрешить язык ПСП.
Пусть <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> и воспользовавшись предположением, что задача об эквивалентности КС-грамматик разрешима, мы разрешим и язык ПСП. Но язык ПСП неразрешим, следовательно, мы пришли к противоречию, а значит наше предположение неверно.
}}
[[Категория: Теория вычислимости]]
