Lemat Ogdena

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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 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 uv^kwx^ky \in L