Pumpande lemma för kontextfria språk är ett kraftfullt verktyg för att bevisa att ett språk är * inte * kontextfritt. Det fungerar genom motsägelse:vi antar att språket * är * kontextfritt och visar sedan att detta antagande leder till en motsägelse. Så här tillämpas det, tillsammans med exempel:
Pumpande lemma (för CFL):
Om L är ett kontextfritt språk, finns det en konstant * p * (pumplängden) så att alla strängar * W * i L med | W | ≥ *p *kan skrivas som *w =uvxyz *, där:
1. | Vxy | ≤ *p *
2. | Vy | ≥ 1
3. För alla *i *≥ 0, *uv
i
xy
i
Z* är i L.
Bevisstrategin är att hitta en sträng *w *på språket så att oavsett hur vi sönderdelar det till *uvxyz *som uppfyller lemmas förhållanden, pumpar den (ökar *i *) kommer att producera en sträng som är *inte *på språket. Detta strider mot lemmaet och bevisar att språket inte är kontextfritt.
Exempel:
Låt oss illustrera med några exempel på språk och hur man kan bevisa att de inte är kontextfria med hjälp av pumpens lemma:
1. L₁ ={a
n
b
n
c
n
| n ≥ 0}
1. Antag att L₁ är kontextfri. Detta innebär att pumpens lemma gäller.
2. Välj en sträng W: Låt oss välja *w =a
p
B
p
c
p
*, där *p *är pumplängden. | W | ≥ *p *.
3. Pumpning: Eftersom | vxy | ≤ *p *, *vxy *kan sträcka sig över de flesta två av avsnitten (AAA ... BBB ... CCC ...). Det finns tre möjligheter:
* vxy innehåller endast A och B: Pumpning kommer att ändra antalet A och/eller B utan att ändra antalet C, vilket resulterar i en sträng som inte är i L₁.
* vxy innehåller endast B och C: I likhet med ovan kommer antalet B:er och/eller C kommer att förändras oproportionerligt.
* vxy innehåller endast A: Pumpning påverkar endast antalet A.
4. Motstånd: I alla fall producerar pumpning en sträng som inte är i L₁. Detta strider mot den pumpande Lemmas påstående att *uv
i
xy
i
z* är i l₁ för alla* i* ≥ 0.
5. Slutsats: Därför är L₁ inte kontextfri.
2. L₂ ={a
n
B
m
c
n+m
| n, m ≥ 0}
1. Antag att L₂ är kontextfri.
2. Välj en sträng W: Låt *w =a
p
B
p
C
2p
*.
3. Pumpning: Återigen, | vxy | ≤ *p *. Möjligheterna liknar l₁:om * vxy * bara innehåller A och B kommer pumpning att ändra antalet A och B utan att proportionellt ändra antalet C.
4. Motstånd: Pumpning kommer att leda till strängar inte i L₂.
5. Slutsats: L₂ är inte kontextfri.
3. L₃ ={ww | w ∈ {a, b}*} (Språket i strängar som är sammankoppling av en sträng med sig själv)
1. Antag att L₃ är kontextfri.
2. Välj en sträng W: Låt *w =a
p
B
p
a
p
B
p
*.
3. Pumpning: Eftersom | vxy | ≤ *p *, *vxy *kan inte korsa mitten av strängen (den kan inte sträcka sig över båda halvorna av `ww`). Om * vxy * är helt under första halvlek, kommer pumpen att obalansera de två halvorna.
4. Motstånd: Den pumpade strängen kommer inte att vara i L₃.
5. Slutsats: L₃ är inte kontextfri.
Viktiga överväganden:
* att välja rätt sträng *W *: Detta är avgörande. Strängen måste väljas noggrant för att utnyttja de begränsningar som ställs av | Vxy | ≤ *p *. Ofta är strängar med upprepade mönster användbara.
* Hantering av alla fall: Du måste överväga alla möjliga sätt att sönderdelas * w * till * uvxyz * som uppfyller lemmas förhållanden och visa att pumpning leder till en motsägelse i båda fallen.
* Pumplängden * P * är godtycklig: Du behöver inte veta värdet på *p *; Beviset fungerar för alla *p *.
Genom att noggrant använda dessa steg kan du använda pumpningslemma för att visa att många språk inte är kontextfria. Kom ihåg att det pumpande lemmaet endast tillhandahåller en metod för att bevisa språk är * inte * kontextfria; Det kan inte användas för att bevisa att ett språk * är * kontextfritt.
