Лемма Огдена

Лемма Огдена — результат, расширяющий утверждение леммы о разрастании для контекстно-свободных языков: если язык $L$ контекстно-свободен, то существует некоторое число $p>0$ (где $p$ может быть, а может и не быть длиной накачки), такое что для любой строки $w$ длины не меньше $p$ из $L$ и для любой «разметки» $p$ или более позиций в $w$, $w$ может быть представлено в виде:

$w=uvzyz$

где $u$, $v$, $x$, $y$, и $z$ — строки, такие что:

• $x$ содержит по меньшей мере одну помеченную позицию,
• либо и $u$ и $v$ содержат помеченную позицию, либо её содержат и $y$ и $z$,
• $vxy$ содержит не более $p$ отмеченных позиций, и
• $uv^{i}xy^{i}z$ принадлежит $L$ для любого $i\geqslant 0$.

Утверждение может использоваться для доказательства того, что данный язык не является контекстно-свободным в случаях, когда леммы о разрастании для контекстно-свободных языков недостаточно. Примером может быть язык $\{a^{i}b^{j}c^{k}d^{l}\mid i=0\vee j=k=l\}$. Также может применяться для доказательства существенной неоднозначности некоторых языков.

Если все позиции отмечены, утверждение эквивалентно лемме о разрастании для контекстно-свободных языков.

Литература

• Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1.