Reguläre Ausdrücke

Angenommen du hast eine Webseite erstellt, auf der man seine E-Mail-Adresse eingeben kann, um den Newsletter zu abonnieren. Dann überprüfst du mithilfe eines regulären Ausdrucks, ob die eingegebene E-Mail-Adresse formal richtig ist. Der reguläre Ausdruck bestimmt, dass als Eingabe nur Wörter zulässig sind, die mit Buchstaben, Ziffern und den Zeichen -, _ und . beginnen, dann ein @-Zeichen enthalten und dann mit Buchstaben, Ziffern und den Zeichen - , _ und . weitergehen und zum Schluss einen Punkt gefolgt von Buchstaben enthalten (für .de oder .com usw.).

In diesem Artikel lernst du, welche Bedeutung reguläre Ausdrücke in der Informatik haben, wie reguläre Ausdrücke gebildet werden und welche Sprachen von ihnen erzeugt werden.

Idee

Du kennst arithmetische Ausdrücke. Zum Beispiel ist

$2 + 3 \cdot 4$

ein arithmetischer Ausdruck. Er beschreibt, welche Operationen in welcher Reihenfolge auf welche Operanden angewendet werden. Die Operanden sind Zahlen, und die Operationen sind die Grundrechenarten Plus, Minus, Mal und Geteilt-durch. Heraus kommt als Ergebnis ebenfalls eine Zahl.

Ganz entsprechend werden reguläre Ausdrücke gebildet. Die Operanden sind Sprachen, und die Operationen sind Vereinigung, Verkettung und Abschluss. Heraus kommt als Ergebnis wieder eine Sprache.

Wenn du nicht weißt, was es mit den erwähnten Operationen Vereinigung, Verkettung und Abschluss auf sich hat, schau dir noch einmal den Artikel Operationen auf Sprachen an.

Reguläre Ausdrücke bilden

Ein Beispiel für einen regulären Ausdruck ist

{a} $\cup$ {a}{a, b}$^*${a}

Sieh dir diesen regulären Ausdruck einmal genau an. Welche Sprachen kommen als Operanden vor? Es sind sehr einfache Sprachen, die nur aus einbuchstabigen Wörtern bestehen, wie {a} oder auch {a, b}. Solche Sprachen heißen Elementarsprachen.

Als Operationen kommen Vereinigung, Verkettung und Abschluss vor. Genau wie bei arithmetischen Ausdrücken "Punktrechnung vor Strichrechnung" geht, so gibt es bei regulären Ausdrücken auch eine Präzedenz der Operatoren: Der Abschluss bindet am stärksten, dann kommt die Verkettung, und die Vereinigung bindet am schwächsten.

Die Reihenfolge der Anwendung ist also bei dem regulären Ausdruck aus dem Beispiel:

• Zuerst wird der Abschluss der Sprache {a, b} gebildet,

• dann werden die Sprachen {a} und {a, b}$^*$ und {a} miteinander verkettet,

• dann werden die Sprachen {a} und {a}{a, b}$^*${a} vereinigt.

Die Auswertung eines arithmetischen Ausdrucks ergibt als Ergebnis eine Zahl, im Beispiel geschrieben als

$2 + 3 \cdot 4 = 1$4

Die Auswertung eines regulären Ausdrucks ergibt eine Sprache als Ergebnis. Im Beispiel ist dies die Sprache aller Wörter über dem Alphabet $A$ = {a, b}, die mit a anfangen und mit a aufhören, geschrieben als

{a} $\cup$ {a}{a, b}$^*${a}  =  {a, aa, aaa, aba, …}

Eine Sprache, die von einem regulären Ausdruck erzeugt wird, heißt reguläre Sprache.

Vereinfachte Schreibweise

Die vielen Mengenklammern machen den regulären Ausdruck unleserlich. Deshalb werden sie weggelassen, und ferner werden die Zeichen $\cup$ und , durch das Zeichen | ersetzt. So vereinfacht sich der reguläre Ausdruck aus dem Beispiel zu

a | a(a|b)$^*$a

