Reguläre Sprache

Die einfachste Sprachklasse (Typ 3). Sie wird gleichwertig durch endliche Automaten erkannt, durch reguläre Ausdrücke beschrieben und durch Typ-3-Grammatiken erzeugt.

Drei gleichwertige Beschreibungen

Jede Form lässt sich in jede andere umwandeln (Quelle - Automatentheorie Zusammenfassung).

Reguläre Ausdrücke

• Bausteine: ∅ (leere Sprache), ε (leeres Wort), jedes Symbol a ∈ Σ.
• Operatoren: Konkatenation αβ, Auswahl α|β (Vereinigung), Iteration α* (Kleene-Stern).
• Beispiele: a* = {ε, a, aa, …}; a(a|b) = {aa, ab}; ba | a*b = {ba, b, ab, aab, …}.
• Rechenregeln: εα = α (neutral bei Konkatenation), ∅|α = α (neutral bei Auswahl), ∅α = ∅, α|α = α, ∅* = ε, a(b|c) = ab|ac, (10)*1 = 1(01)*, (a|b)* = (a*b*)*.
• Anwendung: Ein Scanner-Generator (z.B. lex) wandelt einen regulären Ausdruck automatisch in einen endlichen Automaten um. So entstehen Scanner für Compiler und Prüfroutinen für Eingabefelder, ohne dass man sie von Hand programmieren muss (Quelle - Automatentheorie Zusammenfassung).

Typ-3-Grammatiken

G = (Σ, N, P, S): Terminale, Nichtterminale, Produktionen, Startsymbol.

• Rechtslinear: Regeln der Form A → aB oder A → a. Das Wort wächst von links nach rechts.
• Linkslinear: A → Ba oder A → a. Das Wort wächst von rechts nach links.
• Beide sind gleichwertig und lassen sich durch Spiegelung ineinander umformen.
• Beispiel (rechtslinear, Wörter über {0,1}, deren drittletztes Zeichen 0 ist): S → 0S | 1S | 0A, A → 0B | 1B, B → 0 | 1.

Eigenschaften

• Triviale Sprachen sind regulär: ∅, Σ, Σ*, {w} und jede endliche Sprache.
• Abgeschlossen unter Vereinigung, Durchschnitt, Differenz, Komplement, Konkatenation, Kleene-Stern und Spiegelung. Für das Komplement nimmt man einen vollständigen DFA und vertauscht End- und Nicht-Endzustände.
• Entscheidbar: Wortproblem, Leerheit, Äquivalenz.

Pumping-Lemma (regulär)

Ist L regulär, so gibt es ein n (z.B. die Zustandszahl eines DFA für L). Jedes Wort x ∈ L mit |x| ≥ n lässt sich zerlegen in x = uvw mit |v| ≥ 1 und |uv| ≤ n, sodass uvⁱw ∈ L für alle i ≥ 0 gilt.

• Die Bedingung ist notwendig, nicht hinreichend. Man kann damit nur zeigen, dass eine Sprache nicht regulär ist.
• Nicht regulär sind z.B. {aᵏbᵏ | k ≥ 0} und {a^(k²) | k ≥ 1}. Praktisch betrifft das Klammerstrukturen: arithmetische Ausdrücke und blockstrukturierte Programmiersprachen (Quelle - Automatentheorie Zusammenfassung).

Verwandt

• Endlicher Automat – erkennendes Modell
• Kontextfreie Sprache – die nächstgrössere Klasse (Typ 2)
• Chomsky-Hierarchie – Gesamtbild
• Formale Sprache – Grundbegriffe und Operationen