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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 4: Строка 4:
 
Пусть <tex>a_1, a_2, ..., a_n</tex> набор слов над алфавитом <tex>\Sigma </tex>. И пусть <tex>List(a_1, a_2, ... a_n) </tex> {{---}} язык над алфавитом <tex> \Sigma \cup \{1, 2, ..., n  \}</tex>(для простоты будем считать, что <tex> \Sigma \cap \{1, 2, ..., n\} = \varnothing </tex>), каждое слово которого имеет вид <tex> i_1i_2...i_ka_{i_k}a_{i_{k-1}}...a_{i_1} </tex>, где <tex> i_j \in \{1, 2, ..., n\} </tex>. Тогда <tex> \overline {List(a_1, a_2, ..., a_n)} </tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора | контекстно-свободный]].
 
Пусть <tex>a_1, a_2, ..., a_n</tex> набор слов над алфавитом <tex>\Sigma </tex>. И пусть <tex>List(a_1, a_2, ... a_n) </tex> {{---}} язык над алфавитом <tex> \Sigma \cup \{1, 2, ..., n  \}</tex>(для простоты будем считать, что <tex> \Sigma \cap \{1, 2, ..., n\} = \varnothing </tex>), каждое слово которого имеет вид <tex> i_1i_2...i_ka_{i_k}a_{i_{k-1}}...a_{i_1} </tex>, где <tex> i_j \in \{1, 2, ..., n\} </tex>. Тогда <tex> \overline {List(a_1, a_2, ..., a_n)} </tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора | контекстно-свободный]].
 
|proof =
 
|proof =
Для доказательства построим [[Автоматы с магазинной памятью|МП-автомат]] с допуском по допускающему состоянию.
+
Для доказательства построим [[Автоматы с магазинной памятью|МП-автомат]] с допуском по допускающему состоянию:
 +
 
 +
*<tex> \Sigma = \{a_1, a_2, ..., a_n\} \cup \{1, 2, ..., n\} </tex>;
 +
*<tex> \Gamma = \Sigma \cup z_0 </tex>;
 +
*<tex> Q = \{ S_0, S_1\} </tex>, где <tex> S_0 </tex> {{---}} стартовое состояние, а <tex> S_1 </tex> {{---}} допускающее.
 +
 
 +
Переходы определим следующим образом:
 +
 
 +
*<tex>\delta(S_0, i, \alpha) = \langle S_0, a_i \alpha \rangle, i \in  \{1, 2, ..., n  \}</tex>;
 +
*<tex> \delta(S_0, a_i, i) = \langle S_0, \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_1, c, \alpha) = \langle S_1, \alpha \rangle </tex>, для любых <tex> c </tex> и <tex> \alpha </tex>.
 +
 
 +
Несложно увидеть, что любое слово, принадлежащее <tex> {List(a_1, a_2, ..., a_n)} </tex>, оставит данный автомат в состоянии <tex> S_0 </tex>, в противном случае переведет его в допускающее состояние <tex> S_1 </tex>.
 
}}
 
}}
  

Версия 02:48, 3 января 2014

Лемма:
Пусть [math]a_1, a_2, ..., a_n[/math] набор слов над алфавитом [math]\Sigma [/math]. И пусть [math]List(a_1, a_2, ... a_n) [/math] — язык над алфавитом [math] \Sigma \cup \{1, 2, ..., n \}[/math](для простоты будем считать, что [math] \Sigma \cap \{1, 2, ..., n\} = \varnothing [/math]), каждое слово которого имеет вид [math] i_1i_2...i_ka_{i_k}a_{i_{k-1}}...a_{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\} [/math], где [math] S_0 [/math] — стартовое состояние, а [math] S_1 [/math] — допускающее.

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

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