Formale Sprache

Grundidee und Bedeutung

Eine formale Sprache ist eine genau festgelegte Menge von endlichen Symbol- oder Zeichenketten, die als „Wörter“ der Sprache bezeichnet werden. Die zulässigen Zeichen stammen aus einem Alphabet. Anders als bei natürlichen Sprachen steht meist nicht die menschliche Kommunikation im Mittelpunkt, sondern die präzise Definition und Anwendung formaler Systeme. Formale Sprachen werden besonders in der Logik, Mathematik, Linguistik und theoretischen Informatik verwendet.

Mit ihnen lassen sich beispielsweise Datenformate und Programmiersprachen eindeutig beschreiben. Eine formale Semantik ordnet den Zeichenketten eine Bedeutung zu. So kann einer Anweisung einer Programmiersprache ein eindeutiges Maschinenverhalten zugewiesen werden. Formale Sprachen bilden außerdem die Grundlage für Logikkalküle, mit denen mathematische Schlüsse gezogen oder Programme auf Korrektheit überprüft werden können.

Definition und Erzeugung

Eine formale Sprache L über einem Alphabet Σ ist eine Teilmenge der Kleeneschen Hülle dieses Alphabets:

L ⊆ Σ*.

Das Alphabet Σ legt fest, welche Zeichen in den Wörtern vorkommen dürfen. Für Dezimaldarstellungen kann beispielsweise Σ = {0,1,2,3,4,5,6,7,8,9} gewählt werden.

Die Kleenesche Hülle Σ* ist die Menge aller aus den Zeichen von Σ bildbaren Wörter endlicher Länge. Dazu gehört auch das leere Wort ε mit der Länge 0. Eine formale Sprache wählt aus Σ* bestimmte Wörter aus; deshalb muss nicht jede mögliche Zeichenkombination ein gültiges Wort der Sprache sein. Eine formale Sprache kann leer, endlich oder unendlich sein. Im größtmöglichen Fall ist sie gleich Σ*.

Eine Sprache kann durch eine mathematische Bedingung an ihre Wörter definiert werden. Häufig wird sie in der theoretischen Informatik aber durch Ersetzungsregeln festgelegt. Bei einer generativen Grammatik entsteht ein Wort schrittweise aus einer Startzeichenkette, indem Regeln wiederholt beziehungsweise rekursiv angewendet werden. Zu solchen Regelsystemen zählen Semi-Thue-Systeme, Chomsky-Grammatiken und Lindenmayer-Systeme. Umgekehrt kann eine Sprache auch aus allen Wörtern bestehen, die sich mithilfe der Regeln auf ein oder mehrere vorgegebene Wörter zurückführen lassen.

Abgrenzung und Beispiele

Formale Sprachen können natürliche Sprachen modellieren, vor allem deren Syntax. Natürliche Sprachen besitzen oberhalb der elementaren Laute oder Zeichen mindestens die Ebenen Wort und Satz. Der Wortaufbau wird gewöhnlich durch die Morphologie, der Satzaufbau durch die Syntax beschrieben. Bei formalen Sprachen gibt es über den Alphabetzeichen häufig nur die Ebene des formalen Wortes; dessen Aufbau heißt ebenfalls Syntax. Wird eine natürliche Sprache formal modelliert, gelten ihre Sätze daher aus formalsprachlicher Sicht als Wörter.

Typische Beispiele sind:

• Die Programmiersprache C ist eine formale Sprache. Ihre Wörter sind vollständige Programme; ihr Alphabet besteht aus den in der Definition von C festgelegten Schlüsselwörtern und Zeichen.

• Die natürlichen Zahlen in unärer Darstellung bilden die Sprache ℕ_un = {ε,1,11,111,1111,…}.

• Die Sprache count₂ = {aⁿbⁿ | n ∈ ℕ} enthält jeweils n Zeichen a, gefolgt von n Zeichen b. Entsprechend enthält count₃ = {aⁿbⁿcⁿ | n ∈ ℕ} gleich viele aufeinanderfolgende a, b und c.

