Springe zum Inhalt oder Footer
SerloDie freie Lernplattform

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

LL = {an^nbn^n | nNn \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 LL 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^*b^* beschreibt zwar die Wörter von LL, 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 LL beschreibt, ist schwer zu beweisen. Einfacher zu beweisen ist die Aussage:

Es gibt keinen deterministischen, endlichen Automaten, der die Sprache LL erkennt.

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 pp Zustände und liest er das Wort ap^pbp^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 ap^pbp^p erkennt, dann erkennt er auch ap+r^{p+r}bp^p (wobei rr die Länge des Kreises ist), indem er den Kreis zweimal durchläuft. Dieses Wort ist aber kein Wort der Sprache LL, weil es mehr a's als b's enthält. Es gibt also keinen deterministischen endlichen Automaten, der genau die Sprache an^nbn^ 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 ap^pbp^p sich zu ap+r^{p+r}bp^p aufpumpen lässt.

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

Du hast noch nicht genug vom Thema?

Hier findest du noch weitere passende Inhalte zum Thema:

Artikel


Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0Was bedeutet das?