2.3 Reguläre Ausdrücke
Wir kennen nun die Begriffe Alphabet, Wort und Sprache. Ziel ist es noch immer, einen Mechanismus zu finden, der entscheiden kann, ob ein Wort zu einer Sprache mit gewissen Regeln gehört oder nicht.
Reguläre Ausdrücke sind spezielle Formeln, die reguläre Sprachen beschreiben können. Starten wir mit Beispielen.
Beispiele
- Ein regulärer Ausdruck, der die Sprache aller Binärwörter der Länge eins beschreibt, ist \(\underbrace{(0|1)}_ {0 \:oder\: 1}\).
- Ein regulärer Ausdruck, der die Sprache aller Binärwörter der Länge drei beschreibt, ist \((0|1)(0|1)(0|1)\).
- Ein regulärer Ausdruck, der die Sprache aller Binärwörter beschreibt, ist \(\underbrace{(0|1)^*}_ {0 \: oder \: 1, \:beliebig \: oft}\)
- Ein regulärer Ausdruck, der die Sprache aller Binärwörter beschreibt, die das Teilwort \(000\) enthalten, ist \((0|1)^*000(0|1)^*\).
Definition: Reguläre Ausdrücke
Es sei \(Σ\) ein beliebiges Alphabet. Die Sprache \(RA_Σ\) der regulären Ausdrücke über \(Σ\) ist wie folgt definiert:
- \(\emptyset , ε \in RA_Σ\)
- \(a \in RA_Σ\) für ein \(a \in Σ\)
- \(R \in RA_Σ ⇒ (R^*) \in RA_Σ\)
- \(R, S \in RA_Σ ⇒ (RS) \in RA_Σ\)
- \(R, S \in RA_Σ ⇒ (R|S) \in RA_Σ\)
Erläuterungen zur Definition
- Die Sonderzeichen \(\emptyset\) und \(ε \) (die Repräsentation vom leeren Wort und das leere Wort selber) sind reguläre Ausdrücke.
- Jedes Symbol aus dem Alphabet \(Σ\) ist auch ein regulärer Ausdruck über \(Σ\).
- Kleensche Hülle: Ist \(R\) ein regulärer Ausdruck über \(Σ\), dann ist auch \((R^∗)\) ein regulärer Ausdruck über \(Σ\).
- Konkatenation: Sind \(R\) und \(S\) reguläre Ausdrücke über \(Σ\), dann ist auch \((RS)\) ein regulärer Ausdruck über \(Σ\).
- Alternative: Sind \(R\) und \(S\) reguläre Ausdrücke über \(Σ\), dann ist auch \((R|S)\) ein regulärer Ausdruck über \(Σ\).
Übung
Welche Wörter werden von den folgenden RA über \(Σ= \{a, b \}\) beschrieben?
- a(b(ba)a)
- (ab)|(baa)
- ((ab)|(baa))bb
- (aa)*b
- ((ba)|b)*
- (bb)*a*b(ba)
- Erinnern wir uns an die Frage “Ist \(10.13.1997\) ein Wort der Sprache, die Daten beschreibt?”. Diese Frage können wir beantworten, indem wir das Format überprüfen. Computer machen dies ebenfalls. Dazu stellen wir einen regulären Ausdruck für erlaubte Geburtsdaten (ab dem Jahr 1900 und Schaltjahre ignoriert) auf. Wie sehen das passende Alphabet und der passende Reguläre Ausdruck aus? Lösung
Rangfolge der Operatoren
Überflüssige Klammern werden weggelassen, damit die Ausdrücke leichter zum lesen sind.
Damit ein regulärer Ausdruck nicht mehrdeutig gelesen werden kann, gilt die folgende Rangfolge der Operatoren: ∗ vor Konkatenation und Konkatenation vor |.
Beispiele
- \(ab^*\) wird als \(a(b^*)\) gelesen.
- \(ab|ba\) wird als \((ab)|(ba)\) gelesen.
- \(a|b^*\) wird als \(a|(b^*)\) gelesen.
- \(ab^∗|c\) wird als \(((a(b^∗))|c)\) gelesen.
Mehr zu regulären Ausdrücken
Aus den nun bekannten Operationen von regulären Ausdrücken lassen sich weitere Operationen bilden. Diese weiteren Operationen erlauben eine noch effizientere und übersichtlichere Notation und sind insbesondere beim Programmieren von längeren Programmen hilfreich. Ein gut aufgebautes Tutorial dazu finden Sie auf RegexOne. Eine alternative Webseite zum Üben von regulären Ausdrücken wäre Regex Crossword.
Hier haben Sie die Option Notizen, Screenshots und Bilder zu diesem Abschnitt hochzuladen. Wir empfehlen eine sinnvolle Beschriftung wie z. B. 2_3_regEx_Notizen.
Ich glaube die Auflösung für Übung 6 ist falsch. Das Wort endet auf bba und nicht auf bab
Korrekt, die Lösung wurde angepasst. Als Belohnung haben Sie sich eine Schokolade verdient. 🙂