Lemat Ogdena

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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