Reguläre Sprachen

Definition

Eine reguläre Sprache ist eine formale Sprache, die von einem endlichen Automaten erkannt wird. Sie können mit regulären Ausdrücken beschrieben und durch reguläre Grammatiken erzeugt werden.

---

Formale Definition

Eine Sprache L ist regulär, wenn es einen deterministischen (DEA) oder nichtdeterministischen endlichen Automaten (NEA) gibt, der L akzeptiert.

Ein DEA wird definiert als:
M = (S, Σ, δ, s0, F)

• S: Endliche Menge von Zuständen
• Σ: Eingabealphabet
• δ: Übergangsfunktion $S\times \Sigma \to S$
• s0: Startzustand
• F: Menge der Endzustände $F\subseteq S$

Ein NEA kann mehrere mögliche Übergänge für ein Zeichen haben, während ein DEA für jedes Zeichen einen eindeutigen Folgezustand hat.

---

Reguläre Grammatiken

Eine reguläre Grammatik besteht aus Produktionen der Form:

• Rechtslinear: $A\to aB$ oder $A\to a$
• Linkslinear: $A\to Ba$ oder $A\to a$

Jede reguläre Grammatik kann in einen endlichen Automaten umgewandelt werden und umgekehrt.

---

Reguläre Ausdrücke

Reguläre Ausdrücke sind eine Schreibweise zur Darstellung regulärer Sprachen. Die wichtigsten Operatoren sind:

Notation	Bedeutung
a	Symbol „a“
ε	Leeres Wort
r|s	„r oder s“
rs	„r gefolgt von s“
r*	„r beliebig oft“
r+	„r mindestens einmal“
r?	„r optional“

Beispiel:

(0|1)*1

Diese Sprache enthält alle Binärzahlen mit mindestens einer 1.

---

NEA zu DEA (Potenzmengenkonstruktion)

Ein nichtdeterministischer Automat (NEA) kann durch die Potenzmengenkonstruktion in einen deterministischen Automaten (DEA) umgewandelt werden. Dabei wird jeder Zustand des DEA als eine Menge von NEA-Zuständen betrachtet.

Die Anzahl der Zustände des DEA kann dabei exponentiell ansteigen.

---

Eigenschaften regulärer Sprachen

Reguläre Sprachen sind unter folgenden Operationen abgeschlossen:

• Vereinigung: $L_1\cup L_2$ ist regulär.
• Konkatenation: $L_1{L}_2$ ist regulär.
• Stern-Operator: $L^{\ast }$ ist regulär.
• Komplement: $\bar{L}$ ist regulär.
• Schnitt: $L_1\cap L_2$ ist regulär.

---

Grenzen regulärer Sprachen

Reguläre Sprachen können keine Sprachen mit tief verschachtelten Strukturen (wie z. B. (a^n b^n)) ausdrücken. Dazu sind kontextfreie Sprachen notwendig.

Mit dem Pumping Lemma kann gezeigt werden, dass eine Sprache nicht regulär ist.

---

Anwendungen

Reguläre Sprachen werden in vielen Bereichen eingesetzt, z. B.:

• Lexikalische Analyse in Programmiersprachen
• Suchmuster in Textdateien (z. B. mit grep oder regex in Programmiersprachen)
• Filterung von Zeichenketten (E-Mail-Adressen, IP-Adressen)

---

Zusammenfassung

• Reguläre Sprachen werden von endlichen Automaten erkannt.
• Sie können durch reguläre Ausdrücke oder reguläre Grammatiken dargestellt werden.
• Sie sind unter Vereinigung, Konkatenation, Stern-Operator und Komplementbildung abgeschlossen.
• Nicht alle Sprachen sind regulär – komplexere Strukturen benötigen kontextfreie oder noch mächtigere Grammatiken.