Lemat Ogdena

Lemat Ogdena to uogólnienie lematu o pompowaniu dla języków bezkontekstowych. Służy do udowadniania, że dany język nie jest językiem bezkontekstowym.

Lemat mówi że:
Dla każdego języka bezkontekstowego $L$ istnieje taka stała $n$, że dla każdego słowa $z \in L$, zawierającego co najmniej $n$ wyróżnionych symboli, możemy podzielić $z$ na $uvwxy$ w taki sposób, że:

• słowo $vx$ zawiera (przynajmniej jeden) wyróżniony symbol
• słowo $vwx$ zawiera co najwyżej $n$ wyróżnionych symboli
• dla każdego $k$ mamy $uv^kwx^ky \in L$