Lemat Ogdena

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 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