Formale Sprache

aus Freepedia, der freien Wissensdatenbank

Formale Sprachen sind ein eigenständiges Wissensgebiet in der Theoretischen Informatik. Im Gegensatz zur Mathematik liegen die Objekte in den formalen Sprachen immer in einer codierten Form vor. So sind die natürlichen Zahlen <math>\mathbb{N}=\{0,1,2,\ldots\}</math> in der Mathematik ein rein gedankliches Gebilde; in der Theoretischen Informatik wird aus ihnen durch die Codierung in das Dezimalsystem eine formale Sprache.

Wenn wir die Wörter einer natürlichen Sprache als Alphabetszeichen ansehen, dann bilden die Sätze der natürlichen Sprache wiederum eine Formale Sprache über dem Alphabet der natürlich sprachlichen Wörter. Allerdings entzieht sich die natürliche Sprache einer vollständigen Definition, die schließlich festlegt, welche Sätze zu der natürlichen Sprache hinzugehören und welche nicht. (Latein und Esperanto mögen hier Ausnahmen bilden.) Grundsätzlich können Gesetze und Mechanismen der formalen Sprachen daher nur für Teilbereiche der natürlichen Sprachen angewandt werden. Siehe dazu Linguistik.

Inhaltsverzeichnis 1 Definitionen 2 Beispiele 3 Weitere Sprechweisen 4 Operationen auf formalen Sprachen 5 Wichtige formale Sprachklassenen 6 Siehe auch 7 Literatur

Definitionen

Eine formale Sprache <math> \mathbf{\mathit{L}} </math> ist eine Menge von Wörtern. Ein Wort einer formalen Sprache ist eine Folge von Zeichen aus einem (in der Regel endlichen) Alphabet <math>\mathbf{\mathit{\Sigma}}</math>. Das Hintereinanderschreiben von Zeichen oder Wörtern heißt Konkatenation. Wenn man diese anzeigen will wird meist <math>\circ</math> gelegentlich auch <math>\cdot</math> benutzt. Stets ist es belanglos, in welcher Reihenfolge die konkateniert wird. Lediglich die Position der Zeichen in der Folge ist von Bedeutung: Somit gilt:

• <math>(u\circ v)\circ w = u\circ(v\circ w) = uvw</math>

Die Konkatenation führt somit zu der algebraischen Struktur eines freien Monoids über dem gegeben Alphabet.

Dabei bezeichnet man das leere Wort - also die leere Folge von Zeichen - meist durch <math>\varepsilon</math>. Weiterhin wird mit Betragsstrichen in der Regel die Längenfunktion beschrieben: Wenn <math>w</math> ein Wort ist, dann ist mit <math>|w|</math> die Länge bezeichnet, das ist die Anzahl der Folgenglieder in <math>w</math>: <math>|\varepsilon|=0</math> und <math>|a|=1</math> für alle Alphabetszeichen <math>a</math> und |wa|=|w|+1 für alle Wörter <math>w</math> und Alphabetszeichen <math>a</math>.

Beispiele

Wir listen hier häufig verwendete formale Sprachen auf:

1. Die Programmiersprache C ist eine Formale Sprache. Die Wörter von C sind die jeweiligen Programme. Das Alphabet von C sind die Schlüsselwörter und Zeichen, die in der Definition von C festgelegt sind.
2. Die natürlichen Zahlen in unärer Darstellung:<math> \mathbb{N}_{un} := \{\varepsilon,1,11,111,1111,\ldots \} </math>
3. <math>count_2 := \{ w\in\{a,b\}^* | \exist n\in\mathbb{N}: w=a^nb^n\}</math>
4. <math>count_3 := \{ w\in\{a,b,c\}^* | \exist n\in\mathbb{N}: w=a^nb^nc^n\}</math>
5. Die Palindrome: <math>pal := \{w \in \{0,1\}^* | w=w^R \}</math>
   wobei <math>w^R</math> das Wort bezeichnet, das <math>w</math> von hinten nach vorne aufgeschrieben gleicht.
6. Die Primzahlen in Dezimalcodierung: <math>prim_{dec} := \{w\in\{0,1,2,3,4,5,6,7,8,9\}^* | \exist n\in\mathbb{N} : n\in </math>PRIM und <math>dec(n)=w \}</math>.
   Hierbei bezeichnet <math>dec : \mathbb{N} \rightarrow \{0,1,2,3,4,5,6,7,8,9\}^*</math> die Codierung der natürlichen Zahlen im Dezimalsystem und PRIM steht für die Menge der Primzahlen.
7. Die Morse- oder Thue-Folge: <math>thue := \{ w \in\{0,1\}^* | \exist n\in\mathbb{N} : w=h^n_t(0) \}</math>.
   Wobei <math>h_t</math> ein Homomorphismus ist, der folgendermaßen definiert ist: <math>h_t(\varepsilon)=\varepsilon</math> und <math>h_t(w0):= h_t(w)01</math>, <math>h_t(w1):= h_t(w)10</math>.
   Somit sind die ersten Elemente der Thue-Folge: 0, 01, 0110, 01101001, 0110100110010110, ...

Weitere Sprechweisen

Ein Wort einer formalen Sprache heißt häufig auch String oder Zeichenkette. Das leere Wort <math>\varepsilon</math> heißt in der Algebra auch neutrales Element.

Operationen auf formalen Sprachen

Die Konkatenation zweier Sprachen <math>\mathbf{\mathit{L_a}}</math> und <math>\mathbf{\mathit{L_b}}</math> ist <math>L_a \circ L_b = \{ uv | u\in L_a, v\in L_b \}</math>. Also alle Wörter, die man bilden kann, indem ein Wort aus <math>\mathbf{\mathit{L_a}}</math> und ein Wort aus <math>\mathbf{\mathit{L_b}}</math> aneinandergereiht werden.

