Lemat Ogdena


Lemat Ogdena w encyklopedii

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

  • słowo v x {\displaystyle vx} zawiera (przynajmniej jedną) wyróżnioną pozycję,
  • słowo v w x {\displaystyle vwx} zawiera co najwyżej n {\displaystyle n} wyróżnionych pozycji,
  • dla każdego k {\displaystyle k} mamy u v k w x k y L . {\displaystyle uv^{k}wx^{k}y\in L.}
Na podstawie artykułu: "Lemat Ogdena" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy