Pompstelling
Uit Wikipedia, de vrije encyclopedia
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