WikiDer > Formelle Sprache

Der Begriff formelle Sprache hat mindestens drei verwandte Bedeutungen:

1. formaler Sprachgebrauch;
2. Sprache, deren Form und Bedeutung in der Regel durch mathematische Definitionen genau festgelegt sind;
3. eine Sammlung von Saiten.

formale Sprache taal

Im allgemeinen Sprachgebrauch ist formale Sprache eine Sprache, die formell ist: es hält sich an Konventionen zur Formulierung des Gesagten, die selbst Teil von Konventionen der Kommunikation sind. Das Gegenteil ist informell Sprache, die sich nicht an solche Konventionen hält.

Beim formalen Sprachgebrauch wird, wenn alle Beteiligten ihn beherrschen, ein spezifischer Kommunikationskontext geschaffen, in dem die Kommunikation viel präziser erfolgen kann, als dies mit der informellen Sprache möglich ist. Dies ist insbesondere bei der Amts- oder Rechtssprache der Fall, in der weitgehend von Standardformulierungen Gebrauch gemacht wird, deren Bedeutung sehr genau bestimmt wurde, teils explizit in Gesetzestexten und Rechtsbeschlüssen, teils implizit aufgrund der langen Geschichte der Verwendung der Formulierungen in früheren Mitteilungen zu dem betreffenden Thema.

Künstliche Sprache

In der Naturwissenschaft und insbesondere in der Mathematik und Informatik ist eine formale Sprache eine geschaffene, künstliche Sprache, deren Form (Syntax) und oft Bedeutung (Semantik) genau festgelegt sind, oft durch mathematische Definitionen. Formale Sprachen werden in der Mathematik und Informatik und einigen verwandten Disziplinen studiert und verwendet. Ziel ist es auch hier, eine sehr präzise Kommunikation zu ermöglichen, indem die Bedeutung von Ausdrücken und Konstruktionen möglichst genau erfasst wird. Viele formale Sprachen sind explizit darauf ausgelegt, von Maschinen verstanden zu werden; dazu gehört die Computersprachen, die verwendet werden, um Informationen auf einem Computer zu speichern oder das Verhalten eines Computers zu programmieren. Darüber hinaus gibt es Informationsdarstellungssprachen oder DatenModellierungssprachen. Beispiele für Informationsrepräsentationssprachen, die auf einer Formalisierung natürlicher Sprachen basieren, sind Gellish Formales Niederländisch und Gellish Formales Englisch. Das Gegenteil einer künstlichen Sprache ist a Natürliche Sprache: eine Sprache wie Niederländisch, die von Menschen verwendet wird, um miteinander zu kommunizieren, und die sich im Laufe dieser Kommunikation allmählich entwickelt hat. Das Linguistik beschäftigt sich mit dem Studium natürlicher Sprachen.

Wenn Form und Bedeutung einer Sprache mathematisch vollständig festgelegt sind, spricht man von a mathematischer Formalismus. Solche Formalismen sind die Grundlage der Mathematik; bestimmte Bereiche der Mathematik und ihrer Anwendungen, wie z mathematische Logik und der Theoretische Informatik, beschäftigen sich intensiv mit der Gestaltung und dem Studium solcher Formalismen.

Die Mathematik selbst entstand, weil Form und Inhalt des logischen Denkens immer mehr formalisiert wurden, bis sich die immer noch am häufigsten verwendeten Formalisierungen etablierten. Grundlagen der Mathematik in dem die Grenzen der mathematischen Formalisierung ausgelotet wurden; einige Mathematiker glaubten sogar, dass mathematisches Denken im Wesentlichen nichts anderes als formale, mechanisch ausführbare Symbolmanipulation ist (eine Ansicht, die Formalismus wird genannt). Damit war auch der Grundstein für die programmierbare Computer.

Gleichzeitig im Linguistik die Notwendigkeit, Form und Bedeutung von menschlich gesprochenen Sprachen wie dem Niederländischen genau zu beschreiben. Eine Möglichkeit, dies zu tun, besteht darin, eine formale Sprache zu definieren, die versucht, sich der natürlichen Sprache in Form und Bedeutung anzunähern.

