Pompstelling

De pompstelling (ook gekend als pomplemma of pompend lemma) is een stelling 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: niet elke taal die voldoet aan de eigenschappen uit het pomplemma behoort noodzakelijk tot de klasse. Het lemma geeft dus een eigenschap die nodig, maar niet voldoende is om tot een klasse van talen te behoren.

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 sommige 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 pomplemma's zijn de volgende:

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

Pomplemma 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) een opdeling in drie delen kunnen vinden waarvoor we het middelste gedeelte (y) kunnen pompen, waarbij 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 het pomplemma 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.

Pomplemma 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 er voor elk woord in de taal dat lang genoeg is (|w| ≥ n) een opdeling in vijf delen bestaat waarvoor we het tweede en vierde gedeelte kunnen pompen, waarbij het te pompen gedeelte 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 = { dd | d ∈ {0, 1}^*}. We bewijzen uit het ongerijmde dat L niet contextvrij is.

We beginnen met te veronderstellen dat L wel contextvrij is en dat de pomplengte voor de taal n is. Vervolgens kiezen we z = 0ⁿ1ⁿ0ⁿ1ⁿ. Het is duidelijk dat z tot de taal L behoort en langer is dan de pomplengte. Nu moet er een opdeling van z bestaan in 5 deelwoorden uvwxy volgens de voorwaarden van het pomplemma. Volgens de tweede voorwaarde moet |vwx| kleiner of gelijk zijn aan n. Er zijn dan twee mogelijkheden voor de positie van het deelwoord vwx:

• vwx valt volledig in de eerste of volledig in de tweede helft van z

Stel dat vwx volledig in de eerste helft valt (het andere geval is analoog). Dan is uwy van de vorm 0ⁱ1^j0ⁿ1ⁿ met i<n en/of j<n aangezien |vx|>0. Het is duidelijk dat uwy niet kan behoren tot L.

• vwx bevat letters uit beide helften van z

In dit geval moet vwx van de vorm 1^k0^l zijn aangezien |vwx| ≤ n. Maar dan is uwy van de vorm 0ⁿ1ⁱ0^j1ⁿ met i<n en/of j<n aangezien |vx|>0. Ook hier is het duidelijk dat uwy niet kan behoren tot L.

In beide gevallen komen we tot een contradictie. Bijgevolg is L niet contextvrij.

Referenties

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