Pumpelemmaet for kontekstfrie språk

I teorien om formelle språk er pumpelemmaet for kontekstfrie språk eit lemma som skildrar ein fundamental eigenskap for kontekstfrie språk. Lemmaet er ei generalisering av pumpelemmaet for regulære språk.

Lemmaet vert ofte nytta for å føra eit motseiingsbevis for at eit formelt språk ikkje er kontekstfritt. Det kan ikkje nyttast til å bevisa at eit formelt språk faktisk er kontekstfritt.

Formell definisjon

Viss eit språk L er kontekstfritt eksisterer det ei pumpelengde som er større enn éin sånn at kvar og ein streng s i språket som er lengre enn pumpelengda kan delast inn i følgjande streng $s=uvwxy$ der u, v, w, x og y er substrengar. Vidare må dei følgjande krava vera oppfylte for at det skal vera eit kontekstfritt språk

1. |vwx| ≤ p,

2. |vx| ≥ 1, og

3. uvⁿwxny er i L for kvar og ein n ≥ 0.

Uformell forklaring av definisjonen

Om ein følgjer den formelle definisjonen vert det sagt at v og x vert gjentekne eit vilkårlig tal gongar i strengen og utgjer pumpinga av strengen. Alle kontekstfrie språk har denne eigenskapen, viss ikkje er ikkje det formelle språket eit kontekstfritt språk. Endelege språk oppfyller pumpelemmaet ved å la pumpelengda vera den maksimale strenglengda i språket pluss éin. Pluss éin følgjer frå prinsippet om at det skal kunne pumpast, altså at det er ein substreng som skal kunne repeterast eit vilkårlig tal gongar.

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..