Informatik

Wann ist eine Sprache regulär?

Eine Sprache $L$ ist regulär, wenn sie von einem deterministischen oder nichtdeterministischen endlichen Automaten (DFA/NFA) erkannt werden kann oder wenn sie durch einen regulären Ausdruck beschrieben werden kann.

Formelle Definition

Eine Sprache $L$ ist regulär, wenn es einen endlichen Automaten $M = (Q, Σ, δ, q_0, F)$ gibt, wobei:

• $Q$ die endliche Menge der Zustände ist.
• $Σ$ das endliche Eingabealphabet ist.
• $δ: Q \times Σ \rightarrow Q$ die Übergangsfunktion ist.
• $q_0 \in Q$ der Startzustand ist.
• $F \subseteq Q$ die Menge der Endzustände ist.

Beispiel

Die Sprache $L = \{ a^n b^n \,|\, n \geq 0 \}$ ist nicht regulär, während die Sprache $L' = \{ a^n \,|\, n \geq 0 \}$ regulär ist, da sie von einem DFA erkannt werden kann:

DFA für $L$: