1. Formuleer het pomplemma (voorzichtig!)

Voordat u begint, is het essentieel dat u de verklaring van het Pumping Lemma *exact* begrijpt. Hier is een veel voorkomende formulering:

Pomplemma voor CFL's:

Als L een contextvrije taal is, dan bestaat er een geheel getal *p* (de "pomplengte") zodat voor elke string *s* in L met een lengte groter dan of gelijk aan *p* (|s| ≥ *p*), *s* kan worden verdeeld in vijf substrings:*s =uvxyz*, wat aan de volgende voorwaarden voldoet:

* |vxy| ≤ *p* (Het middelste gedeelte dat wordt gepompt, is niet te lang)

* |vy| ≥ 1 (Het gepompte gedeelte is niet leeg)

* Voor alle *i* ≥ 0, *uv ⁱ xy ⁱ z* staat ook in L (door 'v' en 'y' een willekeurig aantal keren te pompen, blijft de string in de taal)

2. Stel dat de taal *contextvrij is

Begin met aan te nemen, ter wille van de tegenspraak, dat de taal *L* die je wilt bewijzen *niet* contextvrij is *is*, in feite contextvrij. Dit is de initiële veronderstelling die je uiteindelijk zult weerleggen.

3. Laat *p* de pomplengte zijn

Omdat je hebt aangenomen dat *L* contextvrij is, *moet* het Pumping Lemma van toepassing zijn. Dit betekent dat er een pomplengte *p* bestaat (waarvan u de exacte waarde niet weet). Het is van cruciaal belang om te onthouden dat de tegenstander (die de taal kent, *niet* contextvrij is en je probeert te misleiden) *p* mag kiezen. Je doel is om een ​​string te vinden waarvan *ongeacht welke waarde van p* wordt gekozen, de voorwaarden van het pomplemma tot een tegenspraak leiden.

4. Kies een tekenreeks *s* ∈ *L* zodat |*s*| ≥ *p *

Dit is een cruciale stap. U moet zorgvuldig een string *s* selecteren die tot de taal *L* behoort en een lengte groter dan of gelijk aan *p* heeft. De keuze voor *s* is van cruciaal belang om het bewijs te laten werken. Denk na over de structuur van de snaren in jouw taal en hoe pompen die structuur kan beïnvloeden. Het doel is om een ​​string te kiezen waarvan de eigenschappen worden geschonden wanneer 'v' en 'y' worden gepompt op een manier die wordt voorgeschreven door het Pumping Lemma. Deze keuze houdt *vaak* in dat sommige delen van de string worden ingesteld op basis van de waarde *p*.

*Denk na over de eigenschappen die ervoor zorgen dat strings in de taal erbij horen. Kies vervolgens een string op zo'n manier dat wanneer een substring wordt gepompt, ten minste één van de beperkingen voor het taallidmaatschap wordt geschonden.*

5. Overweeg alle mogelijke ontledingen *s =uvxyz* Voldoet aan |vxy| ≤ *p* en |vy| ≥ 1

Het Pumping Lemma stelt dat *elke* string *s* met |*s*| ≥ *p* kan op deze manier worden verdeeld. *uw tegenstander* mag dus kiezen hoe *s* wordt verdeeld in *uvxyz* (onder voorbehoud van de beperkingen |vxy| ≤ *p* en |vy| ≥ 1). U kunt echter alle mogelijke dergelijke verdelingen overwegen. Je moet laten zien dat *ongeacht hoe* de tegenstander *u*, *v*, *x*, *y* en *z* kiest, je de string kunt gebruiken om een ​​tegenspraak te krijgen.

Vaak houdt dit in dat er verschillende *cases* in overweging worden genomen op basis van waar *v* en *y* mogelijk binnen de string *s* zouden kunnen vallen. Voor elk geval analyseer je wat er gebeurt als je *v* en *y* pompt.

6. Laat zien dat voor Sommige *i* ≥ 0 de String *uv ⁱ is xy ⁱ z* is *niet* in *L *

