Reguläre Ausdrücke/Sprachen

Die Menge aller möglichen Werte einer Tokenklasse ist üblicherweise eine reguläre Sprache, und wird (extern) durch eine regulären Ausdruck beschrieben.

Zur Erinnerung: Chomsky-Hierarchie

• (Typ 0) aufzählbare Sprachen (beliebige Grammatiken, Turingmaschinen)
• (Typ 1) kontextsensitive Sprachen (monotone Grammatiken, linear beschränkte Automaten)
• (Typ 2) kontextfreie Sprachen (kontextfreie Grammatiken, Kellerautomaten)
• (Typ 3) reguläre Sprachen (rechtslineare Grammatiken, reguläre Ausdrücke, endliche Automaten)

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.