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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 2: Строка 2:
 
|id = Лемма
 
|id = Лемма
 
|statement =
 
|statement =
Пусть <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 =
 
Для доказательства построим [[Автоматы с магазинной памятью|МП-автомат]] с допуском по допускающему состоянию.
 
Для доказательства построим [[Автоматы с магазинной памятью|МП-автомат]] с допуском по допускающему состоянию.

Версия 01:23, 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]\triangleleft[/math]