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

Материал из Викиконспекты
Версия от 01:12, 3 января 2014; Warrior (обсуждение | вклад) (Новая страница: «{{Лемма |id = Лемма |statement = Пусть <tex>a_1, a_2, ..., a_n</tex> набор слов над алфавитом <tex>\Sigma </tex>. Пусть <...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Лемма:
Пусть [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] контекстно-свободный.