Pumpelemmaet for kontekstfrie språk

I teorien om formelle språk beskriver pumpelemmaet for 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 $s=uvwxy$. 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ⁿwxⁿy er i L for enhver n ≥ 0.

Uformell forklaring av definisjonen

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

• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Seksjon 1.4: Nonregular Languages, ss. 77–83. Seksjon 2.3: Non-context-free Languages, ss. 115–119..