Formale Sprachen

Eine formale Sprache ist eine Verallgemeinerung des Begriffs Sprache, den wir aus dem Alltag kennen.

Grundbegriffe

Eine formale Sprache kannst du dir zunächst als gewöhnliche Sprache vorstellen, zum Beispiel Deutsch. Woraus besteht so eine Sprache? Sie besteht aus Wörtern, die wir weiter zu Sätzen verbinden. Die Sätze interessieren uns nicht, uns interessieren nur die Wörter. Woraus bestehen die Wörter? Aus Buchstaben des Alphabets. Mit dem Alphabet fangen wir also an.

Ein Alphabet ist eine beliebige nichtleere Menge. Die Elemente des Alphabets nennen wir Symbole. Geht es um Deutsch, ist es das klassische deutsche Alphabet mit Klein- und Großbuchstaben sowie den Umlauten und dem ß. Wollten wir nicht Deutsch beschreiben, sondern zum Beispiel Zahlen, hätten wir im Alphabet alle zehn Ziffern. Das Alphabet bezeichnen wir oft mit dem Symbol Σ.

Unter einem Wort, oder auch einer Zeichenkette, verstehen wir eine endliche Folge von Symbolen aus einem Alphabet Σ. Haben wir zum Beispiel das Alphabet Σ= {a; b; c; d; e; …; z}, dann ist die Folge „hallo“ oder „dackel“ ein Wort, nicht aber „schön“ (der Buchstabe „ö“ fehlt), „Hans“ (der Buchstabe „H“ fehlt) oder „guten tag“ (das Leerzeichen fehlt). Unter der Länge eines Wortes verstehen wir die Anzahl der Symbole, aus denen das Wort besteht.

Konkatenation von Wörtern: Haben wir zwei Wörter a = a₁a₂… a_n und b = b₁b₂… b_m, entsteht durch die Konkatenation der Wörter das Wort ab = a₁a₂… a_nb₁b₂… b_m. Beispiel: Durch die Konkatenation der Wörter „hallo“ und „dackel“ entsteht das Wort „hallodackel“. Die Konkatenation bezeichnen wir entweder mit einem Kringel, also a ∘ b, oder gar nicht, und wir schreiben die Wörter einfach ohne besonderes Symbol hintereinander.

Das leere Wort bezeichnen wir mit ε, es ist das Wort mit der Länge null. Verketten wir ein Wort a = a₁… a_n mit dem leeren Wort ε, erhalten wir wieder das Wort a. Es gilt also a ∘ ε = a.

Die Kleene-Hülle des Alphabets Σ ist die Menge aller Wörter, die wir aus dem Alphabet Σ bilden können, einschließlich des leeren Wortes. Die Hülle bezeichnen wir mit Σ^∗. Haben wir das binäre Alphabet Σ= {0; 1}, gilt

$${\mathrm{\Sigma }}^{\ast }=\{\epsilon ;0;1;00;01;10;11;000;001;\dots \}$$

Manchmal verwenden wir noch die positive Hülle des Alphabets, das sind wieder alle Wörter, die wir aus dem Alphabet zusammensetzen können, außer dem leeren Wort. Die positive Hülle bezeichnen wir mit Σ⁺ und es gilt Σ⁺ = Σ^∗ ∖ {ε}.

Beispiele für Alphabete

• Kehren wir zum Beispiel mit der deutschen Sprache zurück. Jedes deutsche Wort finden wir in der Hülle des Alphabets, das Klein- und Großbuchstaben und die Umlaute und das ß enthält (plus vielleicht noch den Bindestrich „-“). Fügen wir zu diesem Alphabet noch das Leerzeichen und die Satzzeichen (Komma, Punkt, Ausrufezeichen, Fragezeichen, …) hinzu, erhalten wir durch die Hülle alle Sätze, die wir in der deutschen Sprache bilden können. Natürlich gehören zu dieser Hülle auch Sätze wie „sadflsf kasdf kagrjewiäöüßker kf fkjbsjbgvbadfgsa!!!:??: ::!?:?:sdf“, die aber immer noch sinnvoller sind als so manche Politikerrede.

• Wenn unser Alphabet alle Ziffern enthält, Σ= {0; 1; …; 9}, dann liegen in der Hülle alle natürlichen Zahlen – und noch einige mehr. Es sind dort nämlich auch Zahlen, die mit einer Null beginnen, z. B. 00054, oder die Null allein, und außerdem das leere Wort, das natürlich keine Zahl ist.

• Das Alphabet muss nichtleer sein, das kleinste Alphabet hat also mindestens ein Symbol. Für das Alphabet Σ= {!} erhielten wir zum Beispiel die Hülle Σ^∗ = {ε; !; !!; !!!; !!!!; …}, also eine Menge von Wörtern, wobei es für jedes n ∈ ℕ₀ in der Hülle ein Wort mit n Ausrufezeichen gibt und kein anderes Wort in der Hülle liegt.

