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 nicht die in den vorangegangenen Abschnitten benutzte Festlegung der Metasymbole, sondern eine Variante, die nur ganz wenige Metasymbole benutzt. Diese Variante wird vorwiegend zur Theoriebildung benutzt. Beachte, dass diese Variante das +-Symbol ganz anders benutzt als die Praxisvariante. Das ist sicher verwirrend, hat sich aber so etabliert.
Mit einem regulären Ausdruck wird eine formale Sprache festgelegt. Das soll hier erst einmal anhand von Beispielen aufgezeigt werden.
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 leere 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.