Lemat Ogdena

Ten artykuł od 2022-12 wymaga zweryfikowania podanych informacji.

Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Google Books • Google Scholar • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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 ${\displaystyle L}$ istnieje taka stała ${\displaystyle n,}$ że dla każdego słowa ${\displaystyle z\in L,}$ zawierającego co najmniej ${\displaystyle n}$ wyróżnionych pozycji, możemy podzielić ${\displaystyle z}$ na ${\displaystyle uvwxy}$ w taki sposób, że:

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

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