Dit is de kern van de tegenstelling. Voor elk geval dat in stap 5 wordt bekeken, moet u aantonen dat er een aantal *i* bestaat (meestal *i* =0 of *i* =2, maar soms zijn andere waarden nodig), zodat de resulterende tekenreeks *uv ⁱ xy ⁱ z* is *niet* in de taal *L*. Dit betekent dat het de regels schendt die tekenreeksen definiëren die bij de taal horen.

* Hoe *uv ⁱ wordt weergegeven xy ⁱ z* staat niet in *L *:Dit is afhankelijk van de specifieke taal. U moet aantonen dat de gepompte string de definiërende eigenschappen van *L* schendt. Gemeenschappelijke strategieën zijn onder meer:

* Laat zien dat de string nu ongelijke aantallen symbolen bevat die voorheen gelijk waren. Als *L* bijvoorbeeld hetzelfde aantal 'a's en 'b's vereist, laat je zien dat pompen ervoor zorgt dat de telling ongelijk is.

* Laat zien dat de volgorde van de symbolen nu onjuist is. Als *L* bijvoorbeeld vereist dat alle 'a's vóór alle 'b's komen, laat je zien dat pompen een 'b' vóór een 'a' kan plaatsen.

* Aantonen dat een wiskundige relatie tussen tellingen niet langer geldt. Als *L* bijvoorbeeld vereist dat het aantal 'a's tweemaal het aantal 'b's is, laat u zien dat pompen deze relatie schendt.

7. Concludeer dat *L* *niet* contextvrij is

Omdat je hebt aangetoond dat de aanname dat *L* contextvrij is, tot een tegenstrijdigheid leidt (het Pumping Lemma moet gelden, maar je hebt een geval laten zien waarin dit niet het geval is), kun je concluderen dat je aanvankelijke aanname onjuist was. Daarom is *L* geen contextvrije taal.

Voorbeeld:de taal L ={ a ⁿ b ⁿ c ⁿ | n ≥ 0 }

Laten we bewijzen dat *L* ={a ⁿ b ⁿ c ⁿ | n ≥ 0} is niet contextvrij met behulp van het Pumping Lemma.

1. Stel dat *L* contextvrij is.

2. Laat *p* de pomplengte zijn gegarandeerd door het Pomplemma.

3. Kies een tekenreeks *s*: Stel *s* =a ^*p* b ^*p* c ^*p* . Het is duidelijk dat *s* ∈ *L* en |*s*| =3*p* ≥ *p*.

4. Overweeg alle mogelijke delingen *s =uvxyz* zodat |vxy| ≤ *p* en |vy| ≥ 1: We moeten overwegen waar de subtekenreeksen *v* en *y* zich binnen *s* kunnen bevinden. De cruciale beperking is dat |vxy| ≤ *p*. Dit beperkt de mogelijkheden aanzienlijk:

* Geval 1:*vxy* bestaat alleen uit 'a's. Dan *v* =a ^j en *y* =a ^k voor sommige *j*, *k* ≥ 0 en *j + k* ≥ 1. Als we naar beneden pompen (*i* =0), krijgen we de string a ^*p-j-k* b ^*p* c ^*p* . Omdat *j + k* ≥ 1 heeft deze string minder dan *p* 'a's, maar nog steeds *p* 'b's en *p* 'c's. Daarom staat het niet in *L*.

* Geval 2:*vxy* bestaat alleen uit 'b's. Dan *v* =b ^j en *y* =b ^k voor sommige *j*, *k* ≥ 0 en *j + k* ≥ 1. Als we leegpompen (*i* =0), krijgen we a ^*p* b ^*p-j-k* c ^*p* . Nogmaals, het aantal 'b's is kleiner dan *p*, terwijl het aantal 'a's en 'c's *p* blijft, dus het staat niet in *L*.

