Pompstelling

De pompstelling is een begrip uit de studie der formele talen, een onderdeel van de theoretische informatica. Aan de hand van het lemma kan bewezen worden dat een taal niet tot een bepaalde klasse van talen behoort. Het omgekeerde is echter niet waar, als het bewijs faalt betekent dit niet noodzakelijk dat de taal tot de klasse behoort. Het lemma is dus een eigenschap die nodig is om tot een klasse van talen te behoren, maar er niet voldoende uitsluitsel over geeft.

De werking van het lemma is er op gebaseerd dat alle woorden in de taal die lang genoeg zijn opgebroken kunnen worden in deelwoorden, waarvan er bepaalde gepompt kunnen worden zodat alle resulterende woorden ook tot de taal behoren. Dit betekent dat die bepaalde deelwoorden weggelaten of een onbepaald aantal keren herhaald kunnen worden, wat men pompen noemt.

De belangrijkste voorbeelden van de pompstelling zijn de volgende:

• Pompstelling voor reguliere talen
• Pompstelling voor contextvrije talen
• Ogden's lemma

Pompstelling voor reguliere talen

Stel dat L een reguliere taal is. Dan bestaat er een constante n, die afhankelijk is van L, waarvoor geldt dat elk woord w ∈ L zodat |w| ≥ n, opgebroken kan worden in 3 deelwoorden, w = xyz zodat:

1. |y| > 0
2. |xy| ≤ n
3. Voor alle k ≥ 0, xy^kz behoort tot L

Informeel betekent dit dat we voor elk woord in de taal dat lang genoeg is (|w| ≥ n) het middelste gedeelte kunnen pompen als y niet leeg is (|y| > 0) en het te pompen gedeelte niet te ver van het begin van het woord verwijderd is (|xy| ≤ n).

Bewijs

Het bewijs voor de pompstelling voor reguliere talen steunt op het feit dat er voor elke reguliere taal een eindige toestandsautomaat bestaat die de taal accepteert. Aan de hand van het aantal woorden in de taal onderscheiden we 2 verschillende mogelijkheden.

Eindige taal

Als de reguliere taal een eindig aantal woorden heeft, betekent dit dat we een automaat kunnen maken die voor elk woord in de taal een apart pad heeft. In dit geval valt er niets te pompen en is de pomplengte n groter dan de lengte van elk woord in de taal. Dit impliceert meteen dat het lemma bewezen is voor de eindige talen, want we kunnen de vereiste regels niet overschrijden.

Oneindige taal

Stel dat het aantal toestanden van de automaat die de taal accepteert gelijk is aan n, welke we meteen als pomplengte aannemen. Dit kunnen we doen omdat volgens het duiventilprincipe elk woord w met lengte groter of gelijk aan n de automaat minstens 2 keer in eenzelfde toestand p plaatst.

Nu we dit weten kunnen we het woord w opdelen in 3 deelwoorden zodat w = xyz. We kiezen deze zo dat de automaat na verwerking van het eerste deelwoord x in toestand p is. Na verwerking van y moet de automaat opnieuw in toestand p zijn, en vervolgens na het verwerken van z moet de automaat in een eindtoestand zijn.

Als k in dit geval 0 is gaat de automaat van de begintoestand naar toestand p wanneer x verwerkt wordt, en vervolgens van toestand p naar een eindtoestand als z verwerkt wordt. De automaat accepteert het woord xz en dus behoort het woord tot de taal.

Als k groter is dan 0 zal de automaat van de begintoestand naar toestand p gaan als x verwerkt wordt, vervolgens zal voor elke verwerking van y er van toestand p naar toestand p gegaan worden. Dit betekent dus dat er k keer van toestand p naar toestand p gegaan wordt. Uiteindelijk zal de automaat na verwerking van z dan van de toestand p naar een eindtoestand gaan. De automaat accepteert xy^kz met k > 0 en dus behoren deze woorden tot de taal.

Voorbeeld

