Reguläre Ausdrücke
Aus Informatik
Es sei X ein Alphabet. Die regulären Ausdrücke über X und die Wortmengen, die sie bezeichnen, sind folgendermaßen definiert:
-
ist ein regulärer Ausdruck und bezeichnet die leere Menge {}.
- ε ist ein regulärer Ausdruck und bezeichnet die Menge {ε}.
- Für jedes
ist x ein regulärer Ausdruck und bezeichnet die Menge {x}.
- Sind a und b reguläre Ausdrücke für die Mengen A und B, so sind (a + b), (ab) und (a*) reguläre Ausdrücke und bezeichnen die Mengen
, AB und A * .
- Nur die gemäß den Regeln 1. bis 4. erzeugten Ausdrücke sind regulär.
Die Klammern können wir gegebenenfalls auch weglassen, wenn wir folgende Prioritätsregeln einführen: Die Iteration ist zuerst auszuführen, dann das Produkt und dann die Summe. Die von einem regulären Ausdruck r bezeichnete Wortmenge heißt auch die zu ihm gehörende reguläre Sprache L(r).
In mengentheoretischer Schreibweise gilt für die Verknüpfung von Sprachen:
Gegeben sei ein Alphabet X und 
als Sprachen über X. Dann definieren wir folgende Operationen:
-
Vereinigung von S und T
-
Durchschnitt von S und T
-
Differenz von S und T
-
Produkt von S und T
- S0: = {ε}
Beispiele
Gegeben sei das Alphabet X= {a,b}.
Dann ist a+b ein regulärer Ausdruck für die Sprache {a,b}, ab ein regulärer Ausdruck für die Sprache {ab} und a* ein regulärer Ausdruck für die Sprache {ε,a,aa,aaa,aaaa,...}.
Die Menge aller Worte X* lässt sich durch den regulären Ausdruck (a+b)* beschreiben.
Der reguläre Ausdruck (a+b)*aa(a+b)* bezeichnet die Menge aller Worte aus X*, die wenigstens zwei aufeinander folgende a enthalten, und der reguläre Ausdruck (a+b)*bba die Menge aller Worte, die auf bba enden.
Ferner bezeichnet (a+ab)* die Menge {ε,a,aa,ab,aaa,aab,aba,aaaa,aaab,aaba,abaa,abab,...}, d. h. die Menge der Worte, bei denen jedem b zwingend ein a vorsteht.
Der erweiterte reguläre Ausdruck (ε+b)(a+ab)* bezeichnet dann die Menge {ε,a,b,aa,ab,ba,aaa,aab,baa,bab,aaaa,aaab,aaba,abab,baaa,baab,baba,...}, d. h. die Menge aller Worte, die keine zwei aufeinander folgende b enthalten.
