Pumping Lemma

Endliche Automaten können benutzt werden um Sprachen zu erkennen. Ein Wort einer Sprache kann aber beliebig lang sein, weshalb die Zustände des endlichen Automaten so angepasst werden müssen, dass sie eine beliebig lange Eingabe akzeptieren können. Da ein endlicher Automat nur endlich viele Zustände haben kann, muss man dieses Problem dadurch lösen, dass man eine Schleife einführt. Es folgt daraus, dass es in dem Wort mindestens eine Stelle gibt, die man beliebig oft pumpen kann. Dieser Worteil kann also beliebig lang sein, der endliche Automat verwendet jedoch einfach immer wieder die selben Zustände in Form einer Schleife.

Wird das Pumping Lemma für eine Sprache nicht erfüllt, kann man sofort sagen, dass es keinen endlichen Automaten gibt, der die betrachtete Sprache akzeptieren kann. Das Pumping Lemma wird also in einen Widerspruchsbeweis eingebaut.