imported>Aka: typografische Anführungszeichen, Komma ergänzt

2024-08-13T10:33:24Z

typografische Anführungszeichen, Komma ergänzt

Neue Seite

Eine '''formale Sprache''' ist eine [[Abstraktion|abstrakte]] [[Sprache]], bei der im Unterschied zu [[Natürliche Sprache|natürlichen Sprachen]] oft nicht die [[Kommunikation]] im Vordergrund steht, sondern die Definition und Anwendung [[Formales System|formaler Systeme]] im engeren Sinn und der [[Logik]] im weiteren, allgemeinen Sinn. Eine formale Sprache besteht aus einer bestimmten Menge von Symbolketten (im Allgemeinen [[Zeichenkette]]n) („Wörter“ der Sprache), die aus einem [[Alphabet (Informatik)|Zeichen-/Symbolvorrat]] („Alphabet“, Grundsymbole) zusammengesetzt werden können. Während die Logik die Begrifflichkeit „Formale Sprache“ untersucht, finden formale Sprachen z. B. in der [[Mathematik]], in der [[Linguistik]] und der [[Theoretische Informatik|theoretischen Informatik]] eine praktische Anwendung.

Formale Sprachen eignen sich zur (logisch) präzisen Beschreibung des Umgangs mit Zeichenketten. So können zum Beispiel [[Datenformat]]e oder ganze Programmiersprachen spezifiziert werden. Zusammen mit einer [[Formale Semantik|formalen Semantik]] erhalten die definierten Zeichenketten eine (logische) 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 Logik[[kalkül]]e definiert werden, mit denen mathematische Schlüsse gezogen werden können. In Verbindung mit formal definierten Programmiersprachen können Kalküle helfen, Programme auf ihre [[Korrektheit (Informatik)|Korrektheit]] zu überprüfen.

== Definition ==
Eine formale Sprache <math>L</math> über einem Alphabet <math>\Sigma</math> ist eine Teilmenge der [[Kleenesche Hülle|Kleeneschen Hülle]] des Alphabets: <math>L \subseteq \Sigma^*</math>.

Ein '''Alphabet''' <math>\Sigma</math> legt die Zeichen fest, aus denen ein '''Wort''' der Sprache gebildet werden kann. Zum Beispiel kann man die Dezimaldarstellung jeder [[Natürliche Zahl|natürlichen Zahl]] aus dem Alphabet <math>\Sigma = \{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \}</math> bilden.

Alle aus einem gegebenen Alphabet <math>\Sigma</math> beliebig bildbaren [[Wort (Theoretische Informatik)|Wörter]] mit endlicher Länge (Länge 0 oder länger), deren jeder einzelne Buchstabe Element von <math>\Sigma</math> ist, diese größtmögliche Wortmenge zum Alphabet <math>\Sigma</math>, nennt man die ''Kleenesche Hülle'' des Alphabetes <math>\Sigma</math>, kurz <math>\Sigma^*</math>. Eine formale Sprache über einem Alphabet <math>\Sigma</math> ist also eine bestimmte [[Teilmenge]] der Kleeneschen Hülle ihres Alphabets – im Allgemeinen ist also ''nicht'' jede beliebige Zeichenkombination ein gültiges Wort der Sprache.

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 Wörter definiert sein: „Die Sprache … ist die Menge aller Wörter, für die gilt …“.

Die in der theoretischen Informatik auftretenden Sprachen sind jedoch meistens spezieller durch ein bestimmtes Ersetzungsverfahren definiert – Regeln, wie die Alphabet-Zeichen kombiniert sein/werden dürfen. Von den Ersetzungsverfahren gibt es verschiedene Typen: [[Semi-Thue-System]]e, [[Chomsky-Hierarchie|Chomsky-Grammatiken]], [[Lindenmayer-System]]e u. a. Bei solchen Ersetzungsverfahren geht man beispielsweise von einer spezifischen Start-Zeichenkette aus, die man durch wiederholte („rekursive“) Anwendung der Regeln (Text-Ersetzungen) schrittweise in Wortgebilde überführt, die dann als ganzes, oder nur ein vorgegebener Abschnitt davon, als Wörter der Sprache gelten. Man redet hier auch von ''generativen Grammatiken'', weil die Wörter einer Sprache über solche Textsubstitutionen schrittweise ''erzeugt'' werden. Umgekehrt kann man Sprachen auch definieren als die Menge aller Wörter, aus denen (über das Ersetzungsverfahren der Sprache) ein bestimmtes vorgegebenes Wort oder eines von mehreren vorgegebenen Wörtern erzeugbar ist. („Es gehört alles zur Sprache, was sich über die Regeln auf … zurückführen lässt.“)

