✖

Reguläre Ausdrücke

Ein regulärer Ausdruck ist eine Zeichenkette, mit der sich eine Menge von Wörtern beschreiben lässt. Reguläre Ausdrücke können wir auch als einfache Möglichkeit verstehen, einen endlichen Automaten zu beschreiben.

Was ist ein regulärer Ausdruck

In der Arithmetik verwenden wir Symbole wie · und +, um einen Term wie (2 + 3) · 4 aufzustellen. Wenn wir diesen Term auswerten, erhalten wir eine Zahl. Ein regulärer Ausdruck ist eine Folge von Zeichen und einigen speziellen Symbolen, z. B. a(x ∪ y), deren Auswertung eine (formale) Sprache ist. Das Ergebnis des Terms (2 + 3) · 4 ist die Zahl 20, das Ergebnis des regulären Ausdrucks a(x ∪ y) ist die Menge der beiden Wörter „ax“, „ay“.

Wie würden wir den vorigen regulären Ausdruck a(x ∪ y) auswerten? Jeder Buchstabe ist in Wirklichkeit eine Abkürzung für die einelementige Menge, die diesen Buchstaben enthält, und die versteckte Multiplikation ist die Verkettung von Wörtern. Den regulären Ausdruck könnten wir „ausführlich“ so umschreiben:

{a}∘({x}∪{y})

Weiter würden wir ihn so auswerten: Die Vereinigung {x} ∪ {y} ergibt die Sprache {x; y}. Durch die Konkatenation der Sprachen {a} und {x; y} erhalten wir die Sprache {ax; ay}.

Reguläre Ausdrücke werden in der Programmierung sehr häufig verwendet, und die meisten Programmiersprachen haben sie in irgendeiner Form implementiert. Reguläre Ausdrücke dienen zum Beispiel dazu, zu überprüfen, ob ein vom Nutzer eingegebener Text bestimmte Kriterien erfüllt (z. B. ob es eine gültige E-Mail-Adresse oder ein gültiges Datum ist usw.), und außerdem zum Ersetzen von Texten (z. B. wenn wir alle URLs in einem Text durch anklickbare Links ersetzen wollen).

Reale Implementierungen regulärer Ausdrücke sind meist mächtiger als die hier beschriebenen regulären Ausdrücke und verwenden eine etwas andere, vor allem aber kompliziertere Syntax.

Definition des regulären Ausdrucks

Wir definieren einen regulären Ausdruck über einem Alphabet Σ. Dann sagen wir, dass ein regulärer Ausdruck Folgendes ist:

  1. a, wobei a ∈ Σ. Also ist ein einzelnes Zeichen des Alphabets ein regulärer Ausdruck.
  2. ϵ: das leere Wort, in der Programmierung wird es auch als leere Anführungszeichen "" geschrieben.
  3. ∅: Ein regulärer Ausdruck muss auch die leere Sprache beschreiben können, also ist die leere Sprache ein regulärer Ausdruck.
  4. (R1 ∪ R2), wobei R1, R2 reguläre Ausdrücke sind.
  5. (R1 ∘ R2), wobei R1, R2 reguläre Ausdrücke sind.
  6. (R∗), wobei R ein regulärer Ausdruck ist.

Anstelle des Symbols ∪ aus Punkt 4 können wir auch den senkrechten Strich verwenden: |. Das Symbol ∘ können wir auch ganz weglassen. So wie wir meistens das Multiplikationszeichen, den Malpunkt ·, nicht direkt schreiben, schreiben wir meistens auch das Symbol der Konkatenation ∘ nicht. Diese regulären Ausdrücke sind also identisch: a ∘ (b ∪ c) und a(b|c).

Was bedeuten die einzelnen Operatoren?

  • ∪ oder | bezeichnet die Vereinigung von Sprachen.
  • ∘ bezeichnet die Konkatenation von Sprachen.
  • ∗ bezeichnet den Kleene-Stern einer Sprache.

Beispiele:

  • a bezeichnet die einfache Sprache {a}.
  • a|b bezeichnet die Sprache, die aus den zwei Wörtern {a; b} besteht.
  • a ∘ b bezeichnet die Sprache {ab}.
  • a(b|c)d bezeichnet die Sprache {abd; acd}.
  • a(b∗) bezeichnet die Sprache aller Wörter, die mit dem Buchstaben „a“ beginnen, auf den beliebig viele Buchstaben „b“ folgen.
  • (ab)∗ bezeichnet die Sprache aller Wörter {ϵ; ab; abab; ababab; …}.
  • 0∗10∗ bezeichnet die Sprache aller Binärwörter, die genau eine Eins enthalten. (Beachte, dass es genauer wäre, diesen Ausdruck so zu schreiben: (0∗)1(0∗), aber wenn die Schreibweise auch ohne das lesbar ist, können wir die Klammern weglassen.)
  • Σ∗1Σ∗ bezeichnet die Sprache aller Wörter, die mindestens eine Eins enthalten.
  • (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)∗ bezeichnet die Sprache aller natürlichen Zahlen.

Als Nächstes zeigen wir die Äquivalenz zwischen regulären Ausdrücken und endlichen Automaten. Für jeden regulären Ausdruck, dessen Auswertung eine Sprache R ist, gibt es einen endlichen Automaten A mit L(A) = R und umgekehrt.

Quellen

Kapitel: Reguläre Ausdrücke, Umwandlung eines regulären Ausdrucks in einen Automaten, Verallgemeinerter nichtdeterministischer endlicher Automat, Umwandlung eines Automaten in einen regulären Ausdruck