Dieser Ansatz wurde stark durch die Verfügbarkeit von Computern für den allgemeinen Gebrauch ab den 1950er Jahren angeregt, einerseits weil sie versuchen wollten, Computern zu helfen, natürliche Sprache zu verstehen - zum Beispiel automatische Übersetzung – zum einen, weil erkannt wurde, dass Computersoftware in einer für den menschlichen Programmierer möglichst verständlichen Sprache geschrieben werden sollte. Dies führte zur Erforschung der Frage, welche Eigenschaften solche Sprachen haben sollten und der Frage, wie solche Sprachen richtig beschrieben werden können. Dies führte zum mathematischen Gebiet der formalen Sprachtheorie.

Pionierarbeit in diesem Bereich wurde geleistet von Noam Chomsky.

Sprache in der formalen Sprachtheorie

Formale Sprachtheorie, ein eigenständiges Forschungsgebiet der Theoretische Informatik, formell Logik und mathematische Linguistik, widmet sich dem Studium mathematischer Formalismen zur Bestimmung der bilden (Syntax) von Ausdrücken in formalen Sprachen. Das Inhalt (Bedeutung, Semantik) von Ausdrücken wird in der Regel völlig außer Acht gelassen.

Eine Sprache wird in der formalen Sprachtheorie als eine Sammlung von Zeichenketten definiert, die aus Zeichen bestehen, die aus einem bestimmten endlichen Alphabet ausgewählt werden. Eine solche Sammlung fungiert als Prädikat: die Definition einer Sprache unterscheidet die grammatikalisch Ausdrücke (die zur Sprache gehörenden Zeichenfolgen) der ungrammatischen (die nicht zur Sprache gehörenden Zeichenfolgen). Das Konzept der formalen Sprache in diesem Sinne ist komplementär zum Konzept eines Formalismus in der Mathematik. In der Mathematik wird die genaue Definition der Ausdrucksform als Zeichenkette eher informell verworfen; Wichtig ist die Bedeutung der Ausdrücke. In der formalen Sprachtheorie ist diese genaue Definition Gegenstand der Forschung.

Ein Beispiel ist die Sammlung natürliche Zahlen. Die meisten Mathematiker nehmen diese als gegeben hin oder untersuchen, wie sie ihre Bedeutung am besten definieren können; aber ihre genaue Schreibweise als ${displaystyle mathbb {N} ={0,1,2,ldots}}$ betrachten sie nicht als Gegenstand der Forschung. In der formalen Sprachtheorie kommt es genau auf diese Spezifikation der Notation an: Dezimal, oktal und binärZahlensystem sind zum Beispiel drei verschiedene Sprachen.

Chomsky definierte a Natürliche Sprache als formale Sprache in diesem Sinne: de grammatikalisch Sätze in der Sprache können als formale Sprache über das Alphabet der Buchstaben angesehen werden, mit denen die Sprache geschrieben wird. Die Aufgabe besteht dann darin, eine genaue Definition dieser Sprache zu finden. Für die meisten Sprachen gibt es umfangreiche Grammatiken, die dies weitgehend beschreiben. Chomsky unterschätzte jedoch die Schwierigkeiten bei der vollständigen Umsetzung dieser Idee: Sowohl was genau die elementaren Einheiten sind, aus denen Sätze aufgebaut werden, als auch was genau grammatikalische Sätze sind, sind für natürliche Sprachen nicht genau festgelegt. Die Bedeutung seines Ausgangspunkts wird daher von vielen Linguisten angezweifelt. Darüber hinaus hoffte Chomsky, einen einfachen Formalismus zu finden, der geeignet ist, genau die Art von Sprache zu beschreiben, für die existierende natürliche Sprachen Beispiele sind; er dachte zuerst an die kontextfreie Grammatik. Auch hier war er zu optimistisch: Dieser Formalismus kann zwar Grammatiken definieren, die sich der Struktur natürlicher Sprache grob annähern, aber genaue Beschreibungen realer Sprachen erfordern allerhand zusätzliche Mechanismen.

Dies gilt auch im Informatik, jedoch werden dort Chomskys Techniken und deren Erweiterungen routinemäßig bei der Definition von Computersprachen angewendet. Eine Anwendung ist die genaue Definition von Notationen, zum Beispiel die dezimale Notation natürlicher Zahlen; solche Definitionen sind normalerweise Teil der Definition komplexerer Sprachen, zum Beispiel a Programmiersprache. Eine zweite Anwendung besteht darin, die allgemeine syntaktische Struktur von Ausdrücken in komplexeren Sprachen zu beschreiben: eine solche formale Grammatik (oft in BNF) beschreibt dann alle gültigen Ausdrücke, aber in der Regel werden zusätzliche Regeln benötigt, um alle ungültigen Ausdrücke auszuschließen, die meist informell oder gar nicht angegeben werden.

