| Het pompende lemma voor contextvrije talen is een krachtig hulpmiddel om te bewijzen dat een taal *niet* contextvrij is. Het werkt door tegenspraak:we nemen aan dat de taal contextvrij is, en laten vervolgens zien dat deze aanname tot een tegenspraak leidt. Hier ziet u hoe het wordt toegepast, samen met voorbeelden:
Het pomplemma (voor CFL's):
Als L een contextvrije taal is, dan bestaat er een constante *p* (de pomplengte) zodat elke string *w* in L met |w| ≥ *p* kan geschreven worden als *w =uvxyz*, waarbij:
1. |vxy| ≤ *p*
2. |vy| ≥ 1
3. Voor alle *i* ≥ 0, *uv
i
xy
i
z* staat in L.
De bewijsstrategie is om een string *w* in de taal te vinden, zodat, ongeacht hoe we deze ontbinden in *uvxyz* en aan de voorwaarden van het lemma voldoet, het pompen ervan (verhogen van *i*) een string zal opleveren die *niet* in de taal is. Dit is in tegenspraak met het lemma, wat bewijst dat de taal niet contextvrij is.
Voorbeelden:
Laten we dit illustreren met enkele voorbeelden van talen en hoe we kunnen bewijzen dat ze niet contextvrij zijn met behulp van het pomplemma:
1. L₁ ={a
n
b
n
c
n
| n ≥ 0}
1. Stel dat L₁ contextvrij is. Dit betekent dat het pomplemma van toepassing is.
2. Kies een tekenreeks w: Laten we *w =a
p
kiezen b
p
c
p
*, waarbij *p* de pomplengte is. |w| ≥ *p*.
3. Pompen: Omdat |vxy| ≤ *p*, *vxy* kan maximaal twee secties omvatten (aaa...bbb...ccc...). Er zijn drie mogelijkheden:
* vxy bevat alleen a's en b's: Door te pompen verandert het aantal a's en/of b's zonder het aantal c's te veranderen, wat resulteert in een string die niet in L₁ staat.
* vxy bevat alleen b's en c's: Net als hierboven zal het aantal b's en/of c's onevenredig veranderen.
* vxy bevat alleen a's: Pompen heeft alleen invloed op het aantal a's.
4. Tegenstrijdigheid: In alle gevallen produceert het pompen een snaar die niet in L₁ staat. Dit is in tegenspraak met de bewering van het pompende lemma dat *uv
i
xy
i
z* zit in L₁ voor alle *i* ≥ 0.
5. Conclusie: Daarom is L₁ niet contextvrij.
2. L₂ ={a
n
b
m
c
n+m
| n, m ≥ 0}
1. Stel dat L₂ contextvrij is.
2. Kies een tekenreeks w: Stel dat *w =a
p
b
p
c
2p
*.
3. Pompen: Nogmaals, |vxy| ≤ *p*. De mogelijkheden zijn vergelijkbaar met L₁:als *vxy* alleen a's en b's bevat, zal het pompen het aantal a's en b's veranderen zonder het aantal c's proportioneel te veranderen.
4. Tegenstrijdigheid: Pompen leidt tot snaren die niet in L₂ staan.
5. Conclusie: L₂ is niet contextvrij.
3. L₃ ={ww | w ∈ {a, b}*} (De taal van tekenreeksen die de aaneenschakeling van een tekenreeks met zichzelf zijn)
1. Stel dat L₃ contextvrij is.
2. Kies een tekenreeks w: Stel dat *w =a
p
b
p
a
p
b
p
*.
3. Pompen: Omdat |vxy| ≤ *p*, *vxy* kan niet door het midden van de string gaan (het kan niet beide helften van `ww` overspannen). Als *vxy* zich geheel in de eerste helft bevindt, zal het pompen de twee helften uit balans brengen.
4. Tegenstrijdigheid: De opgepompte string zal niet in L₃ zijn.
5. Conclusie: L₃ is niet contextvrij.
Belangrijke overwegingen:
* De juiste tekenreeks kiezen *w*: Dit is cruciaal. De string moet zorgvuldig worden gekozen om gebruik te maken van de beperkingen opgelegd door |vxy| ≤ *p*. Vaak zijn snaren met herhaalde patronen nuttig.
* Alle zaken afhandelen: Je moet alle mogelijke manieren overwegen om *w* te ontbinden in *uvxyz*, waarbij je voldoet aan de voorwaarden van het lemma, en je moet aantonen dat pompen in elk geval tot een tegenstrijdigheid leidt.
* De pomplengte *p* is willekeurig: U hoeft de waarde van *p* niet te weten; het bewijs werkt voor elke *p*.
Door deze stappen zorgvuldig toe te passen, kun je het pomplemma gebruiken om aan te tonen dat veel talen niet contextvrij zijn. Houd er rekening mee dat het pomplemma alleen een methode biedt om te bewijzen dat talen *niet* contextvrij zijn; het kan niet worden gebruikt om te bewijzen dat een taal contextvrij is. |