Dieser reguläre Ausdruck stellt also die Sprache aller Wörter dar, die entweder aus einem einzelnen a bestehen oder aus einem a, gefolgt von 0, 1 oder beliebig vielen a's oder b's, gefolgt von einem a. Dies sind genau die Wörter, die mit a anfangen und mit a aufhören. Alle diese Wörter werden also gewissermaßen durch ein einziges Muster, nämlich den regulären Ausdruck, beschrieben.

Gelegentlich wird zwischen dem regulären Ausdruck, aufgefasst als Zeichenkette oder als Muster, und der erzeugten regulären Sprache unterschieden, z. B. im Wikipedia-Artikel über reguläre Ausdrücke. Aus einem regulären Ausdruck wie beispielsweise a wird dann mit $L$(a) = {a} die Sprache erzeugt.

Wenn du dagegen ein a in einem regulären Ausdruck als abkürzende Schreibweise für die Sprache {a} auffasst, dann ist die Unterscheidung zwischen regulärem Ausdruck und erzeugter Sprache nicht nötig. Du schreibst dann ohne Weiteres

a | a(a|b)$^*$a   =   {a, aa, aaa, aba, …}

Zum Üben

Als Alphabet legst du im Folgenden $A$ = {a, b} zugrunde. Bilde jeweils reguläre Ausdrücke für die Sprachen, die aus allen Wörtern bestehen, die

• mit bb enden

• nicht mit bb enden

• nur aus a's bestehen und eine ungerade Länge haben

Gar nicht so einfach, oder? Auf der Webseite https://hwlang.de/theor/regulaerer-ausdruck-test.htm kannst du überprüfen, ob deine Lösung richtig ist.

Nachdem du ein wenig Erfahrung im Umgang mit regulären Ausdrücken gewonnen hast, ist es Zeit für die formale Definition.

Definition

Eine Elementarsprache ist eine Sprache, die nur aus einbuchstabigen Wörtern besteht, sie kann auch leer sein. Oder noch etwas formaler:

Mit $A^n$ wird die Sprache aller Wörter der Länge $n$ über dem Alphabet $A$ bezeichnet. Dann ist $L$ eine Elementarsprache, wenn gilt

$L \subseteq A^1$

Eine Sprache heißt reguläre Sprache, wenn sie sich durch endlich viele Anwendungen der Operationen Vereinigung, Verkettung und Abschluss auf Elementarsprachen erzeugen lässt. Ein ent­sprechender Ausdruck, der angibt, in welcher Reihenfolge welche Operationen auf welche Elementar­sprachen angewendet werden, heißt regulärer Ausdruck.

Es ist wichtig, dass du dir bewusst machst, dass der Begriff regulär in Bezug auf Sprachen ein Fachbegriff ist, der genau das bedeutet, was in dieser Definition ausgesagt wird. Es gibt durchaus Sprachen, die irgendwie sehr regelmäßig aufgebaut sind, die aber nicht regulär sind.

Sonderfälle

Jede Elementarsprache ist eine reguläre Sprache, denn sie lässt sich durch 0-malige Anwendung beispielsweise der Operation Vereinigung auf sich selbst erzeugen.

Insbesondere ist auch die leere Menge $\emptyset$ eine reguläre Sprache.

Auch die Sprache $\{\varepsilon\}$ ist regulär, denn es gilt

$\{\varepsilon\} ~ = ~ \emptyset^*$

Weiterlesen

Vielleicht möchtest du als Nächstes weiterlesen, wie reguläre Ausdrücke in Programmiersprachen wie Java, JavaScript, Python, PHP und anderen angewendet werden. Dies ist die eher praktische Seite.

Die eher theoretische Seite beschäftigt sich damit, wie du feststellen kannst, ob ein bestimmtes Wort von einem regulären Ausdruck erzeugt wird. Durch scharfes Hinsehen erkennst du, dass das Wort abba von dem regulären Ausdruck a(a|b)$^*$a erzeugt wird. Aber im Allgemeinen ist dies gar nicht so einfach. Hierzu ist das Konzept des endlichen Automaten hilfreich.