Theoretische Informatik

Regulärer Ausdruck, reguläre Sprache

Definition: 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. Eine solche 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:

`L`₁ = {a, bb, aab, aba, abb}		(endliche Sprache)
`L`₂ = {a, aa, aaa, aba, aaaa, aaba, abaa, ...}		(unendliche Sprache)
alle Wörter, die mit a anfangen und mit a aufhören		(Syntax von `L`₂)

Die Syntax einer unendlichen Sprache kann informell angegeben werden, wie in diesem Beispiel, aber auch formal. Es gibt unterschiedliche Möglichkeiten, die Syntax von Sprachen formal zu beschreiben. Die wichtigsten sind Grammatik, erkennender Automat und regulärer Ausdruck.

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. Das Ergebnis der Auswertung des Ausdrucks ist 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 Operationen sind Vereinigung, Verkettung und Abschluss. Das Ergebnis ist wieder eine Sprache.

Definition: Sei A ein Alphabet und sei A¹ die Menge der Wörter der Länge 1 über A. Wir nennen eine Teilmenge von A¹ eine Elementarsprache.

Eine Sprache L enthalten A* heißt regulär, wenn sie sich durch Anwendung der Operationen Vereinigung, Verkettung und Abschluss auf Elementarsprachen erzeugen lässt. Der entsprechende Ausdruck, der angibt, in welcher Reihenfolge welche Operationen auf welche Elementarsprachen angewendet werden, heißt regulärer Ausdruck.

In regulären Ausdrücken bindet der Abschluss am stärksten, die Verkettung am zweitstärksten und die Vereinigung am schwächsten.

Beispiel: Jede Elementarsprache ist regulär, da sie sich durch Anwendung der Operation Vereinigung auf sich selbst erzeugen lässt. Somit gilt

leere Menge ist regulär, da enthalten A¹,

{a} ist regulär, da {a} enthalten A¹, für alle a Element A.

Ferner gilt

{ε} ist regulär, da {ε} = leere Menge *.

Ist A = {a, b}, so sind beispielsweise folgende Sprachen regulär:

{a, b}*{b} = { b, ab, bb, aab, abb, bab, bbb, aaab, ... }

{a} vereinigt {a}{a, b}*{a}

({a} vereinigt {a}{b})* {b}

Um reguläre Ausdrücke einfacher lesbar zu machen, werden die geschweiften Klammern weggelassen und die Zeichen , und vereinigt werden durch das Zeichen | ersetzt. Aus dem regulären Ausdruck

{a} vereinigt {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 entsprechend bei einem regulären Ausdruck

a*b* = { w | w enthält nicht das Teilwort ba }

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*

Weiter mit: [Erkennung von regulären Sprachen] oder