Formale Sprache

Formale Sprache

Eine formale Sprache ist eine bestimmte Menge von Zeichenketten, die aus einem Zeichenvorrat zusammengesetzt werden können. Anwendung finden formale Sprachen in der Linguistik, der Logik und der theoretischen Informatik.

Formale Sprachen eignen sich zur mathematisch präzisen Beschreibung im Umgang mit Zeichenketten. So können zum Beispiel Datenformate oder ganze Programmiersprachen spezifiziert werden. Zusammen mit einer formalen Semantik erhalten die definierten Zeichenketten eine mathematische Bedeutung. Bei einer Programmiersprache kann damit einer Programmieranweisung (als Teil der formalen Sprache) ein eindeutiges Maschinenverhalten (als Teil der Semantik) zugeordnet werden.

Aufbauend auf formalen Sprachen können aber auch Logikkalküle definiert werden, mit denen man mathematische Schlüsse ziehen kann. In Verbindung mit formal definierten Programmiersprachen können Kalküle helfen, Programme auf ihre Korrektheit zu überprüfen.

Inhaltsverzeichnis

Definition

Eine formale Sprache L über einem Alphabet Σ ist eine Teilmenge der Kleeneschen Hülle des Alphabets: L \subseteq \Sigma^*.

Die aus einem gegebenen Alphabet Σ schlechthin bildbaren Worte sind alle Worte mit endlicher Länge (von 0 oder größer), deren jeder einzelne Buchstabe Element von Σ ist. Diese größtmögliche Wortmenge zum Alphabet Σ nennt man die Kleenesche Hülle des Alphabetes Σ, formal kurz Σ * . Eine formale Sprache über einem Alphabet Σ ist also mathematisch gesehen eine bestimmte Teilmenge der Kleeneschen Hülle ihres Alphabets.

Formale Sprachen können leer, endlich oder unendlich sein, maximal können sie die gesamte Kleenesche Hülle ihres Alphabetes umfassen. Sie können über eine mathematische Bedingung an ihre Worte definiert sein: „Die Sprache … ist die Menge aller Worte, für die gilt … ”.

Die in der theoretischen Informatik auftretenden Sprachen sind jedoch meistens spezieller durch ein bestimmtes Ersetzungsverfahren definiert, von denen es verschiedene Typen gibt: Semi-Thue-Systeme, Chomsky-Grammatiken, Lindenmeyer-Systeme u.a. Bei solchen Ersetzungsverfahren geht man etwa von einer spezifischen Start-Zeichenkette aus, die man durch rekursive Anwendung eines bestimmten Typs von Textsubstitutionen schrittweise zu Wortgebilden überführt, von denen dann ein bestimmter Teil als Worte der mit dem Erzeugungsverfahren erzeugten Sprache gelten. Man redet hier auch von generativen Grammatiken, weil die Worte einer Sprache über solche Textsubstitutionen schrittweise erzeugt werden. Umgekehrt kann man Sprachen auch definieren als die Menge aller Worte, aus denen ein vorgegebenes Wort oder eines von mehreren vorgegebenen Worten erzeugbar sind.

Abgrenzung von natürlichen Sprachen

Mit Hilfe formaler Sprachen können auch natürliche Sprachen modelliert werden, vor allem deren Syntax. Beim Vergleich formaler Sprachen mit natürlichen Sprachen ist aber zu beachten, dass natürliche Sprachen oberhalb der elementaren Laut-Zeichen mindestens die zwei übereinander liegenden Hierarchieebenen des Wortes und des Satzes besitzen. Die Regeln für deren Aufbau trennt man gewöhnlich in Morphologie zum einen und in Syntax zum anderen. In formalen Sprachen dagegen liegt über dem elementaren Alphabet-Zeichen oft nur die eine Hierarchieebene des formalen Wortes, man redet im Hinblick auf den Bau der Worte formalsprachlich von Syntax. Wenn eine natürliche Sprache mittels einer formalen modelliert wird, dann werden also die Sätze der natürlichen Sprache in formalsprachlicher Betrachtung Worte genannt.

Außerdem haben Äußerungen in natürlicher Sprache eine natürliche Bedeutung, während die Bedeutung formaler Sprachen stets auf ebenfalls formalem Weg definiert werden muss.

Beispiele

  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: \mathbb{N}_{\rm un} := \{\varepsilon,1,11,111,1111,\ldots \}
  3. Die unäre Sprache über {a}, die nur Wörter quadratischer Länge enthält: {\rm quad\_count} := \{ a^{(n^2)} | n\in\mathbb N\}
  4. {\rm count}_2 := \{ a^nb^n | n\in\mathbb N\}
  5. {\rm count}_3 := \{ a^nb^nc^n | n\in\mathbb N\}
  6. Die Sprache aller Palindrome: {\rm pal} := \{w \in \{0,1\}^* | w=w^R \}
    wobei wR die Spiegelung des Wortes w ist.
  7. Die Dezimalkodierung der Primzahlen: {\rm prim}_{\rm dec} := \{{\rm dec}(p) | p \in {\rm PRIM} \}.
    Hierbei bezeichnet {\rm dec}\colon \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.
  8. Die Morse- oder Thue-Folge: {\rm thue} := \{ h^n_t(0) | n\in\mathbb{N} \}.
    Wobei ht ein Homomorphismus ist, der folgendermaßen definiert ist: ht(ε) = ε und ht(w0): = ht(w)01, ht(w1): = ht(w)10.
    Somit sind die ersten Elemente der Thue-Folge: 0, 01, 0110, 01101001, 0110100110010110...

Operationen auf formalen Sprachen

