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
Grammatiken und Sprachen: Reguläre Sprachen lassen sich durch endliche Automaten akzeptieren bzw. durch reguläre Grammatiken beschreiben.
Eigenschaften und Grenzen: Reguläre Sprachen sind abgeschlossen unter Vereinigung, Konkatenation und Kleene-Stern. Kontextfreie Sprachen sind abgeschlossen
Anwendungen: Formalsprachentheorie bildet die theoretische Grundlage des Compilerbaus, von Parser-Generatoren und der formalen Verifikation von Softwaresystemen.