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

  • słowo vx zawiera (przynajmniej jedną) wyróżnioną pozycję
  • słowo vwx zawiera co najwyżej n wyróżnionych pozycji
  • dla każdego k mamy uv^kwx^ky \in L