Неразрешимость задачи об эквивалентности КС-грамматик — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 8: Строка 8:
 
*<tex> \Sigma = \{a_1, a_2, ..., a_n\} \cup \{1, 2, ..., n\} </tex>;
 
*<tex> \Sigma = \{a_1, a_2, ..., a_n\} \cup \{1, 2, ..., n\} </tex>;
 
*<tex> \Gamma = \Sigma \cup z_0 </tex>;
 
*<tex> \Gamma = \Sigma \cup z_0 </tex>;
*<tex> Q = \{ S_0, S_1, S_2\} </tex>, где <tex> S_0 </tex> {{---}} стартовое состояние, а <tex> S_1 </tex> {{---}} допускающее.  
+
*<tex> Q = \{ S_0, S_1, S_2\} </tex>, где <tex> S_0 </tex> {{---}} стартовое состояние, а <tex> S_2 </tex> {{---}} допускающее.  
  
 
Переходы определим следующим образом:
 
Переходы определим следующим образом:
  
 
*<tex> \delta(S_0, a_i, \alpha) = \langle S_0, a_i \alpha \rangle, i \in  \{1, 2, ..., n  \}</tex>;
 
*<tex> \delta(S_0, a_i, \alpha) = \langle S_0, a_i \alpha \rangle, i \in  \{1, 2, ..., n  \}</tex>;
*<tex>\delta(S_0, i, a_i) = \langle S_2, \varepsilon \rangle, i \in  \{1, 2, ..., n  \}</tex>;
+
*<tex>\delta(S_0, i, a_i) = \langle S_1, \varepsilon \rangle, i \in  \{1, 2, ..., n  \}</tex>;
*<tex> \delta(S_0, c, \alpha) = \langle S_1, \alpha \rangle </tex>, для всех других <tex> c  </tex> и  <tex> \alpha </tex>, не подходящих под первые два правила;
+
*<tex> \delta(S_0, c, \alpha) = \langle S_2, \alpha \rangle </tex>, для всех других <tex> c  </tex> и  <tex> \alpha </tex>, не подходящих под первые два правила;
*<tex> \delta(S_1, c, \alpha) = \langle S_1, \alpha \rangle </tex>, для любых <tex> c </tex> и <tex> \alpha </tex>;
+
*<tex> \delta(S_1, i, a_i) = \langle S_1, \varepsilon \rangle, i \in \{1, 2, ..., n\}</tex>;
*<tex> \delta(S_2, i, a_i) = \langle S_2, \varepsilon \rangle, i \in \{1, 2, ..., n\}</tex>;
+
*<tex> \delta(S_1, c, \alpha) = \langle S_2, \alpha \rangle </tex>, для всех <tex> c </tex> и <tex> \alpha </tex>, кроме случая, когда <tex> c = i </tex> и <tex> \alpha = a_i </tex>;
*<tex> \delta(S_2, c, \alpha) = \langle S_1, \alpha \rangle </tex>, для всех <tex> c </tex> и <tex> \alpha </tex>, кроме случая, когда <tex> c = i </tex> и <tex> \alpha = a_i </tex>.  
+
*<tex> \delta(S_2, c, \alpha) = \langle S_2, \alpha \rangle </tex>, для любых <tex> c </tex> и <tex> \alpha </tex>.
  
Несложно увидеть, что любое слово, принадлежащее <tex> {List(a_1, a_2, ..., a_n)} </tex>, оставит данный автомат в состоянии <tex> S_2 </tex>, в противном случае переведет его в допускающее состояние <tex> S_1 </tex>.
+
Несложно увидеть, что любое слово, принадлежащее <tex> {List(a_1, a_2, ..., a_n)} </tex>, оставит данный автомат в состоянии <tex> S_1 </tex>, в противном случае переведет его в допускающее состояние <tex> S_2 </tex>.
 
}}
 
}}
  

Версия 16:25, 3 января 2014

Лемма:
Пусть [math] List(a_1, a_2, ... a_n) [/math] для набора слов [math](a_1, a_2, ..., a_n) [/math] — язык над алфавитом [math] \{a_1, a_2, ..., a_n\} \cup \{1, 2, ..., n \}[/math](для простоты будем считать, что [math] \{a_1, a_2, ..., a_n\} \cap \{1, 2, ..., n\} = \varnothing [/math]), каждое слово которого имеет вид [math] a_{i_1}a_{i_2}...a_{i_k}i_ki_{k-1}...i_1 [/math], где [math] i_j \in \{1, 2, ..., n\} [/math]. Тогда [math] \overline {List(a_1, a_2, ..., a_n)} [/math] контекстно-свободный.
Доказательство:
[math]\triangleright[/math]

Для доказательства построим МП-автомат с допуском по допускающему состоянию:

  • [math] \Sigma = \{a_1, a_2, ..., a_n\} \cup \{1, 2, ..., n\} [/math];
  • [math] \Gamma = \Sigma \cup z_0 [/math];
  • [math] Q = \{ S_0, S_1, S_2\} [/math], где [math] S_0 [/math] — стартовое состояние, а [math] S_2 [/math] — допускающее.

Переходы определим следующим образом:

  • [math] \delta(S_0, a_i, \alpha) = \langle S_0, a_i \alpha \rangle, i \in \{1, 2, ..., n \}[/math];
  • [math]\delta(S_0, i, a_i) = \langle S_1, \varepsilon \rangle, i \in \{1, 2, ..., n \}[/math];
  • [math] \delta(S_0, c, \alpha) = \langle S_2, \alpha \rangle [/math], для всех других [math] c [/math] и [math] \alpha [/math], не подходящих под первые два правила;
  • [math] \delta(S_1, i, a_i) = \langle S_1, \varepsilon \rangle, i \in \{1, 2, ..., n\}[/math];
  • [math] \delta(S_1, c, \alpha) = \langle S_2, \alpha \rangle [/math], для всех [math] c [/math] и [math] \alpha [/math], кроме случая, когда [math] c = i [/math] и [math] \alpha = a_i [/math];
  • [math] \delta(S_2, c, \alpha) = \langle S_2, \alpha \rangle [/math], для любых [math] c [/math] и [math] \alpha [/math].
Несложно увидеть, что любое слово, принадлежащее [math] {List(a_1, a_2, ..., a_n)} [/math], оставит данный автомат в состоянии [math] S_1 [/math], в противном случае переведет его в допускающее состояние [math] S_2 [/math].
[math]\triangleleft[/math]
Теорема:
Задача об эквивалентности двух КС-грамматик неразрешима
Доказательство:
[math]\triangleright[/math]

Будем доказывать от противного.

Предположим, что данная задача разрешима. Тогда покажем, как с помощью нее разрешить язык ПСП.

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