== Abgrenzung von natürlichen Sprachen ==
Mit Hilfe formaler Sprachen können auch [[natürliche Sprache]]n 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 (Sprache)|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 ''[[Wort (Theoretische Informatik)|Wortes]]'', man redet im Hinblick auf den Bau der Wörter 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 ''Wörter'' genannt.

== Beispiele ==
# Die [[Programmiersprache]] [[C (Programmiersprache)|C]] ist eine formale Sprache. Die Wörter von C sind die jeweiligen Programme. Das Alphabet von C sind die [[Schlüsselwort (Programmierung)|Schlüsselwörter]] und Zeichen, die in der Definition von C festgelegt sind.
# Die natürlichen Zahlen in unärer Darstellung: <math>\mathbb{N}_{\rm un} := \{\varepsilon,1,11,111,1111,\ldots \}</math>
# Die unäre Sprache über <math>\{a\}</math>, die nur Wörter quadratischer Länge enthält: <math>{\rm quad\_count} := \{ a^{(n^2)} \mid n\in\mathbb N\}</math>
# Die Sprache, die <math>n</math> <math>a</math>s gefolgt von <math>n</math> <math>b</math>s enthält: <math>{\rm count}_2 := \{ a^nb^n \mid n\in\mathbb N\}</math>
# Die Sprache, die <math>n</math> <math>a</math>s gefolgt von <math>n</math> <math>b</math>s gefolgt von <math>n</math> <math>c</math>s enthält: <math>{\rm count}_3 := \{ a^nb^nc^n \mid n\in\mathbb N\}</math>
# Die Sprache aller [[Palindrom (Theoretische Informatik)|Palindrome]]: <math>{\rm pal} := \{w \in \{0,1\}^* \mid w=w^R \}</math>, wobei <math>w^R</math> die [[Spiegelung (Wort)|Spiegelung]] des Wortes <math>w</math> ist.
# Die Dezimalkodierung der Primzahlen: <math>{\rm prim}_{\rm dec} := \{{\rm dec}(p) \mid p \in {\rm PRIM} \}</math>. Hierbei bezeichnet <math>{\rm dec}\colon \mathbb{N} \rightarrow \{0,1,2,3,4,5,6,7,8,9\}^*</math> die Kodierung der natürlichen Zahlen im [[Dezimalsystem]] und PRIM steht für die Menge der [[Primzahl]]en.
# Die [[Morsefolge|Morse-]] oder [[Morsefolge|Thue-Folge]]: <math>{\rm thue} := \{ h^n_t(0) \mid n\in\mathbb{N} \}</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 …

== Operationen auf formalen Sprachen ==
Zwei Sprachen <math>L_1</math> über dem Alphabet <math>\Sigma_1</math> und <math>L_2</math> über dem Alphabet <math>\Sigma_2</math> sind banalerweise beide Sprachen auch über <math>\Sigma_1 \cup \Sigma_2</math>, also Mengen von Wörtern aus <math>(\Sigma_1 \cup \Sigma_2)^*</math>. Deshalb sind auch
* die [[Vereinigungsmenge|Vereinigung]] <math>L_1 \cup L_2</math>
* der [[Durchschnittsmenge|Durchschnitt]] <math>L_1 \cap L_2</math>
* die [[Differenzmenge|Differenz]] <math>L_1 \setminus L_2</math>
Sprachen über <math>\Sigma_1 \cup \Sigma_2</math>.

Weitere Operationen auf Sprachen sind:

=== Konkatenation ===

Die '''Konkatenation''' zweier Sprachen <math>L_1</math> und <math>L_2</math> ist die Sprache der Wörter, die durch Hintereinanderschreibung ([[Konkatenation (Wort)|Konkatenation]]) je eines beliebigen Wortes <math>u</math> aus <math>L_1</math> und <math>v</math> aus <math>L_2</math> entsteht:

:<math>L_1 \circ L_2 := \{ uv \mid u \in L_1, v \in L_2 \}</math>.

So sind zum Beispiel die Konkatenationen von verschiedenen Sprachen über dem Alphabet <math>\Sigma = \{ a ,\, b \}</math>:

