Formale Sprache

Stichpunkte

Allgemein
	sowie beim Compilerbau Anwendung finden. Inhaltsverzeichnis showTocToggle("Anzeigen"
	die besonders in der theoretischen Informatik
	"Verbergen") 1 Definitionen 2 Klassifikation von Grammatiken formaler Sprachen 3 Beispiele 4 Natürliche Sprachen 5 Siehe auch [Bearbeiten]
	Formale Sprachen sind mathematische Objekte
	bei Berechenbarkeits- und Komplexitätstheorie
Definitionen
	Eine formale Sprache <math>L<math> ist eine Menge von Wörtern über einem Alphabet <math>Sigma<math>
	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)
	z.B. <math>w = hallo implies |w| = 5<math>
	Die Länge eines Wortes ist die Anzahl der Folgenglieder
	denn für jedes Wort <math>u<math> gilt <math>u varepsilon = varepsilon u = u<math>. Man sieht
	man betreibt in der theoretischen Informatik Algebra mit Wörtern und Zeichen
	man bezeichnet diese Operation als Konkatenation und schreibt <math>w = u cdot v<math> oder kürzer <math>w = uv<math>. Es gibt auch ein leeres Wort <math>varepsilon<math>
	statt wie gewohnt mit Zahlen
	Zwei Wörter <math>u<math> und <math>v<math> kann man zu einem neuen Wort <math>w<math> aneinanderreihen
	welches das neutrale Element bezüglich der Konkatenation darstellt
	vin L_b }<math>. Also alle Wörter
	die man bilden kann
	indem ein Wort aus <math>L_a<math> und ein Wort aus <math>L_b<math> aneinandergereiht werden
	Die Konkatenation zweier Sprachen <math>L_a<math> und <math>L_b<math> ist <math>L_a cdot L_b = { uv | uin L_a
	2
	dabei wird <math>L^1 = L<math> und <math>L^0 = { varepsilon }<math> definiert (beachte: die Menge
	die nur das leere Wort enthält
	Man kann durch <math>L^{n+1} = L^n cdot L<math> induktiv die Potenz <math>L^n<math> einer Sprache <math>L<math> für <math>n in mathbb{N} <math> mit <math> mathbb{N} = { 0
	ist selbst nicht leer!) Jetzt können wir die Menge aller endlichen Wörter über dem Alphabet <math>Sigma<math> hinschreiben: <math>L = Sigma^*<math>
	1
	wobei <math>M^*=bigcup_{iinmathbb{N}} M^i<math> und wir hier die Symbole <math>a<math> aus <math>Sigma<math> mit den Wörtern <math>a<math> der Länge 1 identifizieren
	ldots } <math> definieren
	Die Operation <math>.^*<math> wird auch als endlicher (oder kleenescher) Abschluss bezeichnet
	der Operator selbst als Kleene-Stern (siehe Kleenesche Hülle)
	Die Menge dieser Wörter kann endlich oder unendlich sein
	Man spricht dann auch von einer endlichen bzw. unendlichen Sprache. [Bearbeiten]
Klassifikation von Grammatiken formaler Sprachen
	die verschiedene Typen von formalen Sprachen erzeugen
	Noam Chomsky hat eine Hierarchie von formalen Grammatiken aufgestellt
	Diese ist heute unter dem Namen Chomsky-Hierarchie bekannt
	Während Grammatiken Wörter einer Sprache produzieren
	ob ein Wort zu einer Grammatik passt
	um Sprachen zu akzeptieren
	werden Automaten verwendet
	das heißt zu entscheiden
	also als ein Regelsatz zur Erzeugung von Wörtern der Sprache
	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
	die genau die Wörter dieser formalen Sprachen erkennen
	Dagegen sind die äquivalenten Automaten (zum Beispiel ein endlicher Automat oder Kellerautomat) mathematische Modelle für Maschinen oder Programme
	der Wörter dieser Grammatik erkennt (siehe Parser-Generator). [Bearbeiten]
	Aus einer gegebenen Grammatik lässt sich auch automatisch ein Automat erzeugen
Beispiele
	b
	Wir betrachten das Alphabet <math>Sigma = {a
	c}<math>
	Dann sind <math>u = abcab<math> und <math>v = aaabbb<math> zum Beispiel Wörter über diesem Alphabet. <math>w = abcdef<math> ist kein Wort über diesem Alphabet
	<math>e<math> und <math>f<math> nicht im Alphabet <math>Sigma<math> vorkommen
	da <math>d<math>
	Die Verkettung der Wörter <math>aaa<math> und <math>bbbcc<math> (in dieser Reihenfolge) ergibt dann das Wort <math>aaabbbcc<math>
	Die Verkettung von <math>aaabb<math> mit dem "leeren Wort" <math>varepsilon<math> ergibt erneut <math>aaabb<math>
	b
	die erst mit einer Folge von <math>a<math> beginnt
	c}<math> könnte zum Beispiel die Menge aller Wörter sein
	Eine formale Sprache über dem Alphabet <math>{a
	dann mit einer Folge von <math>b<math> weitergeht und zuletzt mit einer Folge von <math>c<math> endet
	j
	k in mathbb{N} } <math> beschrieben werden. [Bearbeiten]
	Diese Sprache könnte formal als <math>L = { a^ib^jc^k | i
Natürliche Sprachen
	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
	zum Beispiel um maschinelle Übersetzung zu ermöglichen
	Wissenschaftliche Fachrichtungen wie die Computerlinguistik beschäftigen sich mit der algorithmischen Bearbeitung von natürlichen Sprachen
	hängt von der bisher ungeklärten Einstufung der natürlichen Sprachen in die Chomsky-Hierarchie ab. [Bearbeiten]
	Inwiefern dies effizient möglich ist
Siehe auch
	Lindenmayer-Systeme Chomsky-Hierarchie Formale Grammatik en:Formal language es:Lenguaje formal fr:Langage formel ja:形�言語 nl:Formele taal pl:Język formalny zh:形�语言

Dieser Artikel basiert auf dem Artikel Formale Sprache aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.