Изменения

Перейти к: навигация, поиск
Новая страница: «{{Лемма |id = Лемма |statement = Пусть <tex>a_1, a_2, ..., a_n</tex> набор слов над алфавитом <tex>\Sigma </tex>. Пусть <...»
{{Лемма
|id = Лемма
|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> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора | контекстно-свободный]].

|proof =
}}
403
правки

Навигация