Reguläre Sprachen/Ausdrücke

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

• für jeden Buchstaben x∈Σ : x∈E

  (autotool: Ziffern oder Kleinbuchstaben)

• das leere Wort ε∈E (autotool: Eps)
• die leere Menge ∅∈E (autotool: Empty)
• wenn A, B∈E, dann
  • (Verkettung) A⋅B∈E (autotool: * oder weglassen)
  • (Vereinigung) A + B∈E (autotool: +)
  • (Stern, Hülle) A^*∈E (autotool: ^*)

Jeder solche Ausdruck beschreibt eine reguläre Sprache.