Formale Sprache

Eine Menge von Wörtern (endlichen Zeichenfolgen) über einem Alphabet. Sie wird durch Automaten erkannt oder durch Grammatiken erzeugt und ist das Grundobjekt der Automatentheorie.

Grundbegriffe

• Alphabet Σ: endliche Menge von Symbolen, z.B. {0, 1} oder {a, b, c}.
• Wort: endliche Folge von Symbolen. Das leere Wort ε hat die Länge 0 und ist neutral: εw = wε = w.
• Σ*: Menge aller Wörter über Σ (einschliesslich ε). Σ⁺ = Σ* − {ε}: alle Wörter ohne das leere.
• Sprache L ⊆ Σ*: beliebige Teilmenge davon. Zu unterscheiden sind die leere Sprache ∅ (enthält kein Wort) und {ε} (enthält genau das leere Wort) (Quelle - Automatentheorie Zusammenfassung).

Operationen auf Sprachen

• Konkatenation: L₁L₂ = { uv | u ∈ L₁, v ∈ L₂ }
• Potenz: L⁰ = {ε}, Lⁿ⁺¹ = LⁿL
• Kleene-Stern: L* = L⁰ ∪ L¹ ∪ L² ∪ …, die Vereinigung aller Potenzen
• Dazu Vereinigung, Durchschnitt, Differenz, Komplement (Σ* − L) und Spiegelung SP(L)

Ob eine Sprachklasse unter diesen Operationen abgeschlossen ist, unterscheidet die Klassen: Reguläre Sprachen sind unter allen abgeschlossen, kontextfreie nicht unter Durchschnitt und Komplement → Reguläre Sprache, Kontextfreie Sprache.

Zwei Blickwinkel

Wie die drei Sichten zusammenhängen, zeigt die Chomsky-Hierarchie.

• Wortproblem: Gehört ein Wort w zur Sprache L? Je nach Sprachklasse ist es entscheidbar oder nicht → Berechenbarkeit.
• Abzählbarkeit: Es gibt nur abzählbar viele Grammatiken bzw. Turingmaschinen, aber überabzählbar viele Sprachen (die Potenzmenge von Σ*). Also gibt es Sprachen, die keine Grammatik erzeugen kann (Quelle - Automatentheorie Zusammenfassung).

Verwandt

• Endlicher Automat – das einfachste erkennende Modell
• Chomsky-Hierarchie – Einteilung der Sprachklassen
• Wissensbasierte Bildanalyse – formale Grammatiken zur Beschreibung von Bildinhalten