1. Pomplemma voor contextvrije talen: Dit is de meest gebruikte techniek. Het pomplemma stelt dat er voor elke CFL L een constante *p* (de pomplengte) bestaat, zodat elke string *w* in L met lengte |w| ≥ *p* kan geschreven worden als *uvxyz*, waarbij:

* |vxy| ≤ *p*

* |vy| ≥ 1

* *uv ⁱ xy ⁱ z* ∈ L voor alle *i* ≥ 0

Om te bewijzen dat een taal *niet* contextvrij is, gebruik je het pomplemma:

1. Stel: Neem ter wille van de tegenspraak aan dat de taal *L* contextvrij is.

2. Kies een tekenreeks: Selecteer een string *w* in *L* met een lengte die minstens gelijk is aan de pomplengte *p* (je zult vaak strategisch *w* moeten kiezen).

3. Pomp de string: Probeer *w* te ontbinden in *uvxyz*, dat voldoet aan de voorwaarden van het lemma.

4. Zoek een tegenstrijdigheid: Laat dat zien voor sommige *i*, *uv ⁱ xy ⁱ z* is *niet* in *L*. Dit is in tegenspraak met het pompende lemma, wat bewijst dat de oorspronkelijke aanname (dat *L* contextvrij is) onjuist moet zijn.

Voorbeeld: Laten we eens kijken naar de taal L ={a ⁿ b ⁿ c ⁿ | n ≥ 0}. Met behulp van het pomplemma:

1. Stel: L is contextvrij.

2. Kies een tekenreeks: Stel *w* =a ^p b ^p c ^p (waarbij *p* de pomplengte is).

3. Pomp de string: Hoe je *w* ook ontbindt in *uvxyz*, pompen zal onvermijdelijk de a ⁿ schenden b ⁿ c ⁿ structuur. Als *vxy* bijvoorbeeld alleen 'a's bevat, zal het pompen het aantal 'a's verhogen zonder het aantal 'b's en 'c's te vergroten. Soortgelijke problemen doen zich voor als *vxy* alleen 'b's of 'c's bevat, of een mengsel dat niet de gelijke verhouding handhaaft.

4. Tegenstrijdigheid: Daarom bestaat er een *i* zodat *uv ⁱ xy ⁱ z* ∉ L, wat in tegenspraak is met het pomplemma. L is dus niet contextvrij.

2. Sluitingseigenschappen: Contextvrije talen worden onder bepaalde bewerkingen gesloten (vereniging, aaneenschakeling, Kleene-ster, kruising met een reguliere taal). Als je kunt aantonen dat een taal *niet* gesloten is onder een van deze bewerkingen, kan deze niet contextvrij zijn. Deze methode wordt minder vaak gebruikt voor direct bewijs dan het pomplemma, maar kan nuttig zijn in combinatie met andere technieken.

3. Ogdens lemma: Dit is een krachtigere versie van het pomplemma, waarmee u gemarkeerde posities binnen de string *w* kunt kiezen. Het is nuttig voor talen waarin het eenvoudige pomplemma moeilijk toe te passen is.

4. Stelling van Parikh: Deze stelling heeft betrekking op het aantal keren dat elk symbool voorkomt in strings van een taal. Hoewel het niet direct wordt gebruikt om te bewijzen dat een taal *niet* contextvrij is, kan het soms helpen aantonen dat de structuur van een taal onverenigbaar is met de beperkingen die door CFL's worden opgelegd. Het wordt vaak gebruikt in combinatie met andere technieken.

Samenvattend is het pomplemma de meest gebruikelijke en over het algemeen effectieve methode om te bewijzen dat een taal niet contextvrij is. De keuze van de methode hangt echter af van de structuur van de specifieke taal en het gemak waarmee elke techniek kan worden toegepast. Ogden's Lemma biedt meer kracht wanneer dat nodig is, en sluitingseigenschappen kunnen aanvullend bewijs leveren.