Reguläre Sprachen und endliche Automaten
Eingeordnet in Informatik
Geschrieben am in
Deutsch mit einer Größe von 2,92 KB
Reguläre Sprachen
Betrachten Sie das Alphabet Σ = {a, b}. Für jede natürliche Zahl n gibt es nur eine endliche Anzahl an Wörtern der Länge n. Diese Strings lassen sich lexikographisch ordnen: 0 für die Länge 0, Wörter der Länge 1, und allgemein für die Länge n+1. Beispiel: ε → 0, a → 1, b → 2, aa → 3, ab → 4 ...
Allgemein gilt: Da alle endlichen Alphabete abzählbar sind, können wir die Zeichen in einer beliebigen Reihenfolge anordnen: Σ = {a₀, a₁, a₂, ..., aₙ}. Die Menge aller Sprachen über Σ ist jedoch nicht abzählbar unendlich.
Reguläre Sprachen und reguläre Ausdrücke
Eine Sprache über einem Alphabet Σ ist regulär, wenn sie rekursiv wie folgt definiert ist:
- a) ∅ ist eine reguläre Sprache (leere Sprache)