Laat L de taal zijn die bestaat uit alle woorden met een gelijk aantal 1en en 0en. Bijvoorbeeld de woorden 1001 en 101010 behoren tot deze taal. We beginnen met te veronderstellen dat deze taal regulier is en dat de pomplengte voor de taal n is. Vervolgens kiezen we w zodat w = 1ⁿ0ⁿ en dus per definitie tot de taal behoort. Nu moeten we w opbreken in 3 deelwoorden, en volgens de tweede vereiste moet |xy| in dit geval kleiner of gelijk zijn aan n, dit betekent dat xy enkel uit 1en bestaat. De eerste vereiste zegt dat het y gedeelte dan uit minstens één 1 moet bestaan. Als we y nu gaan proberen pompen, merken we dat elk woord dat dit oplevert een ongelijk aantal 1en en 0en heeft. We hebben dus een contradictie aangezien al deze woorden tot de taal zouden moeten behoren als die regulier is. Bijgevolg is L niet regulier.

Pompstelling voor contextvrije talen

Stel dat L een contextvrije taal is. Dan bestaat er een constante n, die afhankelijk is van L, waarvoor geldt dat elk woord z ∈ L zodat |z| ≥ n, opgebroken kan worden in 5 deelwoorden, z = uvwxy zodat:

1. |v| + |x| > 0
2. |vwx| ≤ n
3. Voor alle k ≥ 0, uv^kwx^ky behoort tot L

Informeel betekent dit dat we voor elk woord in de taal dat lang genoeg is (|w| ≥ n) het tweede en vierde gedeelte kunnen pompen als v of x niet leeg is (|v| + |x| > 0) en het middelste deel van het woord niet te lang is (|vwx| ≤ n).

Voorbeeld

Laat L de taal zijn over alfabet {0, 1} die bestaat uit alle woorden die bestaan uit een deelwoord dat zich 1 keer herhaalt, dus L = { ww | w ∈ {0, 1}^*}. We beginnen met te veronderstellen dat deze taal contextvrij is en dat de pomplengte voor de taal n is. Vervolgens kiezen we z zodat z = 0ⁿ1ⁿ0ⁿ1ⁿ en dus per definitie tot de taal behoort, want het is de herhaling van 0ⁿ1ⁿ. Nu moeten we w opbreken in 5 deelwoorden, en volgens de tweede vereiste moet |vwx| in dit geval kleiner of gelijk zijn aan n. Dit geeft ons de mogelijkheid om vwx te laten bestaan uit:

• een deel van de eerste groep 0en
• een deel van de eerste groep 1en
• een deel van de tweede groep 0en
• een deel van de tweede groep 1en
• een deel van de eerste groep 0en en een deel van de eerste groep 1en
• een deel van de eerste groep 1en en een deel van de tweede groep 0en
• een deel van de tweede groep 0en en een deel van de tweede groep 1en

In de eerste 4 gevallen moet ofwel v ofwel x bestaan uit ten minste één 0 of 1, afhankelijk van het geval we beschouwen. Als we v en x dan gaan pompen zal de groep waarin deze zich bevinden meer of minder symbolen bevatten dan de 3 andere groepen. Geen enkele van de nieuwe woorden behoort tot de taal L.

In de 3 laatste gevallen onderscheiden we nog eens 3 mogelijkheden.

• v bestaat uit ten minste één 0 of 1 en x is leeg, of omgekeerd. In dit geval is de redenering hetzelfde als bij de eerste 4 gevallen, en zal een van de groepen meer of minder symbolen bevatten.
• v bestaat uit een opeenvolging 0en en 1en of omgekeerd, en x is leeg, of omgekeerd. In dit geval zullen de groepen waarin v (of x) zich bevindt ofwel te weinig symbolen bevatten ofwel zal er tussen deze groepen een aantal extra deelwoorden van de vorm v (of x) te vinden zijn. Geen enkele van de nieuwe woorden behoort tot de taal L.
• een combinatie van de 2 bovenstaande gevallen die weer geen nieuwe woorden genereert die tot L behoren.

In alle mogelijke gevallen is dus gebleken dat de nieuwe woorden niet tot de taal L behoren, wat een contradictie oplevert aangezien ze wel tot de taal zouden moeten behoren als deze contextvrij is. Bijgevolg is L niet contextvrij.

Referenties

• (en) John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman Introduction to Automata Theory, Languages, and Computation, Pearson, Addison Wesley. ISBN 0-321-21029-8, 2001 pagina 126-129, 275-280