Formale Sprachen

Die formale Sprache ist eine Art Verallgemeinerung des Sprachbegriffs, den wir aus dem täglichen Leben gewohnt sind.

Grundlegende Konzepte

Zunächst einmal können wir uns die formale Sprache als eine allgemeine Sprache vorstellen, wie z. B. Englisch. Woraus besteht eine solche Sprache? Sie besteht aus Wörtern, die wir dann zu Sätzen zusammensetzen. Wir sind nicht an Sätzen, sondern nur an Wörtern interessiert. Woraus bestehen die Wörter? Aus den Buchstaben des Alphabets. Beginnen wir mit dem Alphabet.

EinAlphabet ist eine beliebige, nicht leere Menge. Die Elemente des Alphabets werden Symbole genannt. Wenn wir über die tschechische Sprache sprechen, dann ist es das klassische tschechische Alphabet, das sowohl Klein- als auch Großbuchstaben enthält, sowie Variationen von Buchstaben mit Haken und Kommas. Wenn wir nicht die tschechische Sprache, sondern z. B. Zahlen beschreiben wollen, würden wir alle zehn Ziffern des Alphabets verwenden. Wir bezeichnen das Alphabet oft mit dem Symbol $\Sigma$.

Unter einem Wort oder auch einer Zeichenkette versteht man eine endliche Folge von Symbolen aus einem Alphabet $\Sigma$. Wenn wir zum Beispiel das Alphabet $\Sigma=\left\{a,b,c,d,e,\dots, z\right\}$ haben, dann ist ein Wort zum Beispiel die Folge "ahoj" oder "doberman", aber nicht "večer" (wir haben kein "č"), "Honza" (wir haben kein "H") oder "dobry den" (wir haben kein Leerzeichen). Unter Wortlänge verstehe ich die Anzahl der Symbole, aus denen ein Wort besteht.

Wortverkettung: Wenn wir zwei Wörter a = a₁a₂… a_n und b = b₁b₂… b_m haben, dann ergibt die Verkettung der Wörter das Wort ab = a₁a₂… a_nb₁b₂… b_m. Beispiel: Die Verkettung der Wörter "hallo" und "Dobermann" ergibt das Wort "hallo Dobermann". Entweder markieren wir die Verkettung mit einem Kreis, z. B. $a\circ b$, oder wir markieren sie gar nicht und schreiben die Wörter einfach hintereinander, ohne ein spezielles Symbol für die Verkettung.

Wir markieren einleeres Wort mit $\varepsilon$, um ein Wort mit der Länge Null zu kennzeichnen. Wenn wir das Wort a = a₁… a_n mit dem leeren Wort $\varepsilon$ verketten, erhalten wir das Wort a zurück. Das heißt, $a\circ\varepsilon=a$.

Der Abschluss des Alphabets $\Sigma$ ist die Menge aller Wörter, die wir aus dem Alphabet $\Sigma$ bilden können, einschließlich des leeren Wortes. Wir bezeichnen die Schließung mit $\Sigma^\ast$. Wenn wir das binäre Alphabet $\Sigma=\left\{0,1\right\}$ haben, dann

$$ \Sigma^\ast=\left\{\varepsilon,0{,}1,01{,}10,11{,}011,101{,}110,\dots\right\} $$

Manchmal verwenden wir auch einen positiven Abschluss des Alphabets, der wiederum alle Wörter umfasst, die wir aus dem Alphabet zusammensetzen können, mit Ausnahme des leeren Wortes. Wir bezeichnen den positiven Abschluss mit $\Sigma^+$ und die Gültigkeit mit $\Sigma^+=\Sigma^\ast\setminus\left\{\varepsilon\right\}$.

Beispiele für Alphabete

• Kehren wir zum tschechischen Beispiel zurück. Jedes tschechische Wort befindet sich in der Kappe eines Alphabets, das Groß- und Kleinbuchstaben und akzentuierte Varianten (und vielleicht einen Bindestrich "-") enthält. Wenn wir diesem Alphabet ein Leerzeichen und Satzzeichen (Komma, Punkt, Ausrufezeichen, Fragezeichen, ...) hinzufügen, erhalten wir alle Sätze, die wir in der tschechischen Sprache bilden können. Natürlich sind darunter auch Sätze wie "sadflsf kasdf kagrjewichiarzcáýker kf fkjbsjbgvbadfgsa!!!:??: ::::?:::sdf", aber diese sind immer noch aussagekräftiger als die Reden von Miloš Zeman.

• Wenn unser Alphabet alle Ziffern enthält $\Sigma=\left\{0, 1, \dots, 9\right\}$, dann werden alle natürlichen Zahlen in der Mütze sein - und noch einige mehr. Es wird auch Zahlen geben, die mit Null beginnen, z. B. 00054, oder die Null selbst, und es wird ein leeres Wort geben, das natürlich keine Zahl ist.

• Das Alphabet darf nicht leer sein, so dass das kleinste Alphabet mindestens ein Symbol enthält. Für das Alphabet $\Sigma=\left\{!\right\}$ erhalten wir beispielsweise die Schließung $\Sigma^\ast=\left\{\varepsilon, !, !!, !!!, !!!!, \dots\right\}$, d. h. die Menge der Wörter, und für jedes n∈ℕ₀ in der Schließung gibt es ein Wort, das n Ausrufezeichen hat, und es gibt kein anderes Wort in der Schließung.

