Изменения

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

Лемма Огдена

1042 байта добавлено, 11:05, 1 декабря 2011
мчн
{{Лемма Огдена
|statement=
Пусть <tex>L</tex> — [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободный язык]] над алфавитом <tex>\Sigma</tex>. Существует такое <tex>n</tex>, что для любого слова <tex>\omega</tex>, длины не менее <tex>n</tex>, и для любых выделенных в <tex>\omega</tex> не менее <tex>n</tex> позиций, <tex>\omega</tex> может быть представлено в виде <tex>\omega=uvxyz</tex>, так что:
# либо <tex>uvx</tex>, либо <tex>xyz</tex> содержат все выделенные позиции;
# <tex>vxy</tex> содержат более <tex>n</tex> выделенных позиций;
# существует <tex>A \in L</tex>, такой что <tex>S \Rightarrow^{*} uAz \Rightarrow^{*} uvAyz \Rightarrow^{*} uvxyz</tex>
|proof=
}}
Анонимный участник

Навигация