Изменения

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

Лемма Огдена

Нет изменений в размере, 13:07, 29 сентября 2015
Исправлена опечатка
{{Лемма
|statement=
Для каждой [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободный свободной грамматики]] <tex>\Gamma =\langle \Sigma, N, S \in N, P \subset N\times (\Sigma\cup N)^{*}\rangle</tex> существует такое <tex>n</tex>, что для любого слова <tex>\omega \in L(\Gamma)</tex> длины не менее <tex>n</tex> и для любых выделенных в <tex>\omega</tex> не менее <tex>n</tex> позиций, <tex>\omega</tex> может быть представлено в виде <tex>\omega=uvxyz</tex>, причем:
# <tex>x</tex> содержит выделенную позицию;
# либо <tex>u</tex> и <tex>v</tex>, либо <tex>y</tex> и <tex>z</tex> обе содержат выделенные позиции;
Анонимный участник

Навигация