• Nehmen wir $\Sigma=\left\{qw,c\right\}$. Dies ist ein sehr seltsames Alphabet, weil es das Wort qw enthält. Diese Schreibweise wird normalerweise nicht verwendet, weil sie verwirrend und seltsam ist, aber wir können sie uns vorstellen, indem wir die Buchstaben "q" und "w" zusammenkleben, so dass sie ein Zeichen bilden. Dann können wir das Wort "qw" als das Symbol "qw" sehen. Wenn wir aus diesem Symbol das Wort "qwcqw" machen, dann hätte dieses Wort eine Länge von drei - es bestünde aus den Symbolen "qw", "c" und "qw". Solche Alphabetfälle kommen nicht sehr häufig vor, aber es gibt Situationen, in denen wir solche aus mehreren Symbolen bestehenden Symbole verwenden müssen.

Formale Sprache

Die(formale) Sprache über dem Alphabet $\Sigma$ ist eine beliebige Teilmenge von $\Sigma^\ast$. So gilt $L\subseteq\Sigma^\ast$ für die Sprache L über dem Alphabet $\Sigma$. Sprachbeispiele:

• Im vorigen Abschnitt haben wir das Ziffernalphabet $\Sigma=\left\{0, 1, \dots, 9\right\}$ definiert. Der Abschluss sind alle Wörter, die nur aus Ziffern bestehen. Wenn wir die Regel hinzufügen, dass ein Wort nicht mit Null beginnen und ein Wort nicht leer sein darf, erhalten wir die Menge der natürlichen Zahlen ℕ. Die Beziehung $\mathbb{N}\subseteq\Sigma^\ast$ gilt, also ist ℕ eine Sprache über dem Alphabet $\Sigma$.

• Wir können das Minuszeichen "-" zu der vorherigen Menge von Ziffern hinzufügen, also $\Sigma=\left\{0, 1, \dots, 9, -\right\}$. Der Abschluss sind alle Wörter, die aus Ziffern oder einem Minuszeichen bestehen. Das bedeutet jedoch, dass Wörter wie "12-84-", "1-5-8" oder "-" auch in der Schließung enthalten sind. Wir erstellen die ganzzahlige Sprache ℤ, indem wir drei Regeln hinzufügen:

  • Das Minuszeichen kommt im Wort gar nicht oder am Anfang des Wortes vor.
  • Die erste Ziffer eines Wortes darf nicht Null sein, außer bei dem Wort "0".
  • Jedes Wort muss mindestens eine Ziffer enthalten.

  Diese Menge beschreibt die Menge der ganzen Zahlen und ist eine Teilmenge der Menge $\Sigma^\ast$ - sie ist also die Sprache über dem Alphabet $\Sigma$.

• Es sei $\Sigma=\left\{0,1\right\}$. Der Abschluss sind also alle Wörter, die aus Nullen und Einsen bestehen. Die Sprache L über diesem Alphabet kann z.B. als die Menge aller Wörter definiert werden, 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 (was aus Word kommt).

• Wir bleiben beim binären Alphabet $\Sigma=\left\{0,1\right\}$. Jede Zeichenkette (die normalen Zeichen auf Ihrer Tastatur) kann in binäre Zeichen umgewandelt werden, d. h. in Nullen und Einsen, und wieder zurück, z. B. mit Hilfe einer ASCII-Tabelle (oder genauer gesagt, eine ASCII-Tabelle wandelt Zeichen in Zahlen um, und Zahlen im Dezimalsystem können in Zahlen im Binärsystem umgewandelt werden). Wir können also die Sprache aller Wörter definieren, die einer gültigen E-Mail entsprechen, und es wird immer noch eine Sprache über das binäre Alphabet sein.

Verkettung von Sprachen: Wir können auch Alphabete verketten. Die Definition ist ähnlich wie beim kartesischen Produkt von Mengen. Wir haben zwei Sprachen L₁ und L₂. Die Verkettung dieser Sprachen $L_1\circ L_2$ ergibt eine neue Sprache, die wir wie folgt definieren:

$$ L_1\circ L_2 = \left\{w_1\circ w_2,|,w_1\in L_1, w_2\in L_2\right\} $$

Das heißt, wir nehmen alle Wörter der Sprache L₁ und verketten sie mit allen Wörtern der Sprache L₂. Beispiel.

\begin{eqnarray} L_1&=&&\left\{0,1\right\}\ L_2&=&\left\{a,b,ahoj\right\}\\ \end{eqnarray}

Dann:

\begin{eqnarray} L_1\circ L_2 &=& \left\{0a, 0b, 0ahoj, 1a, 1b, 1ahoj\right\}\ L_2\circ L_1 &=& \left\{a0, a1, b0, b1, ahoj0, ahoj1\right\}\ L_1\circ L_1 &=& \left\{00, 01, 10, 11\right\} \end{eqnarray}

Bisher haben wir zur Beschreibung von Sprachen die gewöhnliche Sprache verwendet, indem wir einfach verbal beschrieben haben, wie die Sprache aussehen sollte. Dies ist jedoch sehr unpraktisch, so dass eine formalere Methode zur Definition einer Sprache eingeführt wird. Die erste davon ist die Grammatik.