Definition

EIN formelle Sprache${displaystyle mathbf {mahit {L}} }$ ist ein Sammlung von Wörtern. Ein Wort aus einer formalen Sprache ist eine Folge von Buchstaben aus dem (normalerweise endlichen) Alphabet ${displaystyle mathbf {mathit {Sigma}}}$. Das Schreiben von Buchstaben oder Wörtern hintereinander nennt man Verkettung. Wenn man das betonen will, normalerweise ${displaystyle circ }$ oder ${displaystyle cdot }$ benutzt. Verkettung ist assoziativ, aber nicht kommutativ:

${Anzeigestil für alle u,v,w:(ucirc v)circ w=ucirc (vcirc w)=ucirc vcirc w}$

aber

${Anzeigestil zB für alle u,v:ucirc v=vcirc u}$

Die Verkettungsoperation liefert daher die algebraische Struktur von a monoid über das angegebene Alphabet.

Es ist gegeben leeres Wort, eine Zeile ohne Buchstaben, normalerweise mit ${Anzeigestil Varepsilon }$.Darüber hinaus beschreiben vertikale Streifen normalerweise die Längenfunktion: Wenn ${Anzeigestil w}$ ist ein Wort, dann mit ${Anzeigestil |w|}$ gemeint ist die Länge, also die Anzahl der Buchstaben in der Reihe. Wir haben ${Anzeigestil |varepsilon |=0}$, ${displaystyle forall ain Sigma :|a|=1}$ und ${displaystyle forall v,win Sigma ^{*}:|vcirc w|=|v| |w|}$ (bei welchem ${Displaystil Sigma ^{*}}$ die Sprache aller endlichen Buchstabenfolgen des Alphabets ${Anzeigestil Sigma }$ ist).

Beispiel: Nimm ${Anzeigestil Sigma ={a,b,c}}$. Dann ist ein ein Wort in ${Displaystil Sigma ^{*}}$. Ebenfalls b ist ein Wort in ${Displaystil Sigma ^{*}}$ und auch ab und aabbc und auch ababacacbacabbc. Die Länge des Wortes Bac ist drei und das von Abaca ist fünf.

Natürlich ein Alphabet außer Zeichen in der in römisches alphabet wie wir sie kennen, enthalten sie alle möglichen anderen Zeichen. Beispielsweise ${displaystyle Sigma ={alpha , eta ,gamma }}$. Für viele Anwendungen wissen wir nur, dass wir x verschiedene Symbole haben und es keinen Sinn macht, jedem Symbol eine grafische Darstellung zuzuordnen. In einem solchen Fall werden Symbole oft nummeriert, zum Beispiel: ${Anzeigestil Sigma={0,1,2,3,4,5,6,7,8,9,10,11,12}}$. Ein Wort ist dann eine Reihe von Zahlen.

Ein Wort, das nicht unendlich viele Symbole enthält, hat eine endliche Länge. Die Sammlung aller möglichen Wörter in einem Alphabet ${Anzeigestil Sigma }$ mit endlicher Länge bezeichnet man mit ${Displaystil Sigma ^{*}}$. So eine Sammlung ist also unendlich groß, aber zählbar.

Eine formale Sprache L ist eine Teilmenge von ${Displaystil Sigma ^{*}}$, So:

${displaystyle L_{Sigma }subsetq Sigma ^{*}}$

Sprachklassen

Eine häufig verwendete Hierarchie zur Klassifizierung formaler Sprachen ist die Chomsky-Hierarchie, die Sprachen von Klasse 0 (alle Sprachen) bis Klasse 3 klassifiziert. Jede Klasse in der Hierarchie umfasst auch die Sprachen in nachfolgenden Klassen.

Innerhalb der kontextfreien Sprachklasse gibt es mehrere Unterklassen, die beim Compilerbau besonders wichtig sind, weil sie schneller zu erkennen sind. Auch innerhalb der Klasse der kontextsensitiven Sprachen gibt es subtile Unterklassifikationen, die besonders wichtig sind für Verarbeitung natürlicher Sprache.

Siehe auch

• Van Wijngaarden-Grammatik