Sie sind hier:

Überblick

Die sogenannten formalen Sprachen sind ein wichtiges Teilgebiet der theoretischen Informatik. Es beschreibt (in sehr mathematischer Prägung) Eigenschaften von Wortmengen, die als Eingabe von einem Informatiksysteme akzeptiert werden sollen. Eine solche Wortmenge nennt man „Sprache“. In der Regel muss das Informatiksystem mit der Eingabe eine Gültigkeitsprüfung durchführen („soll dieses Wort als Eingabe akzeptiert werden?“) und/oder die Eingabe in irgendeiner Form verarbeiten (also analysieren, in andere Form übersetzen o.ä.).

Es gibt viele Beispiele für formale Sprachen bzw. Software, die damit umgeht:

Eingabefelder prüfen Mailadressen: Eine Eingabe wie „anna@mail.de“ soll akzeptiert, „annaQmail.de“ oder „anna@mailde“ aber sofort zurückgewiesen werden, weil das keine global gültigen Mailadressen sein können¹ . Eine gültige Adresse ist hier ein „Wort“, die Menge aller gültigen Mailadressen eine „Sprache“ im oben genannten Sinne.
Webbrowser verarbeiten HTML: Der angelieferte HTML-Quelltext muss zuerst analysiert und interpretiert werden. Sind die Fragen „ist das korrektes HTML?“ und „was soll angezeigt werden?“ beantwortet, erzeugen sie schließlich eine bunte Bildschirmdarstellung.
Compiler übersetzen Programme: Sie nehmen den Quelltext eines Programms entgegen, prüfen auf syntaktische Korrektheit und übersetzen es in eine andere Form, die der Computer (mehr oder weniger direkt) ausführen kann.

Mit den formalen Sprachen untrennbar verbunden ist die zugehörige Theorie der Automaten² , wobei Automat hier eher „Denkmodell“ bedeutet als „Maschine“. Es gibt unterschiedliche Klassen von Automaten, die einerseits mathematisch präzise beschrieben und untersucht werden; andererseits kann jeder Typ Automat jeweils einen bestimmten Typ Sprachen verarbeiten. Weil man sie zudem leicht in Software implementieren kann, sind sie in der praktischen Informatik extrem nützlich.

In ihrer Kombination sind formale Sprachen und Automaten ein Grundpfeiler der Informatik. Der Abschnitt 3.3.5 des Bildungsplans für allgemein bildende Gymnasien in Baden-Württemberg enthält im Wesentlichen reguläre und kontextfreie Sprachen und die dazu passenden Typen von Automaten:

Typ der Sprache bzw. Grammatik	dazu passender Automatentyp	Beispielsprache	Hier behandelt
reguläre BP: Items 9, 10	endliche Automaten BP: 7, 10, 15	gültige Mailadressen	ja
kontextfreie BP: 13, 14	Kellerautomaten BP: 13	Rechenausdrücke mit beliebig tief geschachtelten Klammern: ((2+a)((3+x)2)-1)/5	ja
kontextsensitive BP: 14	Turingmaschinen BP: nicht enthalten	XML, Java	nein (nur als Kontrast zu kontextfreien)
rekursiv aufzählbare BP: nicht enthalten	Turingmaschinen BP: nicht enthalten		nein

¹ LibreOffice (mit dem dieses Dokument entsteht) sieht offenbar auch das dritte Beispiel als gültige Adresse an – sie wird daher ohne Zutun des Autors in anderer Farbe gesetzt und mit einem Link auf ein Mailprogramm unterlegt.

² Wichtige Fachbegriffe werden bei ihrem ersten Auftreten innerhalb dieses Skripts fett gesetzt.

Hintergrundinformationen: Herunterladen [odt][669 KB]

Weiter zu Alphabet, Wort, Sprache