Man kann durch <math>L^{n+1} = L^n \circ L</math> induktiv die Potenz <math>\mathbf{\mathit{L^n}}</math> einer Sprache <math>\mathbf{\mathit{L}}</math> für <math>n \in \mathbb{N} </math> mit <math> \mathbb{N} = \{ 0, 1, 2, \ldots \} </math> definieren, dabei wird <math>\mathbf{\mathit{L^1 = L}}</math> und <math>L^0 = \{ \varepsilon \}</math> definiert (beachte: die Menge, die nur das leere Wort enthält, ist selbst nicht leer!)

Jetzt können wir die Menge aller endlichen Wörter über dem Alphabet <math>\mathbf{\mathit{\Sigma}}</math> hinschreiben: <math>\mathbf{\mathit{L = \Sigma^*}}</math>, wobei <math>M^*=\bigcup_{i\in\mathbb{N}} M^i</math> und wir hier die Symbole <math>\mathbf{\mathit{a}}</math> aus <math>\mathbf{\mathit{\Sigma}}</math> mit den Wörtern <math>\mathbf{\mathit{a}}</math> der Länge 1 identifizieren.

Die Operation <math>\mathbf{\mathit{{~}^{*}}}</math> wird auch als endlicher (oder kleenescher) Abschluss bezeichnet, der Operator selbst als Kleene-Stern (siehe Kleenesche Hülle).

Die Menge dieser Wörter kann endlich oder unendlich sein. Man spricht dann auch von einer endlichen bzw. unendlichen Sprache.

Wichtige formale Sprachklassenen

1. Noam Chomsky hat eine Hierarchie von formalen Grammatiken aufgestellt, die verschiedene Typen von formalen Sprachen erzeugen. Diese ist heute unter dem Namen Chomsky-Hierarchie bekannt. Hier wird unterschieden zwischen Typ 0, Typ 1, Typ 2 und Typ 3: Rekursiv aufzählbare, kontextsensitive, kontextfreie bzw. reguläre Sprachen.
2. Aristid Lindenmayer hat ein Regelsystem vorgeschlagen, in dem Ersetzungsschritte in jedem Schritt an jeder Stelle parallel durchgeführt werden. Diese Systeme heißen L-Systeme.
3. Mit Semi-Thue-Systeme lassen sich Sprachen festlegen, die aus Startwörtern ableitgeleitet werden.
4. Mit Church-Rosser-Systemen werden Sprachen erklärt, deren Wörter sich auf ein Terminalwort reduzieren lassen.
5. Termersetzungssysteme erzeugen die Menge von Termen, die zu einem Ausgangsterm äqivalent sind.
6. Verallgemeinerungen von formalen Sprachen erhalten wir mit Graphgrammatiken mit denen wir Graphsprachen erzeugen können.
7. Hypergraphgrammatiken erzeugen Hypergraphen, eine Verallgemeinerung von Graphen.

Siehe auch

• Lindenmayer-Systeme
  
• Chomsky-Hierarchie
  
• Formale Grammatik
  

Anwendungen siehe in:

• Berechenbarkeitstheorie
  
• Komplexitätstheorie
  
• Kryptographie
  
• Kryptanalyse
  
• Compilerbau
• Programmiersprache

Literatur

• Egon Börger: Berechenbarkeit, Komplexität, Logik. Vieweg, Braunschweig Wiesbaden,
  • Eine dritte Auflage erschien 1995.
  • Englische Ausgabe: Computability, Complexity, Logic. Erschienen in der Reihe: Studies in logic and the foundations of mathematics. North Holland, Amsterdam 1985.

Eine Darstellung der Formalen Sprachen im Kontext der Berechenbarkeitstheorie, Logik und Komplexitätstheorie. Stellt hohe Anforderungen an den Leser, liefert dafür tiefe Einblicke.

• Michael A. Harrison: Introduction to Formal Language Theory. Erschienen in der Reihe: Series in Computer Science, Addison-Wesley, 1978.

Eine sehr ausführliche und viel gelobte Einführung.

• John E. Hopcroft and Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley, 1988.
  • Englisches Original: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.
  • Eine überarbeitete dritte Auflage auf deutsch erschien 1994.

Das englische Original ist das in der Theoretischen Informatik am häufigsten zitierte Buch. Die Beweise sind in der deutschen Übersetzung gelegentlich falsch wiedergegeben. Dieses Buch ist in zahlreiche Sprachen übersetzt worden.

• Grzegorz Rozenberg und Arto Salomaa: The Mathematical Theory of L-Systems. Academic Press, New York, 1980.

Das ausführlichste Buch über L-Systeme.

• Grzegorz Rozenberg und Arto Salomaa (Herausgeber): Handbook of Formal Languages. Volume I-III, Springer, 1997, ISBN 3-540-61486-9.

Eine ausführliche Übersicht über die wichtigsten Gebiete der Formalen Sprachen dargestellt jeweils von aktiv in diesem Gebiet arbeitenden Wissenschaftlern.

• Arto Salomaa: Formale Sprachen. Springer, 1978.
  • Englisches Original: Formal Languages. Academic Press, 1973.
• Ingo Wegener: Theoretische Informatik. Teubner Stuttgart, 1993. ISBN 3-519-02123-4.

In der Darstellung der Formalen Sprachen wird stets die Komplexität der formal-sprachlichen Konstruktionen mitbehandelt. Diese ist sonst nur in der Originalliteratur zu finden.