Den pumpende egenskab, også kendt som pumpende lemma, er et grundlæggende begreb inden for beregningsmæssig kompleksitetsteori, specifikt i studiet af kontekstfølsomme sprog (CSL'er). Pumpeegenskaben giver en nødvendig betingelse for, at et sprog kan være kontekstfølsomt, og det hjælper med at bevise, at visse sprog ikke er kontekstfølsomme.
For at forstå de betingelser, der skal være opfyldt for at pumpeegenskaben kan holde, lad os først definere, hvad et kontekstfølsomt sprog er. Et kontekstfølsomt sprog er et formelt sprog, der kan genereres af en kontekstfølsom grammatik, som er en form for formel grammatik, hvor produktionsreglerne har lov til at ændre konteksten for en streng, der genereres. Med andre ord er grammatikken i stand til at genkende og generere sprog, der kræver en form for kontekst for deres genkendelse.
Pumpingsegenskaben for kontekstfølsomme sprog, også kendt som pumping-lemmaet for CSL'er, angiver, at hvis et sprog L er kontekstfølsomt, så eksisterer der en konstant p (pumpelængden), således at enhver tilstrækkelig lang streng w i L kan opdeles i fem dele: uvxyz, der opfylder følgende betingelser:
1. Længden af v og y kombineret er større end nul, dvs. |vxy| > 0.
2. Længden af uvxy er højst p, dvs. |uvxy| ≤ s.
3. For ethvert ikke-negativt heltal k er strengen uv^kxy^kz også i L.
For at præcisere disse betingelser, lad os overveje et eksempel. Antag, at vi har et sprog L = {a^nb^nc^n | n ≥ 0}, som repræsenterer sættet af strenge, der består af et lige antal 'a'er, 'b'er og 'c'er' i nævnte rækkefølge. Vi ønsker at afgøre, om dette sprog opfylder pumpeegenskaben.
I dette tilfælde vil pumpelængden p være antallet af 'a'er, 'b'er eller 'c'er', der kan pumpes. Lad os sige p = 2 for nemheds skyld. Overvej nu strengen w = a^2 b^2 c^2. Vi kan opdele denne streng i fem dele som følger: u = a^2, v = b^2, x = ε (tom streng), y = ε og z = c^2.
Betingelserne for pumpeejendommen er opfyldt i dette tilfælde:
1. Længden af v og y kombineret er større end nul, da |vxy| = |b^2| > 0.
2. Længden af uvxy er højst p, da |uvxy| = |a^2 b^2| ≤ 2.
3. For ethvert ikke-negativt heltal k er strengen uv^kxy^kz også i L. Hvis vi f.eks. vælger k = 0, så er uv^0xy^0z = a^2 c^2, som stadig er i L.
Derfor kan vi konkludere, at sproget L = {a^nb^nc^n | n ≥ 0} opfylder pumpeegenskaben og er kontekstafhængig.
Generelt er betingelserne for, at pumpeejendommen kan holde i forbindelse med CSL'er, som følger:
1. Længden af v og y kombineret skal være større end nul.
2. Længden af uvxy må højst være pumpelængden p.
3. For ethvert ikke-negativt heltal k skal strengen uv^kxy^kz også være på sproget L.
Disse forhold sikrer, at hvis et sprog er kontekstfølsomt, kan det "pumpes" ved at gentage en sektion af strengen, mens sprogets struktur bevares.
Andre seneste spørgsmål og svar vedr Kontekstfølsomme sprog:
- Hvad betyder det, at et sprog er stærkere end et andet?
- Kan Chomskys grammatik normalform altid bestemmes?
- Er der aktuelle metoder til at genkende Type-0? Forventer vi, at kvantecomputere gør det muligt?
- I eksemplet med sprog D, hvorfor holder pumpeegenskaben ikke for strengen S = 0^P 1^P 0^P 1^P?
- Hvilke to tilfælde skal man overveje, når man deler en streng for at anvende pumpelemmaet?
- I eksemplet med sprog B, hvorfor holder pumpeegenskaben ikke for strengen a^Pb^Pc^P?
- Hvordan kan Pumping Lemma for CFL'er bruges til at bevise, at et sprog ikke er kontekstfrit?
- Hvilke betingelser skal være opfyldt, for at et sprog kan anses for kontekstfrit ifølge det pumpende lemma for kontekstfri sprog?
- Forklar begrebet rekursion i sammenhæng med kontekstfri grammatik, og hvordan det giver mulighed for generering af lange strenge.
- Hvad er et parsetræ, og hvordan bruges det til at repræsentere strukturen af en streng genereret af en kontekstfri grammatik?
Se flere spørgsmål og svar i kontekstfølsomme sprog