Redigerer Pumpelemmaet for kontekstfrie språk

I teorien om [[Formelt språk|formelle språk]] beskriver pumpelemmaet for [[Kontekstfritt språk|kontekstfrie språk]] en fundamental egenskap for kontekstfrie språk. Lemmaet er en generalisering av [[pumpelemmaet for regulære språk]].

Det brukes ofte for å føre et motsigelsesbevis for at et språk ikke er kontekstfritt. Det kan ikke brukes til å bevise at et språk faktisk er kontekstfritt.

== Formell definisjon ==
Hvis et språk L er kontekstfritt eksisterer det ei pumpelengde som er større enn én sånn at enhver streng s i språket som er lengde enn pumpelengda kan deles inn i følgende streng <math>s=uvwxy</math>. hvor u, v, w, x og y er substrenger. Videre må følgende krav være oppfylt for at det skal være et kontekstfritt språk
: 1. |''vwx''| ≤ ''p'',
: 2. |''vx''| ≥ 1, og
: 3. ''uv<sup>n</sup>wx<sup>n</sup>y'' er i ''L'' for enhver ''n'' ≥ 0.

== Uformell forklaring av definisjonen ==
Hvis vi{{hvem}} følger den formelle definisjonen sies det at v og x gjentas et vilkårlig antall ganger i strengen og utgjør pumpingen av strengen. Alle kontekstfrie språk har denne egenskapen, hvis ikke er det ikke et kontekstfritt språk. Endelige språk oppfyller pumpelemmaet ved å la pumpelengda være den maksimale strenglengda i språket pluss én. Pluss én følger fra prinsippet om at det skal kunne pumpes, dvs. at det er en substreng som skal kunne repetere et vilkårlig antall ganger.

== Litteratur ==
* {{cite book|author=[[Michael Sipser]]|year=1997|title=Introduction to the Theory of Computation|url=https://archive.org/details/introductiontoth00sips|publisher=PWS Publishing|isbn=0-534-94728-X}} Seksjon 1.4: Nonregular Languages, ss.&nbsp;77–83. Seksjon 2.3: Non-context-free Languages, ss.&nbsp;115–119..

[[Kategori:Formelle språk]]