Formale Sprache Bedeutung, Erklärung und Definition.
Formale Sprachen sind mathematische Objekte, die besonders in der theoretischen Informatik, bei Berechenbarkeits- und Komplexitätstheorie, sowie beim Compilerbau Anwendung finden.
| Table of contents |
|
2 Klassifikation von Grammatiken formaler Sprachen 3 Beispiele 4 Natürliche Sprachen 5 Siehe auch |
Eine formale Sprache ist eine Menge von Wörtern über einem Alphabet . Welche der möglichen Wörter über dem Alphabet zu der Sprache gehören und welche nicht, wird meist durch die Regeln einer formalen Grammatik bestimmt. Dabei ist ein Alphabet einfach eine endliche Menge von Objekten, die man wiederum Symbole oder Zeichen nennt.
Ein Wort der Sprache ist eine Folge solcher Symbolen (Programmierer sagen String oder Zeichenkette dazu). Die Länge eines Wortes ist die Anzahl der Folgenglieder, z.B. .
Zwei Wörter und kann man zu einem neuen Wort aneinanderreihen, man bezeichnet diese Operation als Konkatenation und schreibt
Man sieht, man betreibt in der theoretischen Informatik Algebra mit Wörtern und Zeichen, statt wie gewohnt mit Zahlen.
Die Konkatenation zweier Sprachen und ist
.
Also alle Wörter, die man bilden kann, indem ein Wort aus und ein Wort
aus aneinandergereiht werden.
Man kann durch induktiv die Potenz einer Sprache für
Die Operation wird auch als endlicher (oder kleenescher) Abschluss bezeichnet, der Operator selbst als Kleene-Stern (siehe Kleensche Hülle).
Die Menge dieser Wörter kann endlich oder unendlich sein. Man spricht dann auch von einer endlichen bzw. unendlichen Sprache.
Während Grammatiken Wörter einer Sprache produzieren, werden Automatenen verwendet, um Sprachen zu akzeptieren, das heißt zu entscheiden, ob ein Wort zu einer Grammatik passt. Siehe dazu auch Parser.
Formaler ausgedrückt: eine gegebene Grammatik (zum Beispiel ein regulärer Ausdruck oder eine EBNF-Grammatik) ist als konstruktive Definition für eine formale Sprache L aufzufassen, also als ein Regelsatz zur Erzeugung von Wörtern der Sprache. Dagegen sind die äquivalenten Automaten (zum Beispiel ein endlicher Automat oder Kellerautomat) mathematische Modelle für Maschinen oder Programme, die genau die Wörter dieser formalen Sprachen erkennen. Aus einer gegebenen Grammatik lässt sich auch automatisch ein Automat erzeugen, der Wörter dieser Grammatik erkennt (siehe Parser-Generator).
Wir betrachten das Alphabet . Dann sind und zum Beispiel Wörter über diesem Alphabet. ist kein Wort über diesem Alphabet, da , und nicht im Alphabet vorkommen.
Die Verkettung der Wörter und (in dieser Reihenfolge) ergibt dann das Wort . Die Verkettung von mit dem "leeren Wort" ergibt erneut .
Eine formale Sprache über dem Alphabet könnte zum Beispiel die Menge aller Wörter sein, die erst mit einer Folge von beginnt, dann mit einer Folge von weitergeht und zuletzt mit einer Folge von endet. Diese Sprache könnte formal als beschrieben werden.
Natürliche Sprachen basieren auf endlichen Alphabeten, deshalb sind sie als Teilmenge in der Menge aller Wörter über dem betreffenden Alphabet enthalten und somit auch formale Sprachen. Wissenschaftliche Fachrichtungen wie die Computerlinguistik beschäftigen sich mit der algorithmischen Bearbeitung von natürlichen Sprachen, zum Beispiel um maschinelle Übersetzung zu ermöglichen. Inwiefern dies effizient möglich ist, hängt von der bisher ungeklärten Einstufung der natürlichen Sprachen in die Chomsky-Hierarchie ab.
Lindenmayer-Systeme
Diese Seite ist ein Artikel über Formale Sprache. Seite Versuche, zum von von Beschreibung über bereitzustellen Formale Sprache. Sie konnten Tatsachen über auch finden Formale Sprache. Erklärung von Formale Sprache.Definitionen
oder kürzer .
Es gibt auch ein leeres Wort , welches das neutrale Element bezüglich der Konkatenation darstellt, denn für jedes Wort gilt
. mit definieren, dabei wird und 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 hinschreiben:
, wobei und wir hier die Symbole aus mit den Wörtern der Länge 1 identifizieren.Klassifikation von Grammatiken formaler Sprachen
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.Beispiele
Natürliche Sprachen
Siehe auch
Chomsky-Hierarchie
Formale Grammatik