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 istnieje taka stała że dla każdego słowa zawierającego co najmniej wyróżnionych pozycji, możemy podzielić na w taki sposób, że: słowo zawiera (przynajmniej jedną) wyróżnioną pozycję, słowo zawiera co najwyżej wyróżnionych pozycji, dla każdego mamy
Lemat o pompowaniu dla języków bezkontekstowych jest szczególnym przypadkiem, gdzie wszystkie litery słowa są wyróżnione.
Kategoria:Języki formalne O