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 . 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. uvnwxny 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 Seksjon 1.4: Nonregular Languages, ss. 77–83. Seksjon 2.3: Non-context-free Languages, ss. 115–119..
Kategori:Formelle språk