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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 2: Строка 2:
 
|id = Лемма
 
|id = Лемма
 
|statement =
 
|statement =
Пусть <tex> List(a_1, a_2, \ldots, a_n) </tex> для набора слов <tex>(a_1, a_2, \ldots, a_n) </tex> {{---}} язык над алфавитом <tex> \{a_1, a_2, \ldots, a_n\} \cup \{1, 2, \ldots, n  \}</tex>(для простоты будем считать, что <tex> \{a_1, a_2, \ldots, a_n\}  \cap \{1, 2, \ldots, n\} = \varnothing </tex>), каждое слово которого имеет вид <tex> a_{i_1}a_{i_2} \ldots a_{i_k}i_ki_{k-1} \ldots i_1 </tex>, где <tex> i_j \in \{1, 2, \ldots, n\} </tex>. Тогда <tex> \overline {List(a_1, a_2, \ldots, a_n)} </tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора | контекстно-свободный]].
+
Пусть <tex> List(a_1, a_2, ... a_n) </tex> для набора слов <tex>(a_1, a_2, ..., a_n) </tex> {{---}} язык над алфавитом <tex> \{a_1, a_2, ..., a_n\} \cup \{1, 2, ..., n  \}</tex>(для простоты будем считать, что <tex> \{a_1, a_2, ..., a_n\}  \cap \{1, 2, ..., n\} = \varnothing </tex>), каждое слово которого имеет вид <tex> a_{i_1}a_{i_2}...a_{i_k}i_ki_{k-1}...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, \ldots, a_n\} \cup \{1, 2, \ldots, 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_2 </tex> {{---}} допускающее.  
 
*<tex> Q = \{ S_0, S_1, S_2\} </tex>, где <tex> S_0 </tex> {{---}} стартовое состояние, а <tex> S_2 </tex> {{---}} допускающее.  
Строка 12: Строка 12:
 
Переходы определим следующим образом:
 
Переходы определим следующим образом:
  
*<tex> \delta(S_0, a_i, \alpha) = \langle S_0, a_i \alpha \rangle, i \in  \{1, 2, \ldots, 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_1, \varepsilon \rangle, i \in  \{1, 2, \ldots, 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_2, \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, i, a_i) = \langle S_1, \varepsilon \rangle, i \in \{1, 2, \ldots, n\}</tex>;
+
*<tex> \delta(S_1, i, a_i) = \langle S_1, \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_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_2, \alpha \rangle </tex>, для любых <tex> c </tex> и <tex> \alpha </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, \ldots, a_n)} </tex>, оставит данный автомат в состоянии <tex> S_1 </tex>, в противном случае переведет его в допускающее состояние <tex> S_2 </tex>.
+
Несложно увидеть, что любое слово, принадлежащее <tex> {List(a_1, a_2, ..., a_n)} </tex>, оставит данный автомат в состоянии <tex> S_1 </tex>, в противном случае переведет его в допускающее состояние <tex> S_2 </tex>.
 
}}
 
}}
  
Строка 29: Строка 29:
 
Предположим, что данная задача разрешима. Тогда покажем, как с помощью нее разрешить язык [[Примеры неразрешимых задач: проблема соответствий Поста|ПСП]].
 
Предположим, что данная задача разрешима. Тогда покажем, как с помощью нее разрешить язык [[Примеры неразрешимых задач: проблема соответствий Поста|ПСП]].
  
Пусть <tex>(x_1, x_2, \ldots, x_n)</tex> и <tex>(y_1, y_2, \ldots, y_n) </tex> входные последовательности для ПСП. Пусть <tex> L_1 = List(x_1, x_2, \ldots, x_n), L_2 = List(y_1, y_2, \ldots, y_n) </tex>. Тогда решение ПСП для последовательностей <tex>(x_1, x_2, \ldots, x_n)</tex> и <tex>(y_1, y_2, \ldots, 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> и воспользовавшись предположением, что задача об эквивалентности КС-грамматик разрешима, мы разрешим и язык ПСП. Но язык ПСП неразрешим. Следовательно, мы пришли к противоречию, и наше предположение неверно.  
+
Пусть <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> и воспользовавшись предположением, что задача об эквивалентности КС-грамматик разрешима, мы разрешим и язык ПСП. Но язык ПСП неразрешим. Следовательно, мы пришли к противоречию, и наше предположение неверно.  
  
 
}}
 
}}

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: