Einleitung

In diesem Kurs werden Sie erfahren was formale Sprachen und Grammatiken sind, wie diese mit Automaten (DEA/NEA/PDA) zusammenhängen und was die Chomsky-Hierarchie damit zu tun hat.

Formale Sprachen

Wie auch unsere gesprochenen Sprachen sind "Formale Sprachen" aus mehreren Zeichen (Zeichenketten) aufgebaut. Anders als bei unseren wirklichen Sprech-Sprachen allerdings ist die Anwendung von formalen Sprachen nicht vorrangig die Kommunikation. Statdessen können mit formalen Sprachen beispielsweise Syntaxstrukturen einer Programmiersprache beschrieben werden. Bei Java beispielsweise folgt auf jede Anweisung ein Semikolon. Um jetzt zu überprüfen, ob ein Java-Programmcode diese Regel verletzt, können wir eine Sprache definieren und dann testen, ob das Programm ein gültiger Ausdruck (auch Wort genannt) dieser Sprache ist.

Die formale Definition

Eine Formale Sprache besitzt ein Alphabet \( \Sigma \) (Sigma), welche die Zeichen festlegt aus denen ein Wort (Ausdruck) der Sprache bestehen kann.
Als die Kleenesche Hülle des Alphabetes \( \Sigma \) (Notation: \( \Sigma^* \)) bezeichnet man alle Ausdrücke, die man irgendwie aus dem Alphabet erzeugen könnte. Dazu gehört auch das leere Wort, was oft mit \(\varepsilon\) (Epsilon) bezeichnet wird.

Beispiel: \( \Sigma \) sei \(\{1\}\) (Das Alphabet besteht nur aus "1")
Wenn es sonst keine Einschränkungen der Sprache gibt ist die Menge der Wörter von der Sprache gleich der Kleenesche Hülle des Alphabets.
Also ist in diesem Beispiel die Menge der Wörter: \(W = \{\varepsilon,1,11,111,1111,\dots\}\)


Die Kleenesche Hülle des Alphabetes ist aber nicht immer gleich der Menge der erlaubten Wörtern. Eine Sprache kann mit weiteren Einschränkungen definiert werden, z.B. welcher Teil des Alphabetes auf welchen anderen folgen darf.
Beispiel: \( \Sigma \) sei \(\{1,2\}\), Und eine \(2\) soll nur auf eine \(1\) folgen dürfen, also wäre z.B. \(122\) nicht erlaubt.
In diesem Beispiel ist die Menge der Wörter: \(W = \{\varepsilon,1,11,12,121,1211,1212,\dots\}\)

Eine Sprache L hat ein Alphabet \( \Sigma \), welches die Menge der Zeichen beschreibt. Die Kleensche Hülle des Alphabets, \( \Sigma^* \), ist die Menge aller Wörter die aus dem Alphabet gebildet werden können. Da die Sprache L noch weitere Bedingungen an Wörter stellen kann, ist die Menge der akzeptierten Wörter eine Teilmenge von \( \Sigma^* \).

Leicht fällt auf, dass eine wörtliche Formulierung der Einschränkungen und Regeln einer formalen Sprache oft uneindeutig sind oder unnötig komplex. Aus diesem Grund beschäftigt sich das nächste Kapitel mit Grammatiken, die eine formale Sprache und ihre Regeln beschreiben.
Test: Sei \( \Sigma = \{a,b,c\} \) das Alphabet einer Sprache \(L\). Welche Wörter sind in \( \Sigma^* \) enthalten?





Formale Grammatiken

