| Het pompende lemma voor reguliere talen is een krachtig hulpmiddel om te bewijzen dat een taal *niet* regulier is. Het werkt in tegenspraak:je neemt aan dat de taal *regulier* is, en laat vervolgens zien dat deze aanname leidt tot een tegenspraak van het lemma zelf. Hier is hoe het werkt:
1. De verklaring van het pomplemma:
Het pomplemma stelt dat er voor elke reguliere taal L een pomplengte p bestaat, zodat elke string w in L met lengte |w| ≥ p kan worden verdeeld in drie substrings, w =xyz, die aan de volgende voorwaarden voldoen:
* |xy| ≤p: De lengte van de aaneenschakeling van x en y is kleiner dan of gelijk aan p.
* |y|> 0: De subtekenreeks y is niet leeg.
* Voor alle i ≥ 0, xy
i
z ∈ L: Het nul of vaker pompen van y (inclusief het volledig verwijderen ervan als i=0) resulteert in een string die nog steeds in de taal L is.
2. Bewijsstrategie:
Om te bewijzen dat een taal L niet regulier is met behulp van het pomplemma, volgt u deze stappen:
* Neem aan dat L regulier is: Begin door, ter wille van de tegenspraak, aan te nemen dat L een reguliere taal is.
* Kies een pomplengte p: Het pomplemma garandeert het bestaan van een pomplengte p; je hoeft de werkelijke waarde ervan niet te vinden, maar noem het gewoon 'p'.
* Kies een string w ∈ L zodat |w| ≥p: Selecteer zorgvuldig een string w uit de taal L waarvan de lengte minstens p is. De keuze voor w is cruciaal; het moet je in staat stellen om in de volgende stap een tegenstrijdigheid te creëren. Vaak gaat het hierbij om tekenreeksen met een specifieke structuur die verband houdt met de definitie van de taal.
* Laat zien dat geen enkele ontleding w =xyz voldoet aan de voorwaarden van het pomplemma: Dit is de kern van het bewijs. Voor *elke* mogelijke ontleding van w in xyz die voldoet aan |xy| ≤ p en |y|> 0, je moet aantonen dat er een i ≥ 0 bestaat zodat xy
i
z ∉ L. Dit betekent dat het pompen van y in strijd is met de definitie van de taal L. Vaak demonstreer je dit door aan te tonen dat het pompen van y:
* Introduceer een onbalans: Verander het aantal keren dat een symbool voorkomt, waardoor een telbeperking in L wordt overtreden.
* Maak een ongeldige structuur: Doorbreek het patroon of de structuur die vereist is door de definitie van L.
* Introduceer een ongeldige subtekenreeks: Maak een subtekenreeks die niet bij de taal hoort.
* Concludeer dat L niet regulier is: Omdat je hebt aangetoond dat een dergelijke ontbinding niet kan bestaan voor de gekozen string w, is dit in tegenspraak met het pomplemma. Daarom moet de initiële aanname dat L regulier is onwaar zijn, en L is niet regulier.
Voorbeeld:{a
n
bewijzen b
n
| n ≥ 0} is niet regulier:
Zij L ={a
n
b
n
| n ≥ 0}.
1. Stel dat L regulier is.
2. Kies p: Laat p de pomplengte zijn.
3. Kies w: Stel dat w =a
p
b
p
. Het is duidelijk dat w ∈ L en |w| ≥ blz.
4. Geen ontleding weergeven voldoet aan de voorwaarden: Laten we elke ontbinding w =xyz bekijken zodat |xy| ≤ p en |y|> 0. Sinds |xy| ≤ p, y moet *alleen* uit a's bestaan (omdat y een subtekenreeks is van de eerste p-tekens). Dus y =a
k
voor een k> 0. Pomp y nu nul keer:xy
0
z =a
p-k
b
p
. Deze string staat niet in L omdat het aantal a's en b's verschillend is. Dit is in tegenspraak met het pomplemma.
5. Conclusie: Omdat we een tegenstrijdigheid hebben bereikt, moet onze aanname dat L regulier is, onjuist zijn. Daarom is L ={a
n
b
n
| n ≥ 0} is geen reguliere taal.
De sleutel is om zorgvuldig de string `w` te kiezen en alle mogelijke decomposities `xyz` slim te analyseren om aan te tonen dat het pompen van `y` altijd leidt tot een string buiten de taal. Hoe complexer de taal, hoe ingewikkelder de keuze van ‘w’ en de analyse worden. |
