Reguläre Sprachen/Ausdrücke

Die Menge E($\Sigma$) der regulären Ausdrücke
über einem Alphabet (Buchstabenmenge) $\Sigma$
ist die kleinste Menge E, für die gilt:

• für jeden Buchstaben x $\in$ $\Sigma$ : x $\in$ E

  (autotool: Ziffern oder Kleinbuchstaben)

• das leere Wort $\epsilon$ $\in$ E (autotool: Eps)
• die leere Menge $\emptyset$ $\in$ E (autotool: Empty)
• wenn A, B $\in$ E, dann
  • (Verkettung) A ^. B $\in$ E (autotool: * oder weglassen)
  • (Vereinigung) A + B $\in$ E (autotool: +)
  • (Stern, Hülle) A^* $\in$ E (autotool: ^*)

Jeder solche Ausdruck beschreibt eine reguläre Sprache.