Formalsprachentheorie

Formalsprachentheorie ist ein Teilgebiet der theoretischen Informatik, das sich mit formalen Sprachen beschäftigt. Eine formale Sprache ist eine Menge von Wörtern über ein endliches Alphabet. Sprachen werden häufig durch Grammatiken, Automaten oder logische Beschreibungen definiert und dienen als abstrakte Modelle für Syntaxstrukturen in Programmiersprachen, Textverarbeitung und formaler Verifikation.

Wichtige Modelle sind endliche Automaten (reguläre Sprachen), Pushdown-Automaten (kontextfreie Sprachen), kontext-sensitive Grammatiken oder lineare beschränkte Automaten (kontext-sensitive Sprachen) sowie Turingmaschinen (rekursiv aufzählbare Sprachen). In der Chomsky-Hierarchie werden Sprachen den Typen Typ-3 bis Typ-0 zugeordnet: Typ-3 regulär, Typ-2 kontextfrei, Typ-1 kontextabhängig, Typ-0 rekursiv aufzählbar.

Grammatiken und Sprachen: Reguläre Sprachen lassen sich durch endliche Automaten akzeptieren bzw. durch reguläre Grammatiken beschreiben. Kontextfreie Sprachen werden durch kontextfreie Grammatiken beschrieben und durch Pushdown-Automaten akzeptiert. Kontext-sensitive Sprachen erfolgen über kontext-sensitive Grammatiken oder lineare beschränkte Automaten. Typ-0-Sprachen werden durch Turingmaschinen erkannt. Pumping-Lemmas liefern notwendige Eigenschaften für Zugehörigkeiten; viele Entscheidungsprobleme bleiben für allgemein rekursiv aufzählbare Sprachen unentscheidbar.

Eigenschaften und Grenzen: Reguläre Sprachen sind abgeschlossen unter Vereinigung, Konkatenation und Kleene-Stern. Kontextfreie Sprachen sind abgeschlossen unter Vereinigung, Konkatenation und Kleene-Stern, aber nicht unter Komplement oder Schnitt. Die Hierarchie zeigt, dass sich die Komplexität von Sprachen mit strengeren Modellen erhöht und manche Probleme unentscheidbar bleiben, je weiter man in der Hierarchie geht.

Anwendungen: Formalsprachentheorie bildet die theoretische Grundlage des Compilerbaus, von Parser-Generatoren und der formalen Verifikation von Softwaresystemen. Sie wird auch in der Sprachverarbeitung, in der Modellprüfung und in der formalen Spezifikation eingesetzt.