Formale Sprache
aus www.iwiki.de, der freien Wissensdatenbank
Alle Sprachen werden durch eine Grammatik beschrieben. Demzufolge wird eine formale Sprache durch eine formale Grammatik beschrieben. Formale Sprachen sind ein Teilgebiet der theoretischen Informatik und werden zum Beispiel im Compilerbau, Berechenbarkeitstheorie und Komplexitätstheorie eingesetzt.
Inhaltsverzeichnis |
Definition
Eine Formale Sprache besteht aus einer Menge von Wörtern. Jedes Wort besteht aus Zeichen, die Teil eines Alphabets sind. Verkettet man einzelne Zeichen aus einem Alphabet entsteht eine Zeichenkette, oft auch als Konkatenation bezeichnet. Durch die Anwendung von Regeln einer formalen Grammatik auf einzelne Zeichen können Wörter gebildet werden. Welche Wörter zur Sprache gehören ist durch die Grammatik festgelegt.
Ein Alphabet A könnte etwa aus den Zeichen {a,b,c} bestehen. Ein Zeichenkette über dieses Alphabet wäre zum Beispiel 'aabbbccc'. Eine Sprache über das Alphabet A könnte die Menge aller Zeichenketten sein, welche die gleiche Anzahl von a, b und c enthalten.
Die Menge der Wörter in einer Sprache beinhaltet auch das 'leere Wort' (ε), eine Zeichenkette mit der Länge null.
Spezifikation
Formale Sprachen können spezifiziert werden durch
- Wörter die mit einer formalen Grammatik erzeugt werden
- Wörter die auf einen regulären Ausdruck passen
- Wörter die von einem Automaten (Turingmaschine, DEA, NDEA)akzeptiert werden
Schreibweisen
- Sprachbeschreibung einer formalen Sprache in Mengennotation
-
Literatur
- John E. Hopcroft and Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley, 1988.
