Sprachen, die nicht regulär sind

Nicht jede Sprache lässt sich durch einen regulären Ausdruck beschreiben. Auch wenn eine Sprache sehr regelmäßig aufgebaut ist, heißt das nicht unbedingt, dass sie eine reguläre Sprache ist. Regulär ist ein Fachbegriff, der besagt, dass die Sprache durch endlich viele Anwendungen der Operationen Vereinigung, Verkettung und Abschluss auf Elementarsprachen zustande kommt.

Ein Beispiel für eine nicht reguläre Sprache ist die Sprache

$L$ = {a${}^n$b${}^n$ | $n\in \mathbb{N}$ } = {ab, aabb, aaabbb, aaaabbbb, …}

Regelmäßiger kann eine Sprache kaum aufgebaut sein, aber es gibt keinen regulären Ausdruck, der die Sprache $L$ beschreibt. Jedes Wort der Sprache enthält genauso viele a's wie b's, und dies lässt sich mit einem regulären Ausdruck nicht ausdrücken. Der reguläre Ausdruck a${}^{\ast }$b${}^{\ast }$ beschreibt zwar die Wörter von $L$, aber auch noch andere Wörter wie aabbbb, die unterschiedlich viele a's und b's enthalten.

Dass es keinen regulären Ausdruck gibt, der die Sprache $L$ beschreibt, ist schwer zu beweisen. Einfacher zu beweisen ist die Aussage:

Deterministische endliche Automaten können nicht zählen

Deterministische endliche Automaten "können nicht zählen", jedenfalls nicht beliebig weit. Dies liegt daran, dass ein deterministischer endlicher Automat nur endlich viele Zustände hat. Hat er zum Beispiel $p$ Zustände und liest er das Wort a${}^p$b${}^p$ ein, so gerät er spätestens beim letzten eingelesenen a in einen Zustand, in dem er schon einmal gewesen ist. Er ist also sozusagen im Kreis gelaufen. Wenn der Automat a${}^p$b${}^p$ erkennt, dann erkennt er auch a${}^{p+r}$b${}^p$ (wobei $r$ die Länge des Kreises ist), indem er den Kreis zweimal durchläuft. Dieses Wort ist aber kein Wort der Sprache $L$, weil es mehr a's als b's enthält. Es gibt also keinen deterministischen endlichen Automaten, der genau die Sprache a${}^n$b${}^n$ erkennt.

Auf dieser Idee beruht das sogenannte Pumping-Lemma für reguläre Sprachen. Pumping deutet darauf hin, dass genügend lange Wörter einer regulären Sprache sich an einer Stelle "aufpumpen" lassen – so wie a${}^p$b${}^p$ sich zu a${}^{p+r}$b${}^p$ aufpumpen lässt.

Das Pumping-Lemma ist ein wichtiges Hilfsmittel, wenn du beweisen möchtest, dass eine bestimmte Sprache nicht regulär ist.