• Es sei Σ= {qw; c}. Das ist ein sehr merkwürdiges Alphabet, denn es enthält das Wort qw. Diese Schreibweise wird normalerweise nicht verwendet, weil sie verwirrend und seltsam ist, aber du kannst dir vorstellen, dass wir die Buchstaben „q“ und „w“ so zusammenkleben, dass sie ein einziges Zeichen bilden. Dann können wir das Wort „qw“ als Symbol „qw“ sehen. Bilden wir aus diesem Symbol das Wort „qwcqw“, hätte dieses Wort die Länge drei – es wäre aus den Symbolen „qw“, „c“ und „qw“ zusammengesetzt. Solchen Alphabeten begegnen wir nicht sehr oft, aber es gibt Situationen, in denen wir solche aus mehreren Symbolen bestehenden Symbole brauchen.

Formale Sprache

Eine (formale) Sprache über dem Alphabet Σ ist eine beliebige Teilmenge von Σ^∗. Für eine Sprache L über dem Alphabet Σ gilt also L ⊆ Σ^∗. Beispiele für Sprachen:

• Im vorigen Abschnitt haben wir das Alphabet der Ziffern Σ= {0; 1; …; 9} definiert. Die Hülle besteht aus allen Wörtern, die nur aus Ziffern gebildet werden. Fügen wir die Regel hinzu, dass das Wort nicht mit einer Null beginnen und nicht leer sein darf, erhalten wir die Menge der natürlichen Zahlen ℕ. Es gilt ℕ ⊆ Σ^∗, also ist ℕ eine Sprache über dem Alphabet Σ.

• Zur vorigen Menge der Ziffern können wir noch das Minuszeichen „-“ hinzufügen, also Σ= {0; 1; …; 9; −}. Die Hülle besteht aus allen Wörtern, die aus Ziffern oder dem Minuszeichen zusammengesetzt sind. Das bedeutet aber, dass in der Hülle auch Wörter wie „12-84-“, „1-5-8“ oder „-“ liegen. Die Sprache der ganzen Zahlen ℤ erzeugen wir, indem wir drei Regeln hinzufügen:

  • Das Minuszeichen kommt im Wort gar nicht vor oder steht am Anfang des Wortes.
  • Die erste Ziffer im Wort darf keine Null sein, außer beim Wort „0“.
  • Jedes Wort muss mindestens eine Ziffer enthalten.

  Diese Menge beschreibt die Menge der ganzen Zahlen und ist eine Teilmenge der Menge Σ^∗ – es ist also eine Sprache über dem Alphabet Σ.

• Es sei Σ= {0; 1}. Die Hülle besteht also aus allen Wörtern, die aus Nullen und Einsen zusammengesetzt sind. Eine Sprache L über diesem Alphabet können wir z. B. als die Menge aller Wörter definieren, die genau drei Einsen haben. Wir können auch kreativer sein und sagen, dass die Sprache L die Menge aller Wörter ist, die ein gültiges docx-Dateiformat darstellen (das, was aus Word herauskommt).

• Bleiben wir beim binären Alphabet Σ= {0; 1}. Jede Zeichenkette (gewöhnlicher Zeichen, die du auf der Tastatur hast) lässt sich zum Beispiel mithilfe der ASCII-Tabelle in die binäre Form, also in Nullen und Einsen, und wieder zurück umwandeln (oder genauer – die ASCII-Tabelle wandelt Zeichen in Zahlen um und Zahlen aus dem Dezimalsystem lassen sich in Zahlen im Binärsystem umrechnen). So können wir die Sprache aller Wörter definieren, die einer gültigen E-Mail-Adresse entsprechen, und es bleibt eine Sprache über dem binären Alphabet.

Konkatenation von Sprachen: Konkatenieren können wir auch Sprachen. Die Definition ist ähnlich wie beim kartesischen Produkt von Mengen. Es seien zwei Sprachen L₁ und L₂ gegeben. Durch ihre Konkatenation L₁ ∘ L₂ erhalten wir eine neue Sprache, die wir so definieren:

$$L_1\circ L_2=\{w_1\circ w_2\mid w_1\in L_1,w_2\in L_2\}$$

Wir nehmen also alle Wörter aus der Sprache L₁ und konkatenieren sie mit allen Wörtern aus der Sprache L₂. Beispiel: Es seien

$$\begin{array}{rcl}{L}_1& =& \{0;1\}\\ L_2& =& \{a;b;hallo\}\end{array}$$

Dann gilt:

$$\begin{array}{rcl}{L}_1\circ L_2& =& \{0a;0b;0hallo;1a;1b;1hallo\}\\ L_2\circ L_1& =& \{a0;a1;b0;b1;hallo0;hallo1\}\\ L_1\circ L_1& =& \{00;01;10;11\}\end{array}$$

Bisher haben wir zur Beschreibung von Sprachen die gewöhnliche Sprache benutzt, wir haben also einfach in Worten beschrieben, wie die Sprache aussehen soll. Das ist aber sehr unpraktisch, deshalb führt man eine formalere Art ein, eine Sprache zu definieren. Die erste davon ist die Grammatik.