Reguläre Ausdrücke (1)
Ein oft bequemes Hilfsmittel zur Notation von Sprachen der
Klasse 3 sind
reguläre Ausdrücke
über einem (Terminal-)Alphabet A.
Jeder solche Ausdruck R bezeichnet eine Menge von Wörtern aus A*,
und die Ausdrücke sind durch folgende Regeln definiert:
- ist ein regulärer Ausdruck,
- a ist ein regulärer Ausdruck
für jedes aA,
- (R) ist ein regulärer Ausdruck,
wenn R ein regulärer Ausdruck ist (Klammerung),
- R1|R2 ist ein regulärer Ausdruck,
wenn R1 und R2 reguläre Ausdrücke sind (Alternative),
- R* ist ein regulärer Ausdruck,
wenn R ein regulärer Ausdruck ist (Stern-Bildung),
- sonst gibt es nichts.
Die Symbole { ( ) | * } sind hier
Metasymbole, die nicht zu A gehören.
Die Bedeutung der regulären Ausdrücke ist folgende:
- bezeichnet die Menge {},
die nur aus dem leeren Wort besteht;
- a bezeichnet die (einelementige) Menge {a};
- (R) bedeutet dieselbe Menge wie R,
die Klammern dienen nur der Zusammenfassung;
- R1|R2 bedeutet die Vereinigung R1R2;
- R* bezeichnet die Menge, die durch 0-mal oder öfter
durchgeführte Verkettung der Menge R
mit sich selbst entsteht, also:
R* = {} R RR RRR . . .
Manchmal verwendet man auch R+ als Abkürzung für
R R* = R* R = R* - {}.
Die regulären Ausdrücke sind ebenso mächtig wie die anderen
Mechanismen zur Beschreibung von Sprachen der
Klasse 3.
In der Kommandosprache des Betriebssystems UNIX
(einschließlich seiner Varianten wie Linux )
werden häufig Erweiterungen der angegebenen Notation verwendet;
sie bringen nichts Neues,
erleichtern aber öfters die Aufschreibung.
zurück |
Inhalt | Index |
vor |
Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36