Reguläre Ausdrücke

Um die Wörter zu beschreiben, die ein deterministischer endlicher Automat akzeptiert, benutzt man sogenannte reguläre Ausdrücke. Sie werden durch folgende Regeln beschrieben:

1. ab; das Zeichen a gefolgt von Zeichen b
2. 1. a|b; das Zeichen a oder das Zeichen b
   2. [a-c]; das Zeichen a, b oder c
3. 1. a*; das Zeichen a beliebig oft (auch keinmal)
   2. (ab)*; die Zeichenfolge ab beliebig oft (auch keinmal)
   3. [a-c]*; das Zeichen a, b oder c beliebig oft (auch keinmal)
4. a+; das Zeichen a keinmal oder einmal

Beispiele

Die Sprache L(M) = {a|b a* [a-c]} kann von dem Automaten beispielsweise als baaaac oder ac gelesen werden.