Zwei Sprachen L1 über dem Alphabet Σ1 und L2 über dem Alphabet Σ2 sind banalerweise beide Sprachen auch über \Sigma_1 \cup \Sigma_2, also Mengen von Worten aus (\Sigma_1 \cup \Sigma_2)^*. Deshalb sind auch

Sprachen über \Sigma_1 \cup \Sigma_2.

Weitere Operationen auf Mengen sind:

Konkatenation

Die Konkatenation zweier Sprachen L1 und L2 ist die Sprache der Wörter, die durch Hintereinanderschreibung (Konkatenation) je eines beliebigen Wortes u aus L1 und v aus L2 entsteht:

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 \varepsilon ,\, aab ,\, bb \rbrace = \lbrace abb ,\, bab ,\, abbaab ,\, babaab ,\, abbbb ,\, babbb \rbrace

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

L \circ \lbrace \varepsilon \rbrace = \lbrace \varepsilon \rbrace \circ L = L

Das absorbierende Element der Konkatenation ist die leere Sprache, sodass für jede Sprache L \subseteq \Sigma^* gilt:

L \circ \{ \} = \{ \} \circ 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

Da außerdem die Potenzmenge der Kleeneschen Hülle eines beliebigen Alphabets Σ (die gleich der Menge aller Sprachen ist, die aus Σ gebildet werden können) abgeschlossen bezüglich Konkatenation ist, bildet sie zusammen mit der Konkatenation als Operator und der Sprache des leeren Wortes als neutrales Element einen Monoiden.

Potenz

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

L0: = {ε}
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 \varepsilon \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 \varepsilon \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:

Ln = {w}n = {wn}

Kleene-*-Abschluss und Kleene-+-Abschluss

Der Kleene-*-Abschluss L * (auch Iteration genannt) und der Kleene-+-Abschluss L + einer formalen Sprache L sind definiert über die Vereinigung der Potenzsprachen von L:

L^* := \bigcup_{i\in\mathbb N_0}L^i
L^+ := \bigcup_{i\in\mathbb N} L^i

Siehe auch: Kleenesche Hülle


Wichtige formale Sprachklassen

  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 Lindenmayer-Systeme.
  3. Mit Semi-Thue-Systemen lassen sich Sprachen festlegen, die aus Startwörtern abgeleitet 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 äquivalent 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

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 und 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 bei der Oldenbourg R. Verlag GmbH. Im Jahr 2004 erschien bei Addison-Wesley eine zweite überarbeitete Auflage.
Das englische Original ist das in der theoretischen Informatik am häufigsten zitierte Buch. Die Beweise sind in älteren deutschen Übersetzungen 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 formalsprachlichen 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
  • S. Abramsky, Dov M. Gabbay, T.S.E. Maibaum (eds.): Handbook of logic in computer science. Vol. 5: Logical and algebraic methods. Oxford University Press 2000, ISBN 0-19-853781-6
  • Mogens Nielsen, Wolfgang Thomas: Computer Science Logic. Springer 1998, ISBN 3-540-64570-5

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • formale Sprache — formale Sprache,   eine mithilfe einer formalen Grammatik ableitbare Menge von Zeichenketten. Die formale Grammatik stellt hier die Regeln zur Bildung der Zeichenketten aus einem Zeichenvorrat oder Alphabet zur Verfügung. Bezeichnet man die… …   Universal-Lexikon

  • Konkatenation (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. Beteilige dich dazu an der Diskussion über diese… …   Deutsch Wikipedia

  • Potenz (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. Beteilige dich dazu an der Diskussion über diese… …   Deutsch Wikipedia

  • Formale Grammatik — Formale Grammatiken sind mathematische Modelle von Grammatiken, die mit Hilfe des Semi Thue Systems angegeben werden und durch die formale Sprachen beschrieben und erzeugt werden können. Sie werden in der theoretischen Informatik, insbesondere in …   Deutsch Wikipedia

  • Sprache — Diese Seite wird derzeit im Sinne der Richtlinien für Begriffsklärungen auf der Diskussionsseite des Wikiprojektes Begriffsklärungen diskutiert. Hilf mit, die Mängel zu beseitigen, und beteilige dich an der Diskussion! Hinweise zur Überarbeitung …   Deutsch Wikipedia

  • Formale Systeme — 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. Beteilige dich dazu an der Diskussion über diese… …   Deutsch Wikipedia

  • Formale Semantik — beschäftigt sich mit der exakten Bedeutung von künstlichen oder natürlichen Sprachen. Dabei kann sowohl die Bedeutung bestehender Sprachen untersucht als auch die Bedeutung neu geschaffener Sprachen festgelegt werden. In Abgrenzung zur Semantik… …   Deutsch Wikipedia

  • Sprache — Sprechvermögen; Ausdrucksform * * * Spra|che [ ʃpra:xə], die; , n: 1. <ohne Plural> das Sprechen; die Fähigkeit zu sprechen: durch den Schock verlor er die Sprache; die Sprache wiederfinden. 2. System von Zeichen und Lauten, das von… …   Universal-Lexikon

  • Formale Logik — Neben der Lehre vom Urteil und der in diesen verwendeten Begriffe geht es in der Logik besonders um die Analyse und Konstruktion logischer Schlussfolgerungen, wobei hier formale Aspekte, ohne Bezug auf den semantischen Gehalt der betrachteten… …   Deutsch Wikipedia

  • Formale Spezifikation — Eine formale Spezifikation ist die Beschreibung eines Computerprogramms mittels einer Notation, deren Semantik eindeutig definiert ist (einer sogenannten formalen Sprache). Ziel ist die formalisierte, präzise Beschreibung der zu lösenden Aufgabe… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”