Lemat Ogdena

Szablon:Dopracować Lemat Ogdena – 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 pozycji, możemy podzielić $z$ na $uvwxy$ w taki sposób, że:

• słowo $vx$ zawiera (przynajmniej jedną) wyróżnioną pozycję,
• słowo $vwx$ zawiera co najwyżej $n$ wyróżnionych pozycji,
• dla każdego $k$ mamy $u{v}^{k}w{x}^{k}y\in L.$

Lemat o pompowaniu dla języków bezkontekstowych jest szczególnym przypadkiem, gdzie wszystkie litery słowa są wyróżnione.