Formale Sprache

Die Artikel Formale Sprache, Formales System, Formales System (Logik) und Kalkül überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Die Diskussion über diese Überschneidungen findet hier statt. Bitte äußere dich dort, bevor du den Baustein entfernst. Gratisaktie 14:02, 17. Sep 2006 (CEST); Lückenlos 00:59, 9. Jul. 2007 (CEST)

Eine formale Sprache ist eine Menge von Wörtern, welche aus einem gegebenen Alphabet gebildet werden können (einschließlich des leeren Wortes). Sie ist definiert als eine Teilmenge der Kleeneschen Hülle über dieses gegebene Alphabet. Formale Sprachen werden häufig mit Hilfe einer formalen Grammatik beschrieben. Die Theorie der Formalen Sprachen ist ein eigenständiges Wissensgebiet in der Theoretischen Informatik.

Wenn wir die Wörter einer natürlichen Sprache als Alphabetszeichen ansehen, dann bilden die Sätze der natürlichen Sprache eine Formale Sprache über dem Alphabet der natürlichsprachlichen 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. Grundsätzlich können Gesetze und Mechanismen der formalen Sprachen daher nur auf Teilbereiche der natürlichen Sprachen angewandt werden. Siehe dazu Linguistik.

Die Menge der Wörter einer formalen Sprache kann endlich oder unendlich sein, wobei dann auch der Begriff einer endlichen bzw. unendlichen (formalen) Sprache verwendet wird. Wenn die formale Sprache gleich der leeren Menge ist, spricht man auch von der leeren Sprache. Man beachte hier, dass die Sprache, welche nur das leere Wort enthält, selbst nicht leer, sondern einelementig ist.

Inhaltsverzeichnis

1 Beispiele
2 Operationen auf formalen Sprachen
- 2.1 Konkatenation
- 2.2 Potenz
3 Wichtige formale Sprachklassen
4 Siehe auch
5 Literatur

Beispiele

Wir listen hier häufig verwendete formale Sprachen auf:

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.
Die natürlichen Zahlen in unärer Darstellung: $\mathbb{N}_{\rm un} := \{\varepsilon,1,11,111,1111,\ldots \}$
Die unäre Sprache ist die Sprache, die nur Wörter quadratischer Länge enthält: ${\rm quad\_count} := \{ w\in\{a\}^* | \exist n\in\mathbb{N}: w={(a^n)}^2\}$
${\rm count}_2 := \{ w\in\{a,b\}^* | \exist n\in\mathbb{N}: w=a^nb^n\}$
${\rm count}_3 := \{ w\in\{a,b,c\}^* | \exist n\in\mathbb{N}: w=a^nb^nc^n\}$
Die Sprache aller Palindrome: ${\rm pal} := \{w \in \{0,1\}^* | w=w^R \}$
wobei $w R$ die Spiegelung des Wortes $w$ ist.
Die Dezimalkodierung der Primzahlen: ${\rm prim}_{\rm dec} := \{w\in\{0,1,2,3,4,5,6,7,8,9\}^* | \exist n\in\mathbb{N} : n\in {\rm PRIM} \and {\rm dec}(n)=w \}$ .
Hierbei bezeichnet ${\rm dec} : \mathbb{N} \rightarrow \{0,1,2,3,4,5,6,7,8,9\}^*$ die Kodierung der natürlichen Zahlen im Dezimalsystem und PRIM steht für die Menge der Primzahlen.
Die Morse- oder Thue-Folge: ${\rm thue} := \{ w \in\{0,1\}^* | \exist n\in\mathbb{N} : w=h^n_t(0) \}$ .
Wobei $h t$ ein Homomorphismus ist, der folgendermaßen definiert ist: $h_t(\varepsilon)=\varepsilon$ und $h t (w 0): = h t (w)01$ , $h t (w 1): = h t (w)10$ .
Somit sind die ersten Elemente der Thue-Folge: 0, 01, 0110, 01101001, 0110100110010110, ...

Operationen auf formalen Sprachen

Konkatenation

Die Konkatenation zweier Sprachen $L 1$ und $L 2$ ist die Sprache der Wörter, welche sich aus der Konkatenation (Verkettung) aller Wörter der ersten mit allen Wörtern der zweiten Sprache ergibt:

$L_1 \circ L_2 := \{ uv | u\in L_1, v\in L_2 \}$ .

So sind zum Beispiel die Konkatenationen von verschiedenen Sprachen über dem Alphabet $\Sigma = \lbrace a ,\, b \rbrace$ :

$\lbrace a \rbrace \circ \lbrace ab \rbrace = \lbrace aab \rbrace$