* Geval 3:*vxy* bestaat alleen uit 'c's. Dan *v* =c ^j en *y* =c ^k voor sommige *j*, *k* ≥ 0 en *j + k* ≥ 1. Als we leegpompen (*i* =0), krijgen we a ^*p* b ^*p* c ^*p-j-k* . Het aantal 'c's is kleiner dan *p*, terwijl de aantallen 'a's en 'b's *p* blijven, dus het staat niet in *L*.

* Geval 4:*vxy* bestaat uit 'a's en 'b's. Sinds |vxy| ≤ *p*, het mag geen 'c's bevatten omdat alle *p* 'a's en *p* 'b's aan alle 'c's moeten voorafgaan. Sinds |vy| ≥ 1, minstens één van *v* of *y* moet een teken bevatten. Daarom *v* =a ^j b ^k en *y* =a ^l b ^m voor sommige *j*, *k*, *l*, *m* ≥ 0 en *j + k + l + m* ≥ 1, met ten minste één van 'a' of 'b' in *v* of *y*.

Als we oppompen (*i* =2), krijgen we de string a ^*p+j+l* b ^*p+k+m* c ^*p* . Als *k + m* nul is (dus *v* en *y* bevatten alleen 'a's) neemt het aantal 'a's toe, maar blijft het aantal 'b's hetzelfde. Het resultaat is a ^*p+j+l* b ^*p* c ^*p* dat is niet meer in de taal. Als *j + l* nul is (dus *v* en *y* bevatten alleen 'b's), neemt het aantal 'b's toe, maar blijft het aantal 'a's hetzelfde. Het resultaat is een ^*p* b ^*p+k+m* c ^*p* dat is niet meer in de taal. Als zowel *k+m* als *j+l* groter zijn dan nul, dan is *uv ² xy ² z* heeft meer 'a's en 'b's dan 'c's, wat betekent dat het niet de vorm a ⁿ kan hebben b ⁿ c ⁿ .

* Geval 5:*vxy* bestaat uit 'b's en 'c's. Dit is symmetrisch met geval 4. Opnieuw zal het oppompen resulteren in een string die niet in de taal voorkomt.

5. Tegenstrijdigheid: In elk mogelijk geval hebben we aangetoond dat er een *i* bestaat zodat *uv ⁱ xy ⁱ z* staat niet in *L*. Dit is in tegenspraak met het Pumping Lemma.

6. Conclusie: Daarom moet onze aanvankelijke veronderstelling dat *L* contextvrij is, onjuist zijn. Dus *L* ={a ⁿ b ⁿ c ⁿ | n ≥ 0} is niet contextvrij.

Belangrijke tips voor het gebruik van het pomplemma:

* Begrijp het lemma precies: Ken de exacte verklaring en voorwaarden.

* Strategische stringkeuze: De keuze voor *s* is cruciaal. Kies een string die de eigenschap benadrukt die u door middel van pompen wilt doorbreken. Vaak is het handig om delen van de string in te stellen op basis van *p*.

* Zorgvuldige casusanalyse: Beschouw alle mogelijke locaties voor *v* en *y* binnen *s*, gegeven de beperkingen |vxy| ≤ *p* en |vy| ≥ 1.

* Kies het goede *i *:Experimenteer met *i* =0, *i* =2 of andere waarden om de waarde te vinden die het duidelijkst de schending van *L* aantoont. Soms zorgt *i* =0 ervoor dat iets verdwijnt, en *i* =2 zorgt ervoor dat iets wordt gedupliceerd.

* Wees duidelijk en strikt: Leg precies uit waarom de opgepompte string niet langer in *L* staat. Raadpleeg de bepalende eigenschappen van de taal.

Het Pomplemma kan lastig zijn om onder de knie te krijgen. Oefen met verschillende talen om ervaring op te doen met het kiezen van de juiste tekenreeksen en het omgaan met de casusanalyse. Onthoud dat het doel is om een ​​string te vinden waar *elke* mogelijke toepassing van het Pumping Lemma tot een tegenstrijdigheid leidt. Succes!