• Die Palindromsprache pal = {w ∈ {0,1}* | w = wᴿ} enthält genau die Wörter, die ihrer Spiegelung wᴿ entsprechen.

Weitere Beispiele aus dem Artikel sind die Sprache quad_count = {a^(n²) | n ∈ ℕ} mit Wörtern quadratischer Länge, die Dezimalkodierungen der Primzahlen sowie die Morse- oder Thue-Folge. Bei dieser Folge wird der Homomorphismus h_t durch h_t(ε) = ε, h_t(w0) = h_t(w)01 und h_t(w1) = h_t(w)10 definiert. Die ersten Elemente sind 0, 01, 0110, 01101001 und 0110100110010110.

Operationen auf Sprachen

Sind L₁ und L₂ Sprachen über den Alphabeten Σ₁ und Σ₂, können beide als Sprachen über Σ₁ ∪ Σ₂ betrachtet werden. Daher sind auch ihre Vereinigung L₁ ∪ L₂, ihr Durchschnitt L₁ ∩ L₂ und ihre Differenz L₁ ∖ L₂ formale Sprachen.

Die Konkatenation verbindet jeweils ein Wort aus L₁ mit einem Wort aus L₂ durch Hintereinanderschreiben:

L₁ ∘ L₂ = {uv | u ∈ L₁, v ∈ L₂}.

Beispielsweise gilt {a} ∘ {ab} = {aab} und {a,bb} ∘ {aa,b} = {aaa,ab,bbaa,bbb}. Das neutrale Element ist die Sprache {ε}, denn L ∘ {ε} = {ε} ∘ L = L. Die leere Sprache {} ist absorbierend: L ∘ {} = {} ∘ L = {}. Die Konkatenation ist assoziativ, also unabhängig von der Klammerung, aber im Allgemeinen nicht kommutativ; die Reihenfolge der Sprachen kann das Ergebnis verändern. Die Menge aller Sprachen über einem Alphabet bildet mit der Konkatenation und {ε} als neutralem Element ein Monoid.

Die Potenz Lⁿ ist die n-fache Konkatenation einer Sprache mit sich selbst. Rekursiv gilt:

L⁰ = {ε}, Lⁿ⁺¹ = Lⁿ ∘ L für n ∈ ℕ₀.

Zum Beispiel ist {a,b}² = {aa,ab,ba,bb} und {a}⁴ = {aaaa}. Für eine einelementige Sprache L = {w} gilt allgemein {w}ⁿ = {wⁿ}.

Der Kleene-*-Abschluss oder die Kleenesche Hülle einer Sprache enthält alle Potenzen einschließlich der nullten:

L* = ⋃ᵢ∈ℕ₀ Lⁱ.

Der Kleene-+-Abschluss oder die positive Hülle enthält dagegen nur die positiven Potenzen:

L+ = ⋃ᵢ∈ℕ Lⁱ.

Damit enthält L* stets ε, während L+ erst mit L¹ beginnt.

Wichtige Sprachklassen und Regelsysteme

Die Chomsky-Hierarchie ordnet formale Sprachen nach den Grammatiken, die sie erzeugen. Noam Chomsky stellte sie 1956 auf. Sie unterscheidet Typ 0, Typ 1, Typ 2 und Typ 3: rekursiv aufzählbare, kontextsensitive, kontextfreie beziehungsweise reguläre Sprachen.

Daneben gibt es weitere Arten von Regelsystemen:

• In Lindenmayer-Systemen werden Ersetzungen in jedem Schritt an allen Stellen parallel vorgenommen.

• Semi-Thue-Systeme legen Sprachen fest, deren Wörter aus Startwörtern abgeleitet werden.

• Church-Rosser-Systeme beschreiben Sprachen, deren Wörter sich auf ein Terminalwort reduzieren lassen.

• Termersetzungssysteme erzeugen die Menge der Terme, die zu einem Ausgangsterm äquivalent sind.

• Graphgrammatiken verallgemeinern formale Sprachen zu Graphsprachen; Hypergraphgrammatiken erzeugen Hypergraphen als Verallgemeinerungen von Graphen.