Theoretische Informatik

Regulärer Ausdruck, reguläre Sprache

 aufwärts

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 Programmier­sprachen wie PHP oder JavaScript verwendet, nämlich um in einem bestimmten Zusammenhang zulässige Wörter mithilfe eines kompakten Ausdrucks zusammen­zufassen (z.B. um zu prüfen, ob in einem Eingabefeld eine E-Mail-Adresse steht).

Im Folgenden befassen wir uns mit regulären Ausdrücken in der theoretischen Informatik. Reguläre Ausdrücke in Programmier­sprachen folgen genau diesem Ansatz, enthalten darüber hinaus aber noch einige erweiterte Möglich­keiten.

 

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.

Syntax von Sprachen

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 über­abzä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 unter­schiedliche Möglich­keiten, die Syntax von Sprachen formal zu beschreiben. Die wichtigsten sind Grammatik, erkennender Automat und regulärer Ausdruck.

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, Multi­plikation 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 "Punkt­rechnung vor Strich­rechnung"; in regulären Ausdrücken bindet der Abschluss am stärksten, die Verkettung am zweit­stärksten und die Vereinigung am schwächsten. Geklammerte Teil­ausdrücke werden zuerst ausgewertet.

Definition:  Sei A ein Alphabet. Eine Sprache L enthalten in A* heißt regulär, wenn sie sich durch endlich viele Anwendungen der Operationen Vereinigung, Verkettung und Abschluss auf Elementar­sprachen über A erzeugen lässt.

Der ent­sprechende Ausdruck, der angibt, in welcher Reihenfolge welche Operationen auf welche Elementar­sprachen angewendet werden, heißt regulärer Ausdruck.

Beispiel:  Sei A ein Alphabet. Jede Elementar­sprache ü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

 leere Menge  ist regulär, da  leere Menge  enthalten in A1,

{a} ist regulär, da {aenthalten in A1, für alle a Element A.

Ferner gilt

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

Ist A = {a, b}, so sind beispiels­weise 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})*  vereinigt  {b}

{a}*{b}*

 

Um reguläre Ausdrücke einfacher lesbar zu machen, werden die geschweiften Klammern weggelassen und die Zeichen , und  vereinigt  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 unter­scheiden. Der reguläre Ausdruck R ist eine Zeichenkette, die reguläre Sprache L(R) eine Menge von Wörtern. Meist aber unter­scheiden 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, ... }

Äquivalente reguläre Ausdrücke

Es kann sein, dass unter­schiedliche reguläre Ausdrücke dieselbe Sprache erzeugen. So erzeugen beispiels­weise die unter­schiedlichen 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).

Übungen

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  leere Menge .

Erweiterte Notation

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, ... }

Übungen

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

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 12.11.1997   Updated: 12.09.2017
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik