Regulärer Ausdruck

Einfache Sprache

Ein Regulärer Ausdruck besteht aus Konstanten (z.B.: $1,0$) und Operatoren ($*,\circ, |$). Die Semantik beschreibt welche Sprache ein regulärer Ausdruck erkennt.

Def. Regulärer Ausdruck

Sei $A$ ein Alphabet. Syntax: Die Menge $Reg$ der regulären Ausdrücke ist die kleinste Menge, so dass gilt:

• $\varepsilon\in Reg$
• $\emptyset\in Reg$
• $a\in Reg$ f.a. $a\in A$

Seien $R_1,R_2\in Reg$, dann gilt

• $(R_1\circ R_2)\in Reg$
• $(R_1|R_2)\in Reg$
• $(R^*)\in Reg$

Semantik: Sei $L:Reg\rightarrow\mathcal{P}(A^*)$ eine Abbildung so, dass:

$$L(\varepsilon)=\{\varepsilon\},\;L(\emptyset)=\emptyset,\;L(a)=\{a\}$$

f.a. $a\in A$ und sei $R_1,R_2\in Reg$, dann gilt

• $L(R_1+R_2)=L(R_1)\circ L(R_2)$
• $L(R_1|R_2)=L(R_1)\cup L(R_2)$
• $L(R_1^*)=L(R_1)^*$

Konvention

• Wir schreiben $R_1R_2$ für $R_1\circ R_2$
• Bindungsstärke in absteigender Reihenfolge sei: $^*,\circ,|$
• Klammern können entsprechend der Bindungsstärke entfallen