Reguläre Ausdrücke

Theorie Icon Reguläre Ausdrücke beschreiben eine Familie von formalen Sprachen. Diese Sprachen, die regulären Sprachen, befinden sich auf der untersten und somit ausdrucksschwächsten Stufe der Chomsky-Hierarchie (Typ 3). Sie werden erzeugt durch reguläre Grammatiken.

Definition

Formal werden reguläre Ausdrücke wie folgt definiert:

  • \(\emptyset\) ist ein regulärer Ausdruck.
  • \(\epsilon\) ist ein regulärer Ausdruck.
  • Für jedes \( a \in \sum \) ist \( a \) ein regulärer Ausdruck.
  • Wenn \(\alpha\) und \(\beta\) reguläre Ausdrücke sind, dann sind
    • die Konkatenation \(\alpha \beta\)
    • die Alternative \(\alpha | \beta\)
    • die Iteration \((a)^*\) reguläre Ausdrücke
Anmerkung: \(a^+\) ist die Kurzschreibweise für \((a | a*)\), also mind. einmal \(a\).

Übung