:<math>\{ a \} \circ \{ ab \} = \{ aab \}</math>
:<math>\{ a ,\, bb \} \circ \{ aa ,\, b \} = \{ aaa ,\, ab ,\, bbaa ,\, bbb \}</math>
:<math>\{ abb ,\, bab \} \circ \{ \varepsilon ,\, aab ,\, bb \} = \{ abb ,\, bab ,\, abbaab ,\, babaab ,\, abbbb ,\, babbb \}</math>

Das [[Neutrales Element|neutrale Element]] der Konkatenation ist die Sprache, welche nur das [[Leeres Wort|leere Wort]] enthält. So gilt für jede beliebige Sprache <math>L</math>:

:<math>L \circ \{ \varepsilon \} = \{ \varepsilon \} \circ L = L</math>

Das [[Absorbierendes Element|absorbierende Element]] der Konkatenation ist die leere Sprache, sodass für jede Sprache <math>L \subseteq \Sigma^*</math> gilt:

:<math>L \circ \{ \} = \{ \} \circ L = \{ \}</math>

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

:<math>(\{ a ,\, bab \} \circ \{ a ,\, b \}) \circ \{ ab \} = \{ a ,\, bab \} \circ (\{ a ,\, b \} \circ \{ ab \}) = \{ aaab ,\, abab ,\, babaab ,\, babbab \}</math>

aber:

:<math>\{ a ,\, bab \} \circ \{ a ,\, b \} = \{ aa ,\, ab ,\, baba ,\, babb \} \not= \{ aa ,\, abab ,\, ba ,\, bbab \} = \{ a ,\, b \} \circ \{ a ,\, bab \}</math>

Da außerdem die [[Potenzmenge]] der [[Kleenesche Hülle|Kleeneschen Hülle]] eines beliebigen Alphabets <math>\Sigma</math> (die gleich der Menge aller Sprachen ist, die aus <math>\Sigma</math> gebildet werden können) [[Abgeschlossenheit (algebraische Struktur)|abgeschlossen]] bezüglich Konkatenation ist, bildet sie zusammen mit der Konkatenation als Operator und der Sprache des leeren Wortes als neutrales Element ein [[Monoid]].

=== Potenz ===

Die '''Potenz''' <math>L^n</math> einer Sprache ist die <math>n</math>-fache Konkatenation dieser Sprache mit sich selbst. Sie ist rekursiv definiert mit:

:<math>L^0 := \{\varepsilon\}</math>
:<math>L^{n+1} := L^n \circ L</math>   (für <math>n \in \mathbb{N}_0</math>)

So sind zum Beispiel:

:<math>\lbrace aa ,\, abab ,\, bbab ,\, ba \rbrace^0 = \lbrace \varepsilon \rbrace</math>
:<math>\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</math>
:<math>\lbrace a \rbrace^4 = \lbrace a \rbrace \,\circ\, \lbrace a \rbrace \,\circ\, \lbrace a \rbrace \,\circ\, \lbrace a \rbrace = \lbrace aaaa \rbrace</math>

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

:<math>L^n = \lbrace w \rbrace^n = \lbrace w^n \rbrace</math>

=== Kleene-*-Abschluss und Kleene-+-Abschluss ===
Der '''Kleene-*-Abschluss''' <math>L^*</math> (Kleenesche Hülle, auch '''Iteration''' genannt) und der '''Kleene-+-Abschluss''' <math>L^+</math> (positive Hülle) einer formalen Sprache <math>L</math> sind definiert über die [[Vereinigungsmenge|Vereinigung]] der Potenzsprachen von <math>L</math>:

:<math>L^* := \bigcup_{i\in\mathbb N_0}L^i</math>
 
:<math>L^+ := \bigcup_{i\in\mathbb N} L^i</math>

{{Siehe auch|Kleenesche und positive Hülle}}



== Wichtige formale Sprachklassen ==
# [[Noam Chomsky]] hat 1956 eine Hierarchie von [[Formale Grammatik|formalen Grammatiken]] aufgestellt, die verschiedene Typen von formalen Sprachen erzeugen.<ref>Chomsky, Noam (1956). "Three models for the description of language". IRE Transactions on Information Theory (2): 113–124.</ref> 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 Sprache|Rekursiv aufzählbare]], [[Kontextsensitive Sprache|kontextsensitive]], [[Kontextfreie Sprache|kontextfreie]] bzw. [[Reguläre Sprache|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 [[Lindenmayer-System]]e.
# Mit [[Semi-Thue-System]]en lassen sich Sprachen festlegen, die aus Startwörtern abgeleitet werden.
# Mit [[Church-Rosser-System]]en werden Sprachen erklärt, deren Wörter sich auf ein Terminalwort reduzieren lassen.
# [[Termersetzungssystem]]e erzeugen die Menge von Termen, die zu einem Ausgangsterm äquivalent sind.
# Verallgemeinerungen von formalen Sprachen erhalten wir mit [[Graphgrammatik]]en, mit denen wir Graphsprachen erzeugen können.
# [[Hypergraphgrammatik]]en erzeugen [[Hypergraph]]en, eine Verallgemeinerung von Graphen.

