Reguläre Ausdrücke werden in der theoretischen Informatik zur Beschreibung von Sprachen, also Mengen von bestimmten Wörtern, verwendet. Zu demselben Zweck werden reguläre Ausdrücke auch in Programmiersprachen wie Java, Python, PHP oder JavaScript verwendet, nämlich um Mengen von Wörtern mithilfe eines kompakten Ausdrucks, der quasi als Muster für alle diese Wörter dient, zusammenzufassen. Beispielsweise sind dies Wörter, die in einem bestimmten Zusammenhang zulässig sind (z.B. sollen in einem Eingabefeld nur korrekt gebildete E-Mail-Adressen zulässig sein).
Im Folgenden befassen wir uns mit regulären Ausdrücken in der theoretischen Informatik. Reguläre Ausdrücke in Programmiersprachen folgen genau diesem Ansatz, enthalten darüber hinaus aber noch einige erweiterte Möglichkeiten.
Sei A ein Alphabet. Mit A* bezeichnet man die Menge aller Wörter über A. Jede Teilmenge L von A*, d.h. jede Menge von Wörtern über A, heißt Sprache über A.
Sprachen können endlich viele oder unendlich viele Wörter enthalten. Endliche Sprachen lassen sich einfach durch Aufzählung ihrer Wörter angeben. Um eine unendliche Sprache angeben zu können, benötigt man eine endliche Beschreibung der Sprache.
Es gibt überabzählbar viele Sprachen, aber nur abzählbar viele endliche Beschreibungen. Eine endliche Beschreibung existiert nur, wenn die Sprache nach gewissen Regeln aufgebaut ist. Die Menge dieser Regeln wird als Syntax der Sprache bezeichnet; sie stellt eine endliche Beschreibung der Sprache dar.
Beispiel: Sei A = {a, b}. Beispiele für Sprachen über A sind:
| L1 = {a, bb, aab, aba, abb} | (endliche Sprache) | |
| L2 = {a, aa, aaa, aba, aaaa, aaba, abaa, ...} | (unendliche Sprache) |
Die Syntax einer unendlichen Sprache kann informell angegeben werden, etwa "alle Wörter, die mit a anfangen und mit a aufhören" für die Sprache L2 aus dem Beispiel. Es gibt aber auch unterschiedliche Möglichkeiten, die Syntax von Sprachen formal zu beschreiben. Die wichtigsten sind Grammatik, erkennender Automat und regulärer Ausdruck.
Wir führen reguläre Ausdrücke in Analogie zu arithmetischen Ausdrücken ein.
Ein arithmetischer Ausdruck ist eine Zeichenkette wie z.B.
3 · (6 + 2)
Der Ausdruck beschreibt, welche Operationen in welcher Reihenfolge auf welche Operanden angewendet werden. Die Operanden sind Zahlen, mögliche Operationen sind Addition, Subtraktion, Multiplikation und Division, und das Ergebnis der Auswertung des Ausdrucks ist wieder eine Zahl, in diesem Beispiel 24.
In ähnlicher Weise sind reguläre Ausdrücke definiert. Ein regulärer Ausdruck (engl.: regular expression) beschreibt ebenfalls, welche Operationen in welcher Reihenfolge auf welche Operanden angewendet werden. Hier jedoch sind die Operanden keine Zahlen, sondern Sprachen, und die möglichen Operationen sind Vereinigung, Verkettung und Abschluss. Das Ergebnis ist wieder eine Sprache.
In arithmetischen Ausdrücken geht "Punktrechnung vor Strichrechnung"; in regulären Ausdrücken bindet der Abschluss am stärksten, die Verkettung am zweitstärksten und die Vereinigung am schwächsten. Geklammerte Teilausdrücke werden zuerst ausgewertet.
Definition: Sei A ein Alphabet. Eine Sprache L ⊆ A* heißt regulär, wenn sie sich durch endlich viele Anwendungen der Operationen Vereinigung, Verkettung und Abschluss auf Elementarsprachen über A erzeugen lässt (Elementarsprachen enthalten nur einbuchstabige Wörter).
Der entsprechende Ausdruck, der angibt, in welcher Reihenfolge welche Operationen auf welche Elementarsprachen angewendet werden, heißt regulärer Ausdruck.
Beispiel: Sei A ein Alphabet. Jede Elementarsprache über A, also Teilmenge von A1, ist regulär, da sie sich durch Anwendung der Operation Vereinigung auf sich selbst erzeugen lässt. Somit gilt
∅ ist regulär, da ∅ ⊆ A1,
{a} ist regulär, da {a} ⊆ A1, für alle a ∈ A.
Ferner gilt
{ε} ist regulär, da {ε} = ∅*.
Ist A = {a, b}, so sind beispielsweise folgende Sprachen regulär:
{a, b}*{b} = { b, ab, bb, aab, abb, bab, bbb, aaab, ... }
{a} ∪ {a}{a, b}*{a}
({a} ∪ {a}{b})* ∪ {b}
{a}*{b}*
Um reguläre Ausdrücke einfacher lesbar zu machen, werden die geschweiften Klammern weggelassen und die Zeichen , und ∪ durch das Zeichen | ersetzt. Aus dem regulären Ausdruck
{a} ∪ {a}{a, b}*{a}
wird somit
a | a(a|b)*a
Dieser reguläre Ausdruck erzeugt die Sprache aller Wörter, die mit a anfangen und mit a aufhören. Jedes Wort dieser Sprache ist entweder ein einzelnes a, oder es fängt mit a an, enthält dann beliebig viele a's oder b's, und hört mit einem weiteren a auf.
Es ist gelegentlich notwendig, zwischen dem regulären Ausdruck R und der erzeugten regulären Sprache L(R) zu unterscheiden. Der reguläre Ausdruck R ist eine Zeichenkette, die reguläre Sprache L(R) eine Menge von Wörtern. Meist aber unterscheiden wir nicht zwischen dem Ausdruck selbst und dem von dem Ausdruck erzeugten Wert.
Bei einem arithmetischen Ausdruck schreiben wir
3 · (6 + 2) = 24
und ganz entsprechend bei einem regulären Ausdruck
ab(ab)* = { ab, abab, ababab, ... }
Es kann sein, dass unterschiedliche reguläre Ausdrücke dieselbe Sprache erzeugen. So erzeugen beispielsweise die unterschiedlichen regulären Ausdrücke a(a|b) und aa | ab beide die Sprache { aa, ab }. Wir bezeichnen reguläre Ausdrücke, die dieselbe Sprache erzeugen, als äquivalent, schreiben aber ohne Weiteres etwa
a(a|b) = aa | ab = { aa, ab }
Definition: Zwei reguläre Ausdrücke R und S sind äquivalent, wenn sie dieselbe Sprache erzeugen, d.h. wenn gilt
L(R) = L(S).
Geben Sie reguläre Ausdrücke für folgende Sprachen über dem Alphabet A = {a, b} an:
L0 = { w | w beginnt mit a's und endet mit mindestens zwei b's } =
L1 = { w | w enthält nicht das Teilwort ba } =
L2 = { w | w hat eine gerade Länge } =
Verwenden Sie bei der Eingabe das Zeichen § für ε und das Zeichen % für ∅.
Wir führen Abkürzungen für zwei häufig vorkommende Formen regulärer Ausdrücke ein.
Definition: Sei R ein regulärer Ausdruck. Dann ist
R? = R | ε
R+ = RR*
Beispiel: Es ist
(a|b)? = (a|b) | ε = { ε, a, b }
und
(ab)+ = ab(ab)* = { ab, abab, ababab, ... }
Geben Sie reguläre Ausdrücke für folgende Sprachen über dem Alphabet A = {a, b} an. Verwenden Sie dabei gegebenenfalls die erweiterte Notation.
L3 = { w | w endet auf höchstens ein b } =
L4 = { w | w enthält nicht das Teilwort bb } =
L5 = { w | w hat eine Länge von höchstens 3 } =
Weiter mit: [Syntaxdiagramm] [Reguläre Ausdrücke in Programmiersprachen] oder [up]