$\lbrace a ,\, bb \rbrace \circ \lbrace aa ,\, b \rbrace = \lbrace aaa ,\, ab ,\, bbaa ,\, bbb \rbrace$

$\lbrace abb ,\, bab \rbrace \circ \lbrace \epsilon ,\, aab ,\, bb \rbrace = \lbrace abb ,\, bab ,\, abbaab ,\, babaab ,\, abbbb ,\, babbb \rbrace$

Das neutrale Element der Konkatenation ist die Sprache, welches nur das leere Wort enthält. So gilt für jede beliebige Sprache $L$ :

$L \circ \lbrace \epsilon \rbrace = \lbrace \epsilon \rbrace \circ L = L$

Die Konkatenation von Sprachen ist wie die Konkatenation von Wörtern assoziativ, aber nicht kommutativ. So ist zum Beispiel:

$(\lbrace a ,\, bab \rbrace \,\circ\, \lbrace a ,\, b \rbrace) \,\circ\, \lbrace ab \rbrace = \lbrace a ,\, bab \rbrace \,\circ\, (\lbrace a ,\, b \rbrace \,\circ\, \lbrace ab \rbrace) = \lbrace aaab ,\, abab ,\, babaab ,\, babbab \rbrace$

aber:

$\lbrace a ,\, bab \rbrace \,\circ\, \lbrace a ,\, b \rbrace = \lbrace aa ,\, ab ,\, baba ,\, babb \rbrace \not= \lbrace aa ,\, abab ,\, ba ,\, bbab \rbrace = \lbrace a ,\, b \rbrace \,\circ\, \lbrace a ,\, bab \rbrace$

Potenz

Die Potenz $L n$ einer Sprache ist die n-fache Konkatenation dieser Sprache mit sich selbst. Sie ist rekursiv definiert mit:

$L^0 := \{\varepsilon\}$

$L^{n+1} := L^n \circ L$ (für $n \in \mathbb{N}_0$ )

So sind zum Beispiel:

$\lbrace aa ,\, abab ,\, bbab ,\, ba \rbrace^0 = \lbrace \epsilon \rbrace$

$\lbrace a ,\, b \rbrace^2 = \lbrace a ,\, b \rbrace^1 \,\circ\, \lbrace a ,\, b \rbrace = (\lbrace a ,\, b \rbrace^0 \,\circ\, \lbrace a ,\, b \rbrace) \,\circ\, \lbrace a ,\, b \rbrace = (\lbrace \epsilon \rbrace \,\circ\, \lbrace a ,\, b \rbrace) \,\circ\, \lbrace a ,\, b \rbrace = \lbrace aa ,\, ab ,\, ba ,\, bb \rbrace$

$\lbrace a \rbrace^4 = \lbrace a \rbrace \,\circ\, \lbrace a \rbrace \,\circ\, \lbrace a \rbrace \,\circ\, \lbrace a \rbrace = \lbrace aaaa \rbrace$

Im Speziellen gilt für jede einelementige, formale Sprache $L = {w}$ (mit $w \in \Sigma^\ast$ ) und jedes $n \in \mathbb{N}_0$ :

L n = {w} n = {w n}

Wichtige formale Sprachklassen

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.
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.
Mit Semi-Thue-Systemen lassen sich Sprachen festlegen, die aus Startwörtern abgeleitet werden.
Mit Church-Rosser-Systemen werden Sprachen erklärt, deren Wörter sich auf ein Terminalwort reduzieren lassen.
Termersetzungssysteme erzeugen die Menge von Termen, die zu einem Ausgangsterm äquivalent sind.
Verallgemeinerungen von formalen Sprachen erhalten wir mit Graphgrammatiken mit denen wir Graphsprachen erzeugen können.
Hypergraphgrammatiken erzeugen Hypergraphen, eine Verallgemeinerung von Graphen.

Siehe auch

Anwendungen siehe in:

Literatur

Lars Peter Georgie: 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.

U. Hedtstück: Einführung in die Theoretische Informatik - Formale Sprachen und Automatentheorie. Oldenbourg Verlag, München 2000, ISBN 3-486-25515-0

Quelle:

Artikel Formale Sprache aus der freien Enzyklopädie Wikipedia mit dieser Versionsgeschichte

Lizenz:

GFDL

Kategorien:

Lexikalischer Artikel

Ähnliche Einträge in anderen Lexika

Adelung-1793: Sprache, die

Brockhaus-1809: Die Sprache

Brockhaus-1837: Römische Sprache und Literatur · Spanische Sprache, Literatur und Kunst · Sprache · Griechische Sprache und Literatur · Hebräische Sprache und Literatur · Niederländische Kunst, Literatur, Sprache und Wissenschaft