== Historisches ==
Als eine der ersten formalen Sprachen wird [[Gottlob Frege]]s ''[[Begriffsschrift]]'' erachtet<ref>Martin Davis (1995). ''Influences of Mathematical Logic on Computer Science.'' In Rolf Herken. The universal Turing machine: a half-century survey. Springer. S. 290, ISBN 978-3-211-82637-9.</ref>, eine wie Frege schrieb „Formelsprache des reinen Denkens“. [[Axel Thue]]s im Jahre 1914<ref>Ronald V. Book, Friedrich Otto: ''String-rewriting Systems.'' Springer, 1993, ISBN 0-387-97965-4, S. 36.</ref> eingeführtes [[Semi-Thue-System]], das verwendet werden kann, um Zeichenketten zu transformieren, hatte ebenfalls Einfluss auf die Entwicklung formaler Grammatiken.

=== Zitat ===
Die heutige Grundlagenforschung ist beherrscht {{Zitat| […] vom Geist der Mathematik. […] Sie ist durchmathematisiert bis an die äußersten Grenzen dessen, was heute auf Grund einer weit vorgerückten Formalisierungstechnik erreicht werden kann. Das Ziel dieser Forschung ist ein ziemlich hochliegendes Ziel. Es ist die Beherrschung einer möglichst großen Zahl von möglichst tiefliegenden Problemen aus dem Bereich der Grundlagenforschung mit einer Art von Genauigkeit, die als ‚Genauigkeit in den kleinsten Teilen‘ bezeichnet werden kann. […]

Die angestrebte Genauigkeit kann wie in der Mathematik nur durch die Schöpfung von '''Präzisionssprachen''' erreicht werden, die angestrebte Genauigkeit in den kleinsten Teilen nur durch die Schöpfung von Präzisionssprachen, deren Genauigkeitsgrad den Genauigkeitsgrad auch der höchstentwickelten mathematischen Präzisionssprache des gegenwärtigen Zeitalters, der Sprache der [[Mengenlehre]] und der Sprache der modernen [[abstrakte Algebra|Algebra]] wesentlich übertrifft. […] Eine solche Präzisionssprache ist eine formalisierte wissenschaftliche Sprache. […] ein Rüstzeug, dessen Leistungsfähigkeit mit dem Auflösungsvermögen eines [[Elektronenmikroskop]]s verglichen werden kann. […] [[Gottfried Wilhelm Leibniz|Leibniz]] ist der erste gewesen, der Präzisionssprachen von diesem Genauigkeitsgrad gefordert hat. |[[Heinrich Scholz (Logiker)|Heinrich Scholz]] im Jahre 1941: Eine neue Gestalt der Grundlagenforschung<ref>In: ''Forschungen und Fortschritte'' Nr. 35/36, Jahrgang 1941, S. 382 ff.</ref>}}

Heinrich Scholz traf sich 1944 mit [[Konrad Zuse]], der im Zuge seiner Doktorarbeit an seinem [[Plankalkül]] arbeitete. Im März 1945 sprach ihm Scholz für die Anwendung seines Logikkalküls seine Anerkennung aus.<ref>[[Hartmut Petzold]]: ''Moderne Rechenkünstler. Die Industrialisierung der Rechentechnik in Deutschland.'' C.H. Beck Verlag, München 1992.</ref>

== Siehe auch ==
* [[konstruierte Sprache]]
* [[Computersprache]]
* [[:Kategorie:Formale Sprache]] – Auflistung von formalen Sprachen
Anwendungen siehe in:
* [[Berechenbarkeitstheorie]]
* [[Komplexitätstheorie]]
* [[Kryptographie]]
* [[Kryptoanalyse]]
* [[Compilerbau]]

== 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 Ullman|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

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=4017848-1|LCCN=|NDL=|VIAF=}}

[[Kategorie:Formale Sprachen| ]]

Formale Sprache - Versionsgeschichte

imported>Aka: typografische Anführungszeichen, Komma ergänzt