Um Formale Sprachen besser zu definieren beschreibt man sie mit Formalen Grammatiken. Eine Grammatik lässt sich wie eine Anleitung verstehen, Wörter einer Formalen Sprache zu konstruieren. Dabei kann eine Sprache durch verschiedenen Grammatiken beschrieben werden. Man nennt diese Grammatiken dann äquivalent zueinander. Die Sprache, die von einer Grammatik \((G)\) erzeugt wird, wird mit \(L(G)\) bezeichnet.
Für das Erzeugen der Wörter mit einer Grammatik verwendet man bestimmte sogenannte Produktionsregeln. Man beginnt mit einem Startsymbol \((S)\) und nutzt dann die Produktionsregeln um aus dem \(S\) andere Symbole zu entwickeln. Die Menge der Symbole bezeichnet man meist als \(V\).
\(V\) wird dabei unterschieden in: Terminale, welche in dem Alphabet der durch die Grammatik beschriebenen Sprache enthalten sind und Nonterminale, also "Nicht-Terminalen", welche im letzendlich erzeugtem Wort nicht vorkommen dürfen und nur für die Übergänge benötigt werden. Nonterminale werden meist mit Großbuchstaben notiert, während für Terminale in den meisten Formalen Sprachen und Grammatiken Kleinbuchstaben oder Zahlen verwendet werden.

\(V\) ist die Menge aller Symbole einer Grammatik. Die Teilmenge davon, die im letzendlichen Wort vertreten sein darf, bezeichnet man als die Menge der Terminalen \((T)\). Also ist \(T \subset V\). Die Menge der Terminalen \(T\) einer Grammatik \(G\) entspricht dem Alphabet \( \Sigma \) der Sprache \(L(G)\). Der Rest der Symbole bildet die Menge der Nonterminalen \((N = V \setminus T)\). Nonterminale dürfen nicht im fertig gebildeten Wort enhalten sein und werden nur für Übergangsregeln benutzt.

Die formale Definition

Formale Grammatiken beschreiben Formale Sprachen und sind Quadrupel aus:
  1. Endlich vielen Terminalen \((T\), oft auch: \( \Sigma )\)
  2. Endlich vielen Nonterminalen \((N)\)
  3. Endlich vielen Produktionsregeln \((P)\)
  4. Einem Startzeichen \((S \in N)\)
Beispiel: Folgende Grammatik G sei gegeben: \begin{align*} G = &\{ \\ &T = \{a,b\}, \\ &N = \{S,A,B\}, \\ &S = S, \\ &P = \{ S \rightarrow aB, B \rightarrow bA, A \rightarrow a|aB \} \\ &\} \\ \end{align*} Folgende Informationen kann man entnehmen: Die Menge der Terminalen ist \({a,b}\), genauso wie das Alphabet der Sprache \(L(G)\). Die Nonterminale beinhalten das Startsymbol \(S\) und zusätzlich noch \({A,B}\).
Die Produktionsregeln lesen sich jetzt wie folgt: Das Startsymbol \(S\) können wir die Folge \(aB\) umwandeln. Das Nonterminal \(B\) in \(bA\) und \(A\) entweder nur in \(a\) oder in \(aB\).

Bilden wir zur Probe mal ein Wort aus \(G\):
Wir beginnen mit unserem Startsymbol \(S\) und wandeln dies in \(aB\) um \(S \rightarrow aB\).
Aus dem \(B\) machen wir mit der zweiten Regel \(bA\) \((S \rightarrow aB \rightarrow abA)\).
Nun können wir das Wort mit der Regel \(A\rightarrow a\) fertigstellen \( (S \rightarrow aB \rightarrow abA \rightarrow aba)\). Weil keine Nonterminale mehr im Wort vorhanden sind und wir nur die Produktionsregeln benutzt haben ist das Wort \(aba\) ein gültiges Wort von \(L(G)\).

Test: Sei \begin{align*} G = &\{ \\ &T =\{a,b,c\}, \\ &N =\{S,A,B\}, \\ &S =S, \\ &P = \{ S \rightarrow aA, A \rightarrow bB, B \rightarrow cC|c, C \rightarrow aA\} \\ &\} \\ \end{align*} Bilde ein gültiges Wort der Sprache L(G).

Chomsky-Hierarchie

soon