Lemat Ogdena
Z Wikipedii
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 , 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