Reguläre Ausdrücke

Die Menge der regulären Ausdrücke (r.A.) über \(\varSigma\) ist induktiv definiert durch:

• \(\emptyset, \varsigma, a\) (für \(a \in \varSigma\)) sind r.A. über \(\varSigma\)
• sind r,s reguläre Ausdrücke, so auch (r + s), (r \(\cdot\) s), r*

Beispiel: \((( a + b)^* \cdot a)\)

Die durch einen regulären Ausdruck r definierte Sprache L(r) ist induktiv definiert durch:

• \(L(\emptyset) = \emptyset, L(\varsigma) = \{ \varsigma \}, L(a) = \{ a \} f.a a \in \varSigma\)
• \(L(r + s) = L(r) \cup L(s)\)
• \(L(r \cdot s) = L(r) \cdot L(s)\)
• \(L(r^*) = (L(r))^*\)

\(L(a) = \{ w \in \{ a,b \}^* \mid w = b \vee w = a b^i mit i \ge 0 \}\) und r \(((a \cdot b^*) + b) \widehat{=} a b^* + b\), so ist r = L(a).

Konventionen

• Außenklammern fallen wegen
• \(\cdot\) bindet stärker als +
• \(*\) bindet stärker als \(\cdot\)
• \(\cdot\) darf wegfallen