Reguläre Sprachen/Ausdrücke

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

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

  (autotool: Ziffern oder Kleinbuchstaben)

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

Jeder solche Ausdruck beschreibt eine reguläre Sprache.