Fachkonzept - Regulärer Ausdruck

Vorbemerkung

Ein regulärer Ausdruck beschreibt eine Menge von Wörtern. Neben Symbolen des zu Grunde liegenden Alphabets kommen in einem regulären Ausdruck in der Regel auch noch Metasymbole vor. Das sind zusätzliche Symbole, die zur Konstruktion der Wortmenge benutzt werden.

Wir betrachten hier eine Variante zur Bildung regulärer Ausdrücke, die nur ganz wenige Metasymbole benutzt. Diese Variante wird vorwiegend zur Theoriebildung benutzt. Wir verwenden sie hier, um die Grundidee von reguläen Ausdrücken zu beschreiben: Mit einem regulären Ausdruck wird eine formale Sprache festgelegt.

Beispiele

Zur Verdeutlichung der Grundidee betrachten wir zunächst Beispiele für reguläre Ausdrücke über dem Alphabet Σ = {0, 1}:

regulärer Ausdruck Wortmenge / formale Sprache informelle Schreibung der formalen Sprache
Ø {} die leere Sprache
λ {λ} die Sprache, die nur das leeren Wort enthält
0 {0} die Sprache, die nur eine Null enthält
1 {1} die Sprache, die nur eine Eins enthält
10 {10} die Sprache, die nur das Wort bestend aus einer Eins gefolgt von einer Null enthält
0+1 {0, 1} die Sprache, die nur eine Null und eine Eins enthält
1* {λ, 1, 11, 111, 1111, ...} die Sprache, die aus allen Wörtern mit beliebig vielen (auch gar keinen) Einsen besteht
01* {0, 01, 011, 0111, 01111, ...} die Sprache, die aus allen Wörtern besteht, bei denen auf eine Null beliebig viele (auch gar keine) Einsen folgen
0*1* {λ, 0, 00, ..., 1, 01, 001, ..., 11, 011, 0011, ... } die Sprache, die aus allen Wörtern besteht, bei denen auf beliebig viele (auch gar keine) Nullen beliebig viele (auch gar keine) Einsen folgen
0*+1* {λ 0, 00, 000, ..., 1, 11, 111, ...} die Sprache, die aus allen Wörtern mit beliebig vielen (auch gar keinen) Einsen oder Nullen besteht
0+1(0+1)* {0, 1, 10, 11, 100, 101, 110, 111, ...} die Sprache der Binärzahlen

Präzisierung

Wir präzisieren jetzt, wie man die Sprache zu einen regulären Ausdruck erhält.

Reguläre Ausdrücke über dem Alphabet Σ und die Wortmengen, die sie beschreiben, werden wie folgt festgelegt:

Ø ist ein regulärer Ausdruck. Er beschreibt die leere Wortmenge {}.

λ ist ein regulärer Ausdruck. Er beschreibt die Wortmenge {λ}, in der nur das leere Wort vorkommt.

Für jedes a ∈ Σ ist a ein regulärer Ausdruck. Der reguläre Ausdruck a beschreibt die Wortmenge {a}.

Wenn α und β reguläre Ausdrücke sind, dann ist auch die Konkatenation αβ ein regulärer Ausdruck. Wenn α die Wortmenge A und β die Wortmenge B beschreibt, dann beschreibt die Konkatenation αβ die Menge {ab | a ∈ A und b ∈ B} aller Wörter, die mit einem Wort aus A beginnen und mit einem Wort aus B enden.

Wenn α und β reguläre Ausdrücke sind, dann ist auch die Alternative α+β ein regulärer Ausdruck. Wenn α die Wortmenge A und β die Wortmenge B beschreibt, dann beschreibt die Alternative α+β die Menge {w | w ∈ A oder w ∈ B} aller Wörter, die in A oder in B vorkommen.

Wenn α ein regulärer Ausdruck ist, dann ist auch die Iteration α* ein regulärer Ausdruck. Wenn α die Wortmenge A beschreibt, dann beschreibt die Iteration α* die Menge A* aller Wörter, die durch endlich häufiges Aneinanderfügen von Wörtern aus A entstehen.

